Google Code Jam Round 1C

Блог пользователя Fear_Is_An_Illusion

Автор Fear_Is_An_Illusion, 9 лет назад, По-английски

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

codejam, round 1c

Fear_Is_An_Illusion
9 лет назад
27

Комментарии (27)

Написать комментарий?

Temirulan

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

← Rev. 2 →

+16

How to solve C-large?

→ Ответить

MarioYC

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

+38

Greedily add the smallest coin you need.

→ Ответить

smx

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

Proof?

→ Ответить

MarioYC

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

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.

→ Ответить

xxTastyHypeBeast666xx

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

+26

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

→ Ответить

JohStraat

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

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.

→ Ответить

pavel.savchenkov

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

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·val_i, val_i - 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 $\text{[math]}$ or $\text{[math]}$ ); $\text{[math]}$ .

→ Ответить

lth

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

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.

→ Ответить

Fear_Is_An_Illusion

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

I couldn't solve A large, any hints ?

→ Ответить

Urbanowicz

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

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

→ Ответить

Hepic_Antony_Skarlatos

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

← Rev. 6 →

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.

→ Ответить

smx

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

What about B-large?

→ Ответить

Temirulan

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

← Rev. 4 →

+18

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

→ Ответить

JohStraat

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

← Rev. 2 →

+74

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

→ Ответить

TimonKnigge

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

+17

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

→ Ответить

JohStraat

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

← Rev. 4 →

+31

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.

→ Ответить

tigupine

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

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

→ Ответить

ADJA

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

+73

"You seriously over-complicated the problem"

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

→ Ответить

TimonKnigge

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

+10

You and me both. At least it worked.

→ Ответить

tenshi_kanade

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

← Rev. 2 →

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

→ Ответить

PrakharJain

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

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

→ Ответить

JohStraat

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

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.

→ Ответить

PrakharJain

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

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!

→ Ответить

sping128

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

← Rev. 2 →

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?

→ Ответить

JohStraat

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

+52

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

→ Ответить

ediston

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

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?

→ Ответить

JohStraat

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

← Rev. 5 →

+10

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.

→ Ответить