First of all I want to say you sorry for not making some really easy problems. Next time I will make sure that this does not happen :) First time experimenting latex in editorials, Hope you will like it :)
Editorials:
Gopu and Frogs:
If you have not come across permanent problem, Then look at
http://en.wikipedia.org/wiki/Permanent. As might you read permanent can used to find number of perfect matchings in a graph. Now you have to find perfect matchings in this case too, but in this case, you select an edge by some probability. So you just add this constraints to the problem.
For finding number of perfect matchings in a graph, you can use a dp with bitmask in O($2^n n$).
See the code of
http://www.codechef.com/viewplaintext/460759 of uwi. go to permanent section.
Problems to solve:
http://www.codechef.com//problems/IOPC1114. You can also see its explanation by Raziman TV on
http://razimantv.files.wordpress.com/2011/02/booklet1.pdf.
Arrangement Validity:
From the earlier arrangement validity problem in the first part, you might have
known the condition of when the answer is not possible. Go solve the problem for more clarity
http://www.spoj.com/problems/SPCU/.
Now how to build a correct order. (Exercise) You can prove that if answer exists then it is unique. Go from right to left, Suppose what is the height of last person you can have is smallest positive integer which is not equal to a[n - 1]. eg in case of last person having a[i] = 2, You can have height = 1. in case of 1, you can have 2.
So on generalizing this, you are on the $i^{th}$ from back and you want to know its height, You have to answer queries like this. Find smallest positive integer which is not equal to any of the values from a[i + 1] to a[n - 1]. You can use segment tree or BIT for this kind of queries.
Try solving
http://www.spoj.com/problems/ORDERSET/ for getting more insight into the solution.
Maggu and Weird Things.
This problem is really lovely problem. You can use matrix exponentiation to solve this problem. Hints of constraints being n $\leq$ 50 and m $ \leq 10^9$.
Basically each transformation can be characterized by a matrix multiplication. For doing the first operation, you can create matrix really easily. First try creating matrix for only operation 1, Take simple test cases, You will notice the pattern very fast.
See the marix for only operation 1, Assume n = 4, k = 2
$ \\[ \\left( \\begin{array}{ccc}
1 & -1 & 0 & 0 \\\\
0 & 1 & -1 & 0\\\\
0 & 0 & 1 & -1 \\\\
-1 & 0 & 0 & 1\\\\
\\end{array} \\right)\\] $
Did you guys notice the pattern, if yes, then formalize the intuition.
Now let us see the case of swapping the $i^{th}$ and $(i+1)^{th}$ element.
For this you can swap two consecutive rows of matrix obtained in the first step.
ie.
$ \[ \left( \begin{array}{ccc}
0 & 1 & -1 & 0\\
1 & -1 & 0 & 0 \\
-1 & 0 & 0 & 1\\
0 & 0 & 1 & -1 \\
\end{array} \right)\] $
Now you have got your matrix, Exponentiate it n times ($\mathbb{O}$ ($n^3$ log m) and enjoy yourselves :)
Maggu and Magguness Level:
This problem is so cute to solve. Believe me if you have not solved upto now, first solve yourself.
First let us detect when answer will be -1, When there exists cycles in the graph, You will get contradictions and hence will be -1. eg 1-> 2 and 2 -> 3 and 3 -> 1 is not possible.
Now for first find the vertices which are connected to the vertex id in the graph. Also find the number of vertices which are connected to it in the reverse graph. Call the first number A and second number B. Then the answer to the problem should be all the number from B to N - A + 1.
Take examples and try solving the problem.
Petya and Repairment of Roads.
This problem is really famous. See
http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf.
This book is really a gem book. See its exercise 3.2, Our problem is similar to this. Now use the hint provided in book and solve the problem.
Also solve
http://www.codechef.com/problems/RHOUSE.
Maggu and Mystery:
In simplified language problem is to find min no of operations needed to do on a array to get atleast d distinct elements. In a single operations you can increase or decrease the $i^{th}$ element by atmost $v_i$.
Solution is to use min-cost max flow. Note that it wont make any sense to convert a number into less than -250 (As n $\leq$ 50 and $v_i$ $\leq$ 5) and greater than 1250. So a make a graph of n nodes on one side and 1250 + 250 nodes on the other sides. For each edge add the capacity of 1 and cost equal to $ceil (abs (a_i - j), v_i$. You need to add two special vertices, start and target vertices. Connect first n vertices to start vertex using 1 cap and 0 cost. and similarly connect the target vertex to all the $j^{th}$ vertices (ie vertices on the second part).
Maggu and Vectors : (Wrriten by Abhilash Kumar)
In this problem we have to check that do 3 vectors a,b,c exists such that :
abc=0
Because we have assumed vectors to as non-directional like a simple line segment which can be shifted along x and y axes but its orientation cannot be altered.
It can be easily noticed that solution to above equation exists if solution for one of these equation exists:
a+b=c
b+c=a
c+a=b
As the x and y components lie between -1000 and 1000 we can simply precompute sum of each pair of vectors and store in an 2-D array of bool of size 4000*4000 which denotes that is sum of two vectors equals to that index exists or not(as we can not have negative indexes we can simply shift origin by 2000 to take care of it). And later check for each vector that do we have a sum of which equals of this vector.If any vector satisfy this then we have a solution else no.
Complexity = $\mathbb{O} ( 4000*4000 + n^2 + n )$
Note: Many wrong answer occurred because people were also counting non-degenerate triangle.
To avoid this problem we just had to add only non-zero vectors that were non-parallel .
Maggu and Triangles : (Written by Abhilash Kumar)
We have to find number of non-congruent triangles with perimeter N.
The answer to this question is Alcuin's sequence Nth element of this sequence is coefficient of $x^n$ in $x^3/((1-x^2)*(1-x^3)*(1-x^4))$.
$T_n = < (n+3)^2 / 48 > $ when n is odd.
= $ < n^2 / 48> $ if n is even.
where $ < > $ denotes the nearest integer to x . Note that here x will never be exactly between two integers.
A Cross Product Formula
\[\mathbf{V}_1 \times \mathbf{V}_2 = \begin{vmatrix}
\mathbf{i} & \mathbf{j} & \mathbf{k} \\
\frac{\partial X}{\partial u} & \frac{\partial Y}{\partial u} & 0 \\
\frac{\partial X}{\partial v} & \frac{\partial Y}{\partial v} & 0
\end{vmatrix} \]
