I remember such a bug: when comments are removed by admins, comment counter is not updated properly. This is not just you, I also don't see other comments here.

probably admins decided to hide those comments because gcj quali is still running. If there were hints in those comments that makes sense.

There was 1 root comment and comments to it. Probably the root comment was deleted and so others are not displayed too.

I think, before this, they check that r*c%x == 0

If you have a large number of copies of the initial string (in particular, 42 is big enough) then in one of the three parts you must have a substring in the form SSSS for some S. But any quaternion raised to the power of 4 returns 1, so we can remove that string from this part. Therefore, if X is sufficiently large, we can subtract 4 from it and get the same result. So what tourist is doing here is changing X to the smallest number above 42 that is the same as X nor 4.

Observe that anything ^ 4 = 1. Therefore each part is would not be longer than 4 repeats.

During the round I used 12 as the magic number but I also tested 4 on the small and large-practice and it is also correct.

if (x > 4) {
  x = 4 + x % 4;
}

btw, seems 5 is enough (at least for my test data).

My sad story:

I though 8 is enough (because their are 1,i,j,k,-1,-i,-j,-k). But when I downloaded the data, I was gready: oh what if my proof(guess) is wrong, let's use 16, if it is too slow then change back to 8. And that is super fast, I'm very happy and submitted.

But it failed because the size of array is not enough when I change 8 into 16. >_<

Lesson: don't make stupid decision after download test data..

How about 6 3 12? I caught 5 3 5 and 6 3 6 but not 6 3 12.

D looked really weird until I found this in the sample pictures for X=7 :)

OOO

O..O

OO

For me, it was 5 3 10, 5 3 15, and 5 3 20 instead — quite similar but from the other side.

I'm the victim of 5 3 5, staircase was a killer.

How do you get that ceil((Pi — X) / X) special minutes would be needed? Can you please provide a short proof or intuition?

I used a O(10^9) dp state calculation to calculate this ceil((Pi-X) / X). I cannot think why it is like that. Can you prove it?

There is: http://www.go-hero.net/jam/15/regions

And: http://a2oj.com/CodeJamTools/Results.jsp

You can notice that any signed letter ^4 equals to 1. So we may have periodicity when X > 4. Maybe we can use that to do less processing. If X <= 4 we can just solve it as if we were dealing with small case: one approach is to find first occurrence of i, a later occurrence of i*j and check if the whole multiplication is i*j*k.

Lets split the given string |S| = L in pieces by its periods. If X > 4 we have to consider that even if ij occurs before i in the first piece, it may occur in the second piece after i. We could process 'til 4*L and check if i and ij occurs somewhere. But it does not guarantee us that there will be a i before a ij in the given multiplication. We could have X = 6 with ij occuring in the last part of S and i occuring right after it. Then we would not have i before ij even if the string is periodic, because it wasn't periodic at all (we had a single complete period and an incomplete period). But if we assume we have two complete periods, this logic will work.

So we process as if we were dealing with small cases for X <= 8 (at most two complete periods) and process splitting string in pieces for X > 8.

I didn't come up with idea that fourth power gives one for any letter so my idea for this problem was slightly different, though I decided not to implement it and go sleep instead. The idea is that you can greedily find left and right pieces (the shortest prefix which gives 'i' and longest suffix which gives 'k'). Then all you need to check is whether the string between them gives 'j' and I was going to do that using something similar to binary exponentiation.

222
223
333
113
411
441
445
555
566
666

****##^^^^
xxx*@##%%^
xx@@@@#%%%

EDIT: sniped...why does delete button still show if it can't be deleted anymore?

If it is harder then it is harder for everyone, so I don't think it is something that affects just you, but rather all of us.

Fast exponentiation is not really needed, as only X % 4 matters.

Regarding problem D. I'm surprised that even tourist used "manual" if-if-if-if approach. My "algorithmic" solution is similar to yours one, but without brute force for Gabriel. So,

1. Generate all the possbile figures
2. Iterate through all the figures
3. To check, whether it is possible to use selected figure — iterate through all possible positions for this figure on the grid
4. If for some position the grid is divided to connected components with sizes X*K, the figure is "solvable". Do not try to split the grid using brute force — just believe, that it is possible :)
5. If there is an "unsolvable" figure, Richards wins, otherwise — Gabriel wins

I didn't strictly prove statement 4 (I didn't even try, since didn't have paper and pen :D ), but it seems that it may be incorrect only for significantly larger sizes than 6 (I expect problems starting from sizes about 14-16)

So the solution is O(number_of_figures * (R*C)^2)

enta Prince :D

int temp=v[0]/2

This is not optimal. Test:

1
1 
9

Ans 5: 9 -> 3 + 6 -> 3 + 3 + 3 -> 2 + 2 + 2 -> 1 + 1 + 1 -> 0

It'll definitely be up before the next round.

"If a connected blank area of size M is a multiple of X, it can be guaranteed that there is a way to place M/X X-ominoes to fill in the blank area."

Isn't this what fram just showed a counterexample to? First solution to D seems bogus to me.

(If they meant that this case doesn't matter according to case-by-case analysis, then why bother coding a brute force if you already went through the whole case analysis to prove it correct?)

ETA: A way to fix this would be to do what misof suggested and actually check the placements of the other X-ominoes as well in the brute force.