Fear_Is_An_Illusion's blog

Google Code Jam Round 1C
By Fear_Is_An_Illusion, 10 years ago, In English

The last round for advancing into round 2 starts today at 12:00 MSK

Good luck

Edit : Its over, congrats to all who made it.

Practice Link thanks StoneCold_ for the tip

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

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

How to solve C-large?

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

    Greedily add the smallest coin you need.

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

      Proof?

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

        Add the denominations in increasing order. If you already have interval [1,x] and none of the already existing denominations can help you increase it, then if you add a denomination greater than x + 1, you won't be able to make (x + 1), if you add a denomination smaller than x + 1 you will get a smaller interval.

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

          I think you need to explain a bit more if you actually want to help anyone who doesn't already get it.

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

        Its easy to prove with induction. First sort all coins and take one at a time. If we have a set of coins which can reach all values less than n, and the next coin v is at most n + 1, then we will now be able to reach n + v * c. If however v is larger than n + 1, then we will not be able to reach n + 1, so we need to add that coin to our collection. This is also the best case, we could have added a smaller coin but it will only reduce our max reach in the future so there is no reason to do it.

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

    Another solution (too complicated, I guess, but seems interesting to me :) )

    Imagine that we are to check that existing values cover 0 ... v:

    we could iterate through them in decreasing order and recalculate v as max(v - c·vali, vali - 1) and check if v = 0 in the end.

    So, let's do the following dymanic programming:

    dp[add][i] -- minimum v we can achieve if the first i values were used and we added add new values.

    One can do transitions in O(1) (the best value to add for 0 ... v is or ); .

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

    I personally didn't take part and had no chance to submit my solution, but it seems not hard to prove the correctness of the following solution.
    Suppose we have already managed to add coins in such a way that the requirements of the problem are fulfilled and we got all values in range [1,p] and considered first i-1 coins in sorted order. So now there is two cases to be considered.
    1.a[i]<=p+1. This means that we can collect all the values until p+c*a[i] inclusive, so we can set i=i+1,p=p+c*a[i]. 2.a[i]>p+1. This means that we need to get all values in range [p+1,a[i]-1]. So it is better choice to add coins starting from value p+1. So here we need to decide how many coins to add starting from p+1 in order get values from required range. So we can make either binary search to find out exact number or write out sum of arithmetic progression and solve linear equation. Let k is that number, so we need to add all [p+1,p+k] coin denominations, like in the first case we will set i=i+1,p=p+sum[p+1;p+k]+(c-1)*sum[p+1;p+k] and we should increase answer by k.

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

I couldn't solve A large, any hints ?

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

    For each row, except the last one you need to ensure that there's no way to place the ship.

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

    The code is:
    """""""" answer = R*(C/W) + W;

    if(C%W == 0)

    --answer; """"""""""""

    That means that you 'hit' all possible squares (C/W),and we multiply it by R. After the '+W' means that we fill correct final squares. the 'If' statement, decrease 'answer' by 1,because if W is multiple of C,then in our 'last' option we have one option instead of two.

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

What about B-large?

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

    Dynamic programming: dp[ind][suff] — expected number bananas you will give monkey where covered ind letters and suffix with length suff is equal to prefix of target with length suff. Then iterate next letter and go to the state — (ind + 1, nsuff), where is nsuff the maximal length of suffix of current string equals to the prefix of target. Also be careful with state (ind, L). L  =  |target|.

    But at the start you need to calculate how many bananas you need to bring. This value can be computed greedily (val).

    Answer will be: dp[0][0] - val.

    Code

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

      You seriously over-complicated the problem, all you need to do is multiply all keystroke chances together, multiply this with the amount of characters typed by the monkey — target length +1 (the amount of places the string can appear at). This is the expected amount of bananas the monkey will get:

        double expectedBananas = 1;
  for(char c:target){
    expectedBananas *= keyCount[c]/K; // probability to get the right word at one place
  }
  expectedBananas = expectedBananas*(S-L+1); // multiply by amount of places you can get the right word on
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        Won't this cause problems since getting a match on position i is not independent of getting a match on position i + 1 ?

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

          Interdependence doesn't matter if we just seek the expected value. The problem setter might have missed this since it made the problem really easy, it is possible to solve this quickly even if the strings were of length 100,000.

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

            The low limits for the Large were intentional and allowed solvers to use either DP or linearity of expectations.

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

        "You seriously over-complicated the problem"

        Well, I think I better not even mention my dp on Aho-Corasick solution =.=

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

          You and me both. At least it worked.

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

          Me too. I used a similar approach, but even more complex. I did DP[l][m][t], which means the probability that we reach a state with l letters typed, a current prefix match of length m and t full occurrences of target string. Then at each state, I checked the probability of typing all 26 letters and updated the next state. To check the next value of m at the transition, I used Z Algorithm / KMP's Failure Function.

          The maximum bananas was the maximum value of t among all pairs {m, t} such that DP[S][m][t] > 0. And the expected bananas we keep is that minus t * DP[S][m][t] for all pairs {m, t}.

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

        Won't the output be same for the following two test cases using this algo?

        2 2 3 AB AA

        and,

        2 2 3 AB AB

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

          No, the output of the program wont be the same since in the first case you need to bring 2 bananas while in the second case you only have to bring one banana. The expectation value of number of bananas the monkey will get is 0.5 in both cases though (which is whats calculated in my post), so the answer to the first is 1.5 and the answer to the second is 0.5.

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

            Yes. I was talking about the expected number of bananas that the monkey will get only. Got confused, that, it is not the final answer. Thanks!

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

      I have been wondering about how the expectation updating works. Your dp stores the expected values. Then you update a new expected value with an old expected value by doing something like dp[i + 1] = p(i+1) * (1 + dp[i]). What is the principle behind this? I guess you use the law of total expectation: E(X) = sum(E(X|A_i) * P(A_i)). According to your code, P(A_i) should be p, and E(X|A_i) is cur + calc1(ind + 1, snuff). Am I right?

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

First time I took first place in a competition! Yay me!

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

    Cool. Any advice for how to practice and becoming better for beginners? I thought coming up for a solution for problem 2 and problem 3 was really tough. How to remove this mental block which comes up with every new problem?

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

      I got an advanced degree in mathematics so my ability to reason about problems like these comes from many years of experience. It is kinda hard to distill that into a tip! But this is how I worked through the solutions:

      Problem B is basic probability theory and some implementation.

      Problem C is related to the number system; if you are only allowed to use one of each coin then the ideal solution is all powers of 2, with two of each it becomes all powers of 3 etc. Since you are forced to use some other coins as well this gets shifted a bit, but the general principle is the same.

      → Reply