riadwaw's blog

Google Code Jam 2015. Qualification Round.
By riadwaw, 10 years ago, In English

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

Post about entire GCJ

  • Vote: I like it
  • +66
  • Vote: I do not like it

Comments Comments (99)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +54 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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;
}
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +61 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Input validation saved me)

        assert(read()); 
// ...
if (!(cin >> n >> k)) return false;
// ...
        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lesson: Use a memory safe programming language...

      → Reply
»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Similar. Cool problem :)

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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++;
}
          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you give me example of input

            1 2 5 9 11 7

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +11 Vote: I do not like it 
                  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
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                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

                → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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:

          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
      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any way to filter standings by country?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve large input version of Dijkstra problem ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              actually 4L is one of periods because

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it +19 Vote: I do not like it

                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.

                → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Right

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

##
 ##
  #
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    222
223
333
113
411
441
445
555
566
666
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    ****##^^^^
xxx*@##%%^
xx@@@@#%%%

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +63 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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:

        1. Check if the whole product is -1 in log(X) time.
        2. 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).

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it +147 Vote: I do not like it

      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....
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
10 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So what's the optimal algorithm?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like 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.

            → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What I feel right now:

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Analysis has been posted.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Oops, eduardische saw it first!

→ Reply
»
10 years ago, # |
  Vote: I like it +98 Vote: I do not like it

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...
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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!

    → Reply