Google Code Jam 2015. Qualification Round.

10 лет назад, # |

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?

→ Ответить

pi37

10 лет назад, # ^ |

+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.

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

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;
}

→ Ответить

cgy4ever

10 лет назад, # ^ |

+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. >_<

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

→ Ответить

anuraganand

10 лет назад, # ^ |

+11

Similar mistake. I didn't initialize the array properly after increasing the number of repetition. :'(

→ Ответить

carlotheboss

10 лет назад, # ^ |

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 :')

→ Ответить

andreyv

10 лет назад, # ^ |

+61

I used Rust for the first time in this contest. I made the very same mistake, and Rust caught it for me. Success! :)

→ Ответить

Edvard

10 лет назад, # ^ |

Input validation saved me)

assert(read()); 
// ...
if (!(cin >> n >> k)) return false;
// ...

→ Ответить

jiangzhijie

10 лет назад, # ^ |

Lesson: Use a memory safe programming language...

→ Ответить

Svyat

10 лет назад, # |

+28

How many people failed this testcase for D: 5 3 5?

→ Ответить

waterfalls

10 лет назад, # ^ |

+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 :)

OOO

O..O

→ Ответить

Svyat

10 лет назад, # ^ |

For x==6 I just checked r*c%x==0 and min(r,c)>3

→ Ответить

Edvard

10 лет назад, # ^ |

Similar. Cool problem :)

→ Ответить

Gassa

10 лет назад, # ^ |

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

→ Ответить

Neverauskas

10 лет назад, # ^ |

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

→ Ответить

10 лет назад, # |

+14

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.

→ Ответить

10 лет назад, # ^ |

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

→ Ответить

10 лет назад, # ^ |

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.

→ Ответить

10 лет назад, # ^ |

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

→ Ответить

10 лет назад, # ^ |

Actually we want the smallest n such that Pi <= 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() function

n = Pi / X;
if (Pi % X != 0) {
  n++;
}

→ Ответить

geekSoul1

10 лет назад, # ^ |

Can you give me example of input

1 2 5 9 11 7

→ Ответить

10 лет назад, # ^ |

+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

→ Ответить

geekSoul1

10 лет назад, # ^ |

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

→ Ответить

10 лет назад, # ^ |

Correct

→ Ответить

saurabhverma

10 лет назад, # ^ |

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?

→ Ответить

10 лет назад, # ^ |

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

→ Ответить

saurabhverma

10 лет назад, # ^ |

Actually My doubt was why/how ceil(P[i]-x)/x ?

→ Ответить

10 лет назад, # ^ |

I have explained in another comment above.

→ Ответить

Na2a

10 лет назад, # |

Is there any way to filter standings by country?

→ Ответить

tomlau

10 лет назад, # ^ |

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

→ Ответить

__builtin__wolfy

10 лет назад, # ^ |

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

→ Ответить

AM51

10 лет назад, # |

how to solve large input version of Dijkstra problem ?

→ Ответить

Roberio

10 лет назад, # ^ |

← Rev. 5 →

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.

→ Ответить

10 лет назад, # ^ |

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.

→ Ответить

Urbanowicz

10 лет назад, # ^ |

+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

→ Ответить

10 лет назад, # ^ |

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.

→ Ответить

ffao

10 лет назад, # ^ |

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)

→ Ответить

Urbanowicz

10 лет назад, # ^ |

... 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.

→ Ответить

10 лет назад, # ^ |

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.

→ Ответить

riadwaw

10 лет назад, # ^ |

actually 4L is one of periods because

x^4 = 1 for any x in {+-}{1,i,j,k}

→ Ответить

10 лет назад, # ^ |

+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.

→ Ответить

hellman_

10 лет назад, # ^ |

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).

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Junior94

10 лет назад, # ^ |

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.

→ Ответить

MarioYC

10 лет назад, # ^ |

+30

Did the same thing, except for the last step, you could check that the total product was -1.

→ Ответить

10 лет назад, # ^ |

← Rev. 2 →

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?

→ Ответить

hellman_

10 лет назад, # ^ |

Right

→ Ответить

aviaryan

10 лет назад, # ^ |

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 ?

→ Ответить

eduardische

10 лет назад, # ^ |

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.

→ Ответить

aviaryan

10 лет назад, # ^ |

Thanks

→ Ответить

karan173

10 лет назад, # ^ |

I did the same. But only checked prefix/suffix till four copies of the string.

→ Ответить

ashish1610

10 лет назад, # |

Can anyone explain how we can we solve this 5 3 10 when richard chooses this omino ?

##
 ##
  #

→ Ответить

oversolver

10 лет назад, # ^ |

→ Ответить

ashish1610

10 лет назад, # ^ |

Thanks, missed this case and wrote min(r, c) > 3 in code. :(

→ Ответить

waterfalls

10 лет назад, # ^ |

← Rev. 2 →

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

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

→ Ответить

ashish1610

10 лет назад, # ^ |

Thanks.

→ Ответить

10 лет назад, # |

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?

→ Ответить

akulsareen

10 лет назад, # ^ |

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.

→ Ответить

10 лет назад, # ^ |

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 :)

→ Ответить

misof

10 лет назад, # |

← 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.

→ Ответить

hellman_

10 лет назад, # ^ |

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

→ Ответить

misof

10 лет назад, # ^ |

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?

→ Ответить

Xellos

10 лет назад, # ^ |

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

→ Ответить

klamathix

10 лет назад, # ^ |

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).

→ Ответить

misof

10 лет назад, # ^ |

← Rev. 2 →

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.)

→ Ответить

ashmelev

10 лет назад, # ^ |

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)

→ Ответить

fram

10 лет назад, # ^ |

← 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....

→ Ответить

Gassa

10 лет назад, # ^ |

+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.

→ Ответить

Swistakk

10 лет назад, # ^ |

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).

→ Ответить

ffao

10 лет назад, # ^ |

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.

→ Ответить

I_love_Hoang_Yen

10 лет назад, # ^ |

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.

→ Ответить

Swistakk

10 лет назад, # ^ |

I didn't understand, 3 ifs was too much for you, so you decided to solve 64 ifs?

→ Ответить

MikeMirzayanov

10 лет назад, # |

+48

In Gym: 2015 Google Code Jam Qualification Round (GCJ 15 Qualification).

→ Ответить

Killever

10 лет назад, # ^ |

enta Prince :D

→ Ответить

10 лет назад, # |

My submission for B was judged as incorrect could you help ?

→ Ответить

StarCuriosity

10 лет назад, # ^ |

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

→ Ответить

10 лет назад, # ^ |

So what's the optimal algorithm?

→ Ответить

SashaMN

10 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

10 лет назад, # ^ |

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 :(( )

→ Ответить

SashaMN

10 лет назад, # ^ |

← Rev. 2 →

(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.

→ Ответить

10 лет назад, # ^ |

thank you.I understand it now

→ Ответить

SashaMN

10 лет назад, # |

What I feel right now:

→ Ответить

10 лет назад, # |

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?

→ Ответить

Xellos

10 лет назад, # ^ |

It'll definitely be up before the next round.

→ Ответить