August 2011 Contest Problem Editorials

 

 

Problem Tester for the August 2011 contest was Shilp Gupta.

-------------------------------------------------------------------------------------------------------

BLOCKDRO (written by Ivan Mistreanu)

 

This problem is an exercise in BFS/DFS. The main point here seems to be how to encode the state so that the search to be fast enough. The author’s approach is as follows. There are not more than 25 stones. We sill keep the mask of which stones are left of the board. And we should add the number of the stone we are standing on to the state. So we have at most 25*2^25 states which surely too much, but actually many of the states are going to be inaccessible even in the worst case (also some of the states reachable from the initial state will be unsolvable and can be removed from the search). However we should still try to make the search as fast as possible. For each state we can move to at most 8 other states. In order to make calculation possible move fast for each stack of stones we will keep the number of the first stone on the stack and also for each move the number of the stack this moves lands on or -1 in the move is illegal for the stack. Also for each stone we will keep the number of the stone under it in the stack or -1 if it’s the last stone in the stack and the number of the stack this stone belongs to. Using this information the each state can be resolved rather fast. So now BFS can be used to solve the problem. Since the number of moves to reach any state in fixed DFS can be used as well.

Several optimizations can be applied in this problem. For example we can keep the number of stack instead of the number of stone we are on. Having that the test cases are random the amount of stacks should be lesser than the amount of stones. We can determine unsolvable states and remove them from the search. Since we know the final state – meet in the middle approach can be used for some additional time win. Seems that dynamic programming can be also used in this problem.

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

COMPLEXT (written by Vishal Anand)

 

Will be updated soon

 

You can view solutions here:

Problem Tester Solution

-------------------------------------------------------

DIVISORS (written by Anton Lunyov)

 

You can view the above image in PDF format here: http://www.codechef.com/download/Solutions/2011/August/DIVISORS_pdf.pdf

 

You can view solutions here:

Problem Setter Solution

Optimized Solution

-------------------------------------------------------

HPARITY (written by Abdullah Mahmud)

 

Lucas' Theorem: http://en.wikipedia.org/wiki/Lucas%27_theorem

You can view the above image from here.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

IGAME (written by Snigdha Chandan)

 

The strategy of the game revolves around "LOSS" positions and "WIN" positions.In a "LOSS" position ,the player whose turn it is to move will lose with best play,while in a "WIN" position ,the player whose turn it is to move will win with best play.The optimal strategy from a "WIN" position is to move to any reachable "Loss" psition.

The classification of positions into "WIN" and "LOSS" can be carried out recursively with the following 4 rules:

Rule-1:(0,0) is the "TARGET" position.

Rule-2:Any position from which the "TARGET" position can be reached in a single move is a "WIN" position.

Rule-3:If every move from a particular position leads to a "WIN" position ,then that position is a "LOSS" position.

Rule-4:Any position from which the "LOSS" position can be reached in a single move is a"WIN" position.

Pre-processing step:Now following the rules of the game along with the above 4 rules the cells in a 1000X1000 matrix can be filled up as either "WIN" or "LOSS" for the first player ,i.e ALICE.

Solving the Problem:

Step-1:The actual target position (p,q) is shifted to the origin.

Step-2:Now the initial position (m,n) has also been accordingly changed and comparing the new initial position with the corresponding cell in the pre-processed matrix the winner can be decided.

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

SHORTCIR (written by Ivan Mistreanu)

 

The solution can be described in several not really hard steps:

1. Let us build a syntax tree for the expression with AND, OR, NOT as inner nodes and variables as leaves. Respect the standard priority of the operation when building the tree. However associativity doesn’t matter for the sake of this problem. Right away we can define P(V) for each node meaning the probability that this node will return true.

2. Now we remove all NOTs from the tree using the following rules:

a. NOT (NOT (E)) = E.

b. NOT (AND (E1, E2)) = OR (NOT (E1), NOT (E2)).

c. NOT (OR (E1, E2)) = AND (NOT (E1), NOT (E2)).

d. NOT (V) = U, where V and U are variables (U is a new variable), having P(U) = 1 – P(V). Using this rule is correct, because all the variables are different.

3. So after step 2 we have a tree with only AND and OR as inner node. Now we consider those operations to accept more than two operands and merge the nodes of the tree in the following way: AND(E1, AND(E2, E3)) = AND(E1, E2, E3), OR(E1, OR(E2, E3)) = OR(E1, E2, E3).

4. After step 3 we will end up with AND/OR tree: any child of AND node will be a variable or an OR node, and any child of OR node – a variable or an AND node. For such a tree we can recursively calculate the expected amount of evaluations needed to result this node. The best order of evaluation of children can be derived for each node. The answer is the expected amount of evaluations for the root.

For the best order of evaluations for some inner node let us consider the following node: X = AND(E1, E2, …, En). If we fix any order of evaluations of children: F1, F2, .. Fn. Then the expected number of evaluations will be: M(X) = M(F1) + P(F1)*(M(F2) + P(F2)*(M(F3) + …)). Let’s look at any two children. If we place Fi before Fj we get

[… + M(Fi) + P(Fi)*(… M(Fj) …)],

otherwise we get

[… + M(Fj) + P(Fj)*(… M(Fi) …)].

So the lesser is the value of this part the better is the order. We have:

M(Fi) + P(Fi)*M(Fj) ? M(Fj) + P(Fj)*M(Fj)

M(Fi)*(1 – P(Fj)) ? M(Fj)*(1 – P(Fi))

M(Fi)/(1 – P(Fi)) ? M(Fj)/(1 – P(Fj))

That means that in this case we should sort the children by M(E)/(1 – P(E)) to get the best order of evaluations. Similarly can be done for OR nodes.

However such approach turns to produce optimal solutions only for certain types of and/or trees. For example, for and/or trees of depths no more than two.

Additional information can be found in this paper: http://www.cs.toronto.edu/~molloy/webpapers/aotree.ps

 

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

Comments

Some really interesting

gultus @ 12 Aug 2011 05:07 PM
Some really interesting questions this time around. I was so close for a solution for HPARITY and SHORTCIR. Instead of wasting my weekend I should have tried to solved these problems somehow.

I was seeing some interesting

gultus @ 12 Aug 2011 05:16 PM
I was seeing some interesting patterns in the solution for IGAME and I searched on internet and found out it is same as Wythoff's game http://en.wikipedia.org/wiki/Wythoff's_game Infact the problem setters solution seems to be based on closed form representation for the losing positions.

@gultus: Yeah, I solved IGAME

tendua @ 12 Aug 2011 05:38 PM
@gultus: Yeah, I solved IGAME with Wythoff's game. I had to do only shifting of origin to the starting point. Rest of the coordinates were already defined by sequences.

@gultus::In fact the solution

ritesh_gupta @ 12 Aug 2011 06:13 PM
@gultus::In fact the solution (Cold position ie. the points in which Bob wins ) of IGame and Wythoff's game is exactly same.Even I implemented Whytofs game concept

divisors solution absolutely

cool_prabhjot @ 12 Aug 2011 06:14 PM
divisors solution absolutely not understandeable, please arrange a healthy copy of this. I am deliberately looking for this. THX !

Some of these problems were

lg5293 @ 12 Aug 2011 08:58 PM
Some of these problems were similar to problems in other recent programming competitions: IGAME - April 2011, USACO silver division, cowcheckers - http://ace.delos.com/TESTDATA/OPEN11.cowcheck.htm (there is a different ending point, but a simple shift in coordinates fixes that) COMPLEXT - July 2011, Online BOI round, timeismoney - http://www.boi2011.ro/resurse/tasks/timeismoney.pdf (the evaluation function is different, but the concept is similar) Other than that, I thought the problems were average. BLOCKDRO is just a simple extension of testing your ability to optimize a DFS/BFS, but I thought it would be more complicated, so I didn't really do much work with it. SHORTCIR seemed interesting, but I didn't like that last minute change. I didn't really have that much time yesterday to react to it. DIVISORS was too difficult for me to approach, and the editorial isn't really helping. Anyways, can anyone help me with HPARITY? I was getting TLE (just 1 second over time limit on my computer). Here's my solution: http://www.codechef.com/viewsolution/624014 Basically, I do inclusion/exclusion, and then I take the highest power of two less then the maximum coordinate, call it p, and split the plane into 2^n regions so there are 2^n hypercubes of length p all contained in a bigger hypercube of length 2*p. Then, just based on the rules for generating the cells, it'll be a fractal, so if you imagine the hypercube with the origin pointing upwards, we only need the check the (n+1) topmost regions (this is hard to visualize, but that's the key to getting my solution). Then, we just recursively go into those regions, reducing x_i when needed. I use a hashmap to reduce redundant calculations. My question is, will this approach even work? And if it will, how do I optimize my code further? I will agree though that the editorial's solution looks nice, but relies on prior knowledge of lucas's theorem. This approach only relies on simple pattern spotting. Thanks in advance.

Please provide a full

javadecoder @ 12 Aug 2011 09:16 PM
Please provide a full explanation for HPARITY,as I could not understand a "bit" of it.How do we get that the for black cells,that multinomial should be odd? After that how to solve it using inclusion exclusion....somebody please explain

Just commenting on the

pragrame @ 12 Aug 2011 09:19 PM
Just commenting on the solution to ShortCir: "For the best order of evaluations for some inner node let us consider the following node: X = AND(E1, E2, …, En). If we fix any order of evaluations of children: F1, F2, .. Fn." My doubt is, how do we know that we optimally we would need to solve F1 completely before solving F2? I mean, intuitively, it seems ok after the entire machinery of first removing NOT, then grouping all the ands and all the ors into a single node etc, but are we sure this'll work? I mean, without the assumption of having (a or(b or c) ) clubbed into Or(a, b, c); i.e. consider Or(a, Or(b,c)) we would not need to completely solve Or(b,c) to get the best answer for Or(a, Or(b, c)). I mean, what exactly is hidden in the previous steps that is supposed to ensure that this approach works? -not quite convinced...

@javadecoder, look at it this

pragrame @ 12 Aug 2011 09:28 PM
@javadecoder, look at it this way. i claim that a cell (x1, x2, ..., xn) is coloured black iff "the number of routes from the origin to the cell is odd" where you are allowed to go only through an increase of coordinates' values. Prove by induction on distance of cell from origin i.e. summation xi. for the origin, the distance is 0, and there is only 1 route (origin itself) trivially. Then assuming that it holds for all cells whose distance < k, consider a cell whose distance = k. If it is black, then it has an odd number of (k-1)-distance cells which have an odd number of routes to it. So the total number of routes to the k-distant cell will be odd. If it is white, then it has an even number of (k-1)-distance cells which have an odd number of route to it. So the total number of routes to the k-distance cell = even*odd + remaining*even = even. Finally, see that the number of routes from the origin to a cell (x1, x2, ..., xn) = the multinomial coefficient (summation xi, choose x1,x2,x3,..,xn)).

@Snigdha Chandan can u

rijin @ 12 Aug 2011 09:47 PM
@Snigdha Chandan can u explain abt igame solution; i little confused abt that; about ur solution line int((m-n)*(1+sqrt(5.0))/2+eps)

@rijin:http://en.wikipedia.or

snigdha_adm @ 12 Aug 2011 10:40 PM
@rijin:http://en.wikipedia.org/wiki/Wythoff's_game

@pagrame As they mentioned at

snapdragon @ 13 Aug 2011 04:17 AM
@pagrame As they mentioned at the end of the SHORTCIR writeup, you're right to be doubtful! The linked paper mentions that the DFS solution does NOT, in general, find the optimal linear strategy, meaning that there are cases where you'd want to solve F1 partially, then F2, etc. I imagine that's why they changed the problem specification near the end of the contest. During the contest I only convinced myself it was true with a hand-wavy argument... making the same mistake as the authors. :) Here's a good extreme example: P(a) = 0.7, P(f*) = 0.01, P(t*) = 0.99. The DFS gives a cost of 2.068723 for "a and ((fa and ta and tb and tc) or (fb and td and te and tf))". Note that fa and fb are very likely to be enough to solve the formula on their own, but if they're not (ie, one or both are true), we'll want to try a next. We can prove this by observing that the DFS gives a cost of 3.140820 for "a and ((ta and tb and tc) or (td and te and tf))". If either of them is true, at worst we'll have to solve this second formula (in fact, usually one of the subtrees will already be pruned). So there's a linear strategy starting with fa and fb with cost at most 2 + 0.0199 * 3.140820 = 2.062502, better than what the DFS returns for the original formula.

@Snigdha not about problem;

rijin @ 13 Aug 2011 10:47 AM
@Snigdha not about problem; doubt in ur solution; wot value is generated here?

@admin: I think all these

sherwin21990 @ 13 Aug 2011 12:22 PM
@admin: I think all these editorials require more elaborate explanations.

@admin: I think all these

sherwin21990 @ 13 Aug 2011 12:22 PM
@admin: I think all these editorials require more elaborate explanations.

For the Infinite Grid Game,

ambujpandey @ 13 Aug 2011 09:33 PM
For the Infinite Grid Game, refer to the tutorial on Game Theory on Codechef. I could solve it just by going through it. http://www.codechef.com/wiki/tutorial-game-theory

my answer for igame was

naveennitk2009 @ 14 Aug 2011 12:00 AM
my answer for igame was perfectly right but the codechef compiler showd my answer to be wrong!!!! why???

@javacoder multinomical

nokia @ 14 Aug 2011 12:13 AM
@javacoder multinomical coefficient can be written as follows: let T = M1+M2+..+Mn and C(n,r) = n!/((n-r)! * r!) C(T, M1) * C(T-M1,M2) * C(T-M1-M2,M3) * ...*C(Mn,Mn) so multinomial coefficient to be even we need (C(T, M1) * C(T-M1,M2) * C(T-M1-M2,M3) * ...*C(Mn,Mn))%2 = 0 Now consider the case: C(Mn-1+Mn, Mn-1)%2 = 0 let A = Mn-1+Mn and B = Mn-1 and D = Mn A = (ak,.....,a3,a2,a1,a0) is the binary representation of A B = (bk,.....,b3,b2,b1,b0) is the binary representation of B D = (dk......,d3,d2,d1,d0) is the binary representation of C from the lucas theorem. http://en.wikipedia.org/wiki/Lucas%27_theorem ***A binomial coefficient C(m,n) is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m. we can say if bi > ai then C(A,B)%2 is 0 and bi > ai if and only if bi = 1 and ai = 0 let i be the smallest bit position where bi = 1 and ai = 0. As ai = 0 ,we can say di = 1 because A = B + D we have (bi + di)%2 = ai as i is the smallest bit position there is no carry in addition Now we can say that. If there is two Mi and Mj which shares a 1 in the same bit positon then the multinomial is divisible by 0. we can arrange (M1,M2,..,Mn) so that Mi = (n-1)th term and Mj = nth term.

So, who is the writer of

mmaxio @ 14 Aug 2011 04:26 AM
So, who is the writer of SHORTCIR?

Also, wouldn't it be better

mmaxio @ 14 Aug 2011 04:31 AM
Also, wouldn't it be better if these pics-editorials will be provided as simple pdf-file? Or maybe you can even add all editorials in one file and then release it. Current pictures look terrible with this loss of quality IMO.

@mmaxio Try to increase the

anton_adm @ 15 Aug 2011 04:07 AM
@mmaxio Try to increase the scale of the page. This improves readabilty of editorial for DIVISORS well enough. I have asked admins to add link to the pdf-file but there is still no response from them.

Hey Guys, The PDF can be

admin @ 16 Aug 2011 03:13 PM

Hey Guys,

The PDF can be found here: http://www.codechef.com/download/Solutions/August/DIVISORS_pdf.pdf

When will COMPLEXT be

theluy @ 18 Aug 2011 09:23 PM
When will COMPLEXT be updated? I am really interested in the solution.

I can describe how my optimal

snapdragon @ 19 Aug 2011 02:22 AM
I can describe how my optimal COMPLEXT algorithm works. It's a pretty cool algorithm. Basically, imagine you pick some direction (represent it by a unit vector V) in the plane and decide that (instead of maximizing magnitude) you just want to maximize how far you go along that vector. This new optimization problem is just a normal 1-dimensional MST, with edge weights formed from the projection of each edge's vector onto V. Pretty simple. Now, note that if you happen to have picked the direction of the true optimal solution's sum, you will end up with that optimal solution (obviously!). So the problem is now reduced to looking at all possible MSTs that can be formed from choices of direction V. At this point, you can probably do pretty well with some sort of hill-climbing, by finding good choices of V and then searching around them. I imagine this is how a lot people got good scores. But upon closer examination, we realize we can search ALL possible MSTs formed from choices of V in a reasonable amount of time. Pick an initial V and sort the edges by their projections along V (in preparation for Kruskal's algorithm). Run Kruskal's and get a candidate MST. Now, if you rotate V a little, when can Kruskal's selections change? Exactly when two edges in the sorted list swap position. For each pair of edges with distinct weights, this will happen twice as V goes around the complete circle - both times when V is orthogonal to the line joining the two edge vectors. Thus, we can sweep V around in a complete circle, and simply re-run Kruskal's each of the O(E^2) times two edges swap position. This will be sure to find the true optimal solution, as it will be one of the candidate MSTs. We can do even better than a full Kruskal's at each swap, though. Note that we can ensure we only ever swap adjacent edges in the list (it gets a bit tricky when multiple swaps happen at once, and with edges with equal weights, but it's still possible with clever ordering). But it's pretty easy to describe how Kruskal's selections change when two adjacent edges swap priorities! The only change that can happen is if the better edge was selected, the worse edge wasn't, and the better edge prevented the worse edge from being selected. This only happens when both edges potentially connect the same components. And the only effect on the final MST will be to toggle which of the two edges was chosen. So rather than re-running Kruskal's, we have a simple adjacent swap test: if the top edge is in the MST, the bottom edge isn't, and if the cycle formed by adding the bottom edge goes through the top edge, then remove the top edge from the MST and add the bottom edge. There's probably an efficient way to test this, but in my solution I just do an O(E) DFS, and it's fast enough (since most swaps don't satisfy the first two conditions anyway).

@snapdragon: Thanks, that's

theluy @ 19 Aug 2011 06:31 PM
@snapdragon: Thanks, that's great!

@admin, The next contest is

tijoforyou @ 29 Aug 2011 03:26 PM
@admin, The next contest is abt to start... Please update COMPLEXT...