You need to get 20 points in order to advance to Round 1.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
You need to get 20 points in order to advance to Round 1.
Name |
---|
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.
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.
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.png
because a lot of solutions like eatmore solution he put case 5: gabriel = min(r, c) >= 4 || (min(r, c) == 3 && max(r, c) > 5);
I think, before this, they check that r*c%x == 0
In Dijkstra, tourist has performed this step:
Can someone please explain why the reasoning behind this step?
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.
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..
Similar mistake. I didn't initialize the array properly after increasing the number of repetition. :'(
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 :')
I used Rust for the first time in this contest. I made the very same mistake, and Rust caught it for me. Success! :)
Input validation saved me)
Lesson: Use a memory safe programming language...
How many people failed this testcase for D: 5 3 5?
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 x==6 I just checked r*c%x==0 and min(r,c)>3
Similar. Cool problem :)
For me, it was
5 3 10
,5 3 15
, and5 3 20
instead — quite similar but from the other side.I'm the victim of 5 3 5, staircase was a killer.
Solution for B
Observe 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
.How do you get that
ceil((Pi — X) / X)
special minutes would be needed? Can you please provide a short proof or intuition?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.
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
Actually we want the smallest
n
such thatPi <= n*X
Or we can say
Pi = n*X + c
where-X < C <= 0
There are many implementations that does not make use of the floating point
ceil()
functionCan you give me example of input
1 2 5 9 11 7
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
Correct
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?
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:
Actually My doubt was why/how ceil(P[i]-x)/x ?
I have explained in another comment above.
Is there any way to filter standings by country?
There is: http://www.go-hero.net/jam/15/regions
And: http://a2oj.com/CodeJamTools/Results.jsp
how to solve large input version of Dijkstra problem ?
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.
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:
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.
I didn't notice the fourth power thing and implemented this too. A cute way to get rid of this case is simply:
(for the exponentiation part, use full value of X)
... 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.
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.
actually 4L is one of periods because
x^4 = 1 for any x in {+-}{1,i,j,k}
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.
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).
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.
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.
Did the same thing, except for the last step, you could check that the total product was -1.
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?
Right
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 ?
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.
Thanks
I did the same. But only checked prefix/suffix till four copies of the string.
Can anyone explain how we can we solve this 5 3 10 when richard chooses this omino ?
Thanks, missed this case and wrote min(r, c) > 3 in code. :(
EDIT: sniped...why does delete button still show if it can't be deleted anymore?
Thanks.
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?
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.
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 :)
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.
Fast exponentiation is not really needed, as only X % 4 matters.
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?
if(X > 20) X =20+X%4
I'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
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:
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).
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.)
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,
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)
This is not a valid position, although only one connected component of size 18 needs to be tiled (X=6 on a 4x6 grid):
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.
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).
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.
For large, to do casework, you need some observation like:
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.
I didn't understand, 3 ifs was too much for you, so you decided to solve 64 ifs?
In Gym: 2015 Google Code Jam Qualification Round (GCJ 15 Qualification).
enta Prince :D
My submission for B was judged as incorrect could you help ?
int temp=v[0]/2
This is not optimal. Test:
Ans 5: 9 -> 3 + 6 -> 3 + 3 + 3 -> 2 + 2 + 2 -> 1 + 1 + 1 -> 0
So what's the optimal algorithm?
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.
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 :(( )
(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) / 3
10->3 + 3 + 3 + 1, it takes: (10 — 1) / 3 = 3 minutes to split.
thank you.I understand it now
What I feel right now:
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?
It'll definitely be up before the next round.
That seems good. Thank you !!!
Analysis has been posted.
"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.
Sorry for off-topic, but what does ETA stand for?
Edited To Add?
Oh, I see, thanks)
Oops, eduardische saw it first!
By the way, is there anyone else think task C "Dijkstra" should win the "Best Background Story Award"? :P
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!