You need to get 20 points in order to advance to Round 1.

• +66

 » 6 years ago, # | ← Rev. 2 →   +54 I can't see the comments. Is it a bug, or a feature?EDIT: I can see this comment, but I can't see other user's comments. I can see comments normally on other blogs.
•  » » 6 years ago, # ^ |   +23 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 probably admins decided to hide those comments because gcj quali is still running. If there were hints in those comments that makes sense.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +17 There was 1 root comment and comments to it. Probably the root comment was deleted and so others are not displayed too.
 » 6 years ago, # | ← Rev. 2 →   +3 please someone explaine me how you can put the 4 shape in line 2 in 3*6 grid(for example) http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/All_18_Pentominoes.svg/220px-All_18_Pentominoes.svg.pngbecause a lot of solutions like eatmore solution he put case 5: gabriel = min(r, c) >= 4 || (min(r, c) == 3 && max(r, c) > 5);
•  » » 6 years ago, # ^ |   +4 I think, before this, they check that r*c%x == 0
•  » » » 6 years ago, # ^ |   0 oh i write it at the begining but that case 3 5 3 killed me . thanks for ur reply
 » 6 years ago, # |   -25 Who else missed the word 'at least' in D problem statement ("Gabriel must use at least one copy of that X-omino")
 » 6 years ago, # |   +6 In Dijkstra, tourist has performed this step: const int MAGIC = 42; if (X > MAGIC) { X -= (X - MAGIC) / 4 * 4; } Can someone please explain why the reasoning behind this step?
•  » » 6 years ago, # ^ |   +11 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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; } 
•  » » 6 years ago, # ^ |   +65 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. >_
•  » » » 6 years ago, # ^ |   +11 Similar mistake. I didn't initialize the array properly after increasing the number of repetition. :'(
•  » » » 6 years ago, # ^ |   0 I missed the big case of C only because I forgot to transform to long long a single variable !!! So, you're not the only one :')
•  » » » » 6 years ago, # ^ |   +61 I used Rust for the first time in this contest. I made the very same mistake, and Rust caught it for me. Success! :)
•  » » » » 6 years ago, # ^ |   +3 Input validation saved me) assert(read()); // ... if (!(cin >> n >> k)) return false; // ... 
•  » » » 6 years ago, # ^ |   0 Lesson: Use a memory safe programming language...
 » 6 years ago, # |   +28 How many people failed this testcase for D: 5 3 5?
•  » » 6 years ago, # ^ |   +14 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 :)OOOO..OOO
•  » » » 6 years ago, # ^ |   0 For x==6 I just checked r*c%x==0 and min(r,c)>3
•  » » » 6 years ago, # ^ |   +8 Similar. Cool problem :)
•  » » 6 years ago, # ^ |   0 For me, it was 5 3 10, 5 3 15, and 5 3 20 instead — quite similar but from the other side.
•  » » 6 years ago, # ^ |   +5 I'm the victim of 5 3 5, staircase was a killer.
 » 6 years ago, # |   +14 Solution for BObserve that the optimal solution is always: distribute pancakes to empty plates using special minutes, such that everyone has at most X pancakes. Then spend X minutes to eat those pancakes.Let's brute force X from 1 to 1000. In each try, if a person i has more than X pancakes, we would need ceil((Pi - X) / X) extra special minutes to distribute pancakes. Sum up those special minutes and add X eating minutes, that would be the total time. Output the minimum of such total time in all X.ceil((Pi - X) / X) can be rewritten as (Pi - X + X - 1) / X = (Pi - 1) / X.
•  » » 6 years ago, # ^ |   0 How do you get that ceil((Pi — X) / X) special minutes would be needed? Can you please provide a short proof or intuition?
•  » » » 6 years ago, # ^ |   0 Let's say someone has 11 pancakes, and you want everyone to have 3 or fewer pancakes. You will need 3 minutes to give 3 pancakes to empty plate A, give 3 pancakes to empty plate B, and 2 pancake to empty plate C.The number of extra plates = number of extra special minutes required can be calculated using that formula.
•  » » » » 6 years ago, # ^ |   0 Yes, I understood that. What I am asking is, how do we reach that formula?Can we say that.. Pi = X + k, for some k    = n*X + c, for some c < X Hence, n = (Pi — c) / X
•  » » » » » 6 years ago, # ^ |   0 Actually we want the smallest n such that Pi <= n*XOr we can say Pi = n*X + c where -X < C <= 0There are many implementations that does not make use of the floating point ceil() function n = Pi / X; if (Pi % X != 0) { n++; } 
•  » » » » » » 6 years ago, # ^ |   0 Can you give me example of input1 2 5 9 11 7
•  » » » » » » » 6 years ago, # ^ |   +11  Eating Special Total X = 1 0+1+4+8+10+6 30 X = 2 0+0+2+4+5+3 16 X = 3 0+0+1+2+3+2 11 X = 4 0+0+1+2+2+1 10 X = 5 0+0+0+1+2+1 9 X = 6 0+0+0+1+1+1 9 X = 7 0+0+0+1+1+0 9 X = 8 0+0+0+1+1+0 10 X = 9 0+0+0+0+1+0 10 X = 10 0+0+0+0+1+0 11 X = 11 0+0+0+0+0+0 11 
•  » » » » » » » » 6 years ago, # ^ |   +1 Okay so what I understand with this is, we are actually trying to covert array elements to less then or equal to a particular number (changing every time from 1 to 1000 in our question) using special minute and then reducing that number from array to make it 0 using normal minute and then the answer will be normal minute + special minute
•  » » » » » » » » » 6 years ago, # ^ |   0 Correct
•  » » 6 years ago, # ^ |   0 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?
•  » » » 6 years ago, # ^ |   0 You would not move pancakes from one non-empty plate to another non-empty plate. You would always move them to new people. The number of moves required for each non-empty plate is therefore independent.Since we are exhausting X, (fixing maximum remaining number of pancakes each person has), we can always obtain the best answer.An example would be 1 person having 9 pancakes. The calculations are:  Eating Special Total X = 1 8 9 X = 2 4 6 X = 3 2 5 X = 4 2 6 X = 5 1 6 X = 6 1 7 X = 7 1 8 X = 8 1 9 X = 9 0 9 
•  » » » » 6 years ago, # ^ |   0 Actually My doubt was why/how ceil(P[i]-x)/x ?
•  » » » » » 6 years ago, # ^ |   0 I have explained in another comment above.
•  » » 6 years ago, # ^ |   0 Could you somehow show how is this always optimal? "distribute pancakes to empty plates using special minutes, such that everyone has at most X pancakes. Then spend X minutes to eat those pancakes." Thankyou :)
 » 6 years ago, # |   0 Is there any way to filter standings by country?
•  » » 6 years ago, # ^ |   +7
•  » » 6 years ago, # ^ |   +3
 » 6 years ago, # |   0 how to solve large input version of Dijkstra problem ?
•  » » 6 years ago, # ^ | ← Rev. 5 →   0 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.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +10 So, you just decided to ignore the large case? You still need some good bounds on the lengths of prefix and suffix, otherwise you'll be looking for entire string on this input: 1 1000000000000 j 
•  » » » » 6 years ago, # ^ |   +8 No, of course you you don't iterate the entire string million of times, 8 times is enough, if you didn't run into 'i' then you may safely assume there will be no prefix which will give you 'i'. I thought that this shortcut is obvious so didn't mention it.
•  » » » » » 6 years ago, # ^ |   0 I didn't notice the fourth power thing and implemented this too. A cute way to get rid of this case is simply: if (X > 30) X = 30; (for the exponentiation part, use full value of X)
•  » » » » » 6 years ago, # ^ |   0 ... and since you know there's 8L period, you could reduce X in the same way but with eights instead of fours. I just said, that absence of idea about fourth powers doesn't justify the approach.
•  » » » » » » 6 years ago, # ^ |   +8 Nope, that's different. I said that if you didn't reach 'i' in first 8L letter then you won't reach it in the entire string. It's not a period, it's just an upper bound. The reason for that is the periodicity of course but the actual period was unknown to me (though of course I could calculate it for a given string) and the actual value of that period didn't matter.
•  » » » » » » » 6 years ago, # ^ |   0 actually 4L is one of periods becausex^4 = 1 for any x in {+-}{1,i,j,k}
•  » » » » » » » » 6 years ago, # ^ |   +19 Eh, I started this conversation mentioning that I didn't know that fact about 4L period during the contest. Of course I know that now after reading all the comments above.
•  » » » 6 years ago, # ^ |   +8 For the right piece you can also search for the shortest suffix. Or search for the shortest piece for 'j' after the shortest piece for 'i' and check if the rest of the string is 'k'. (that's what I did and also with fast exponentiation but then replaces fast exponentiation with X % 4 trick).
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 True, checking 'i' and 'j' seems even better than checking 'i' and 'k' because you will need to "cut" the remaining piece only from one side to be a copy of multiple original strings. Reread my comment and you're right, I meant shortest suffix as well. Both of them should be shortest to make things easy. Thanks.
•  » » » » » 6 years ago, # ^ |   +5 Instead of looking for suffixes you can also loop only through the prefixes. Just need to find the first occurrence of i, the last occurrence of i * j and check if the former starts before the latter.
•  » » » 6 years ago, # ^ |   +30 Did the same thing, except for the last step, you could check that the total product was -1.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 My approach was to find the shortest prefix that gave 'i' and then the shortest prefix that gave 'ij' within say 10*L, and then check that the total product was -1. That would work too right?
•  » » » » » 6 years ago, # ^ |   0 Right
•  » » » » » 6 years ago, # ^ |   0 I thought there is a need to check all i's, then all respective j's to get the correct answer. Why it is that the shortest prefix ( the first ) that gives 'i' and 'j' will give the right answer ?
•  » » » » » » 6 years ago, # ^ |   0 Imagine there is a solution you missed because you picked the shortest prefix. So, the shortest prefix is A, and the solution is AB. However, since A = i and AB = i, B = 1. Since 1 is a neutral element, you can use the shortest one and attach B to the part giving j instead for another solution. So we can safely use the shortest one.
•  » » » » » » » 6 years ago, # ^ |   0 Thanks
•  » » » 6 years ago, # ^ |   0 I did the same. But only checked prefix/suffix till four copies of the string.
 » 6 years ago, # |   0 Can anyone explain how we can we solve this 5 3 10 when richard chooses this omino ? ## ## # 
•  » » 6 years ago, # ^ |   +5 222 223 333 113 411 441 445 555 566 666 
•  » » » 6 years ago, # ^ |   0 Thanks, missed this case and wrote min(r, c) > 3 in code. :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 ****##^^^^ xxx*@##%%^ xx@@@@#%%% EDIT: sniped...why does delete button still show if it can't be deleted anymore?
•  » » » 6 years ago, # ^ |   0 Thanks.
 » 6 years ago, # |   0 Dont you think that problems this year was harder than lasts year? Personally I scored 37 points,and last year where I knew nothing about competitive programming I scored 55 points. Also I saw some statitics and this year passed much less programmers than last season.I hope Round 1,to be as usual,beucause if it is harder than usual then I have no hopes :P. What do you think guys?
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 Yea you are right,but I am green and you are yellow,so a harder problem is still easy for you,but for me is harder. :) Anyway I didnt say that I had problem with that,I just refered it to see other opinions :)
 » 6 years ago, # | ← Rev. 3 →   +63 My solutions for C+D are fairly different from the mainstream. I guess I didn't like doing casework ;)In C, we can note that the "Dijkstra language" is regular. There is a simple non-deterministic automaton with 24 states that recognizes it. Each state is a tuple (number,quaternion) where number is the segment we are in (0 if we are still reading the part that will reduce to i, 1 for j, 2 for k), and quaternion is one of 1,i,j,k,-1,-i,-j,-k: what the current part reduces to.Easy input: simulate the automaton. Hard input: Simulate the automaton on a single copy of the input string for each starting state, then use fast exponentiation in O(log X) to simulate it on X copies of the string.D: For X >= 7 Richard wins (by using the 7-omino with a hole), otherwise we can just use brute force. For large R,C with RC divisible by X Gabriel will always win anyway and there are plenty of ways to do so ( => our code is fast ) and for small R,C the number of possibilities is small ( => our code is fast again ). The only optimization needed: when simulating Gabriel, make sure you immediately backtrack from unsolvable states -- ones where some connected component of empty cells isn't divisible by X. This is a useful trick in many tiling problems.
•  » » 6 years ago, # ^ |   0 Fast exponentiation is not really needed, as only X % 4 matters.
•  » » » 6 years ago, # ^ |   +8 That's precisely my point. Why bother thinking about whether x%4 works and whether or not there are special cases with that (e.g., is 0 the same as 4?) if you see a solution that is simple to implement and obviously has no special cases?
•  » » » » 6 years ago, # ^ |   0 if(X > 20) X =20+X%4I'm as sure as I care to be at the time I'm solving the problem (what is sleep?) that it works — and it's just one line. I just want to send something — quickly — so that I'd have a peace of mind and sleep. That's one case :D
•  » » » » 6 years ago, # ^ |   0 While I definitely agree with the "don't do thinking that your code can do for you" sentiment, I think that the mainstream solutions for C were the way to go here. They can be summed up as: Check if the whole product is -1 in log(X) time. Run the simple, 5-line, partial sum solution for a constant number of copies. You can make this constant equal to, let's say, 100 without having any problems and it's obvious that it works without doing any detailed analysis on residues. Don't get me wrong, the automaton solution is more insightful and it is beautiful, but I don't think it supports the "keep it simple" argument in this case.One could also argue that a little more (not complicated) analysis can spare you a lot of code in D (although going pen and paper all the way can be risky).
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Well, "simple", just as "beautiful", is in the eye of the beholder :)There is no single right way to go. Each of us has different goals and priorities.(And btw, once you know the product of a single copy of the string, you can easily check whether the whole product is -1 in O(1) time, if you want to. And it's less code again, if you want to go that way.)
•  » » 6 years ago, # ^ |   +6 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, Generate all the possbile figures Iterate through all the figures To check, whether it is possible to use selected figure — iterate through all possible positions for this figure on the grid 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 :) 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)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +147 This is not a valid position, although only one connected component of size 18 needs to be tiled (X=6 on a 4x6 grid): ...... .X.X.. .XXX.. .X.... 
•  » » » » 6 years ago, # ^ |   +32 Good catch!And a good thing that it still does not affect the answer for the problem, since there are always more fortunate placements.Otherwise, most iffy solutions would also fail to catch something as involved as this.
•  » » » 6 years ago, # ^ |   +8 I don't understand why are you surprised that someone used one approach not another one. For me considering all the cases was pretty fun and it's just qualification round, it can be used to have some fun and writing a backtracking solution is definitely not good way to get it :) (typically, I hate casework, but in this problem it was amusing for me :P).
•  » » » » 6 years ago, # ^ |   0 Casework was so boring for me I decided to do small manually (there are only 64 cases after all -- if you reduce symmetry and obvious cases, even less), but the casework for large looked pretty difficult to prove and not really intuitive -- I don't know how to easily eliminate things such as the case fram showed, for instance, or staircases.
•  » » » » » 6 years ago, # ^ |   +3 For large, to do casework, you need some observation like: If you can fill a board of size 3*5 with any 5-ominoes, then you can fill a board of any bigger size R*C (of course R*C is divisible by 5). If you can fill a board of size 3*6 with any 6-ominoes, then you can fill a board of bigger size. After this, for each 5-ominoes, draw 3*5 board that contains it. After this fail for the staircase thing, you don't even need to redo the other 5-ominoes because those 3*5 boards can be easily converted to 4*5. The same applies to 6-ominoes.It took me around an hour to solve 5 & 6. But I think coding + debugging could have taken more time for me.
•  » » » » » 6 years ago, # ^ |   0 I didn't understand, 3 ifs was too much for you, so you decided to solve 64 ifs?
 » 6 years ago, # |   +48
•  » » 6 years ago, # ^ |   0 enta Prince :D
 » 6 years ago, # |   0 My submission for B was judged as incorrect could you help ?
•  » » 6 years ago, # ^ |   +4 int temp=v[0]/2This is not optimal. Test: 1 1 9 Ans 5: 9 -> 3 + 6 -> 3 + 3 + 3 -> 2 + 2 + 2 -> 1 + 1 + 1 -> 0
•  » » » 6 years ago, # ^ |   0 So what's the optimal algorithm?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 We're trying to minimize:ans = (p[1] — 1) / b1 + ... + (p[n] — 1) / bn + max(b1, b2, ..., bn)It is obvious that b1 = b2 = ... = bn = b (or we can reduce ans).So:ans = (p[1] — 1) / b + ... + (p[n] — 1) / b + b;It remains only to try all possible b.
•  » » » » » 6 years ago, # ^ |   0 I'm not that smart,man! does (p[1] — 1) / b mean it takes this number of minutes for the first one to eat all his cakes? Could you please explain the logic in here.(I know this is the right logic cause many people solved it this way but I just don't get it :(( )
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 (p[1] — 1) / b mean it takes this number of special minutes to split p[1] cakes into the group like b + b + ... + b + p[1] % b.For example, 9-> 3 + 3 + 3, it takes 2 minutes to split: (9 — 1) / 310->3 + 3 + 3 + 1, it takes: (10 — 1) / 3 = 3 minutes to split.
•  » » » » » » » 6 years ago, # ^ |   0 thank you.I understand it now
 » 6 years ago, # |   +5 What I feel right now:
 » 6 years ago, # |   0 Do you know if googlejam write its editorial "fast"(1-2 days after contest) ? I need them for "qualification rounds" and I will need them for Round 1 too. They will post them soon or after whole googlejam is ended?
•  » » 6 years ago, # ^ |   0 It'll definitely be up before the next round.
•  » » » 6 years ago, # ^ |   0 That seems good. Thank you !!!
 » 6 years ago, # |   +23
•  » » 6 years ago, # ^ | ← Rev. 2 →   +21 "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.
•  » » » 6 years ago, # ^ |   0 Sorry for off-topic, but what does ETA stand for?
•  » » » » 6 years ago, # ^ |   0 Edited To Add?
•  » » » » » 6 years ago, # ^ |   0 Oh, I see, thanks)
 » 6 years ago, # | ← Rev. 2 →   0 Oops, eduardische saw it first!
 » 6 years ago, # |   +98 By the way, is there anyone else think task C "Dijkstra" should win the "Best Background Story Award"? :P The Dutch computer scientist Edsger Dijkstra made many important contributions to the field, including the shortest path finding algorithm that bears his name. This problem is not about that algorithm. You were marked down one point on an algorithms exam for misspelling "Dijkstra" -- between D and stra, you wrote some number of characters, each of which was either i, j, or k. You are prepared to argue to get your point back using quaternions... 
•  » » 6 years ago, # ^ |   +15 Yes, I also laughed very hard on this one :D. It is even more hilarious that people in fact very often quarrel about how to pronounce this "ijk" :D. I heard versions "Dikstra", "Dijkstra", "Dajkstra", "Daejkstra" (pronounced in polish). And those quaternions fits there so well :D!