savinov's blog

GP of Azov Sea
By savinov, 11 years ago, In Russian

Предлагаю здесь обсудить задачи прошедшего Гран-При.

Интересно узнать решение задачи K.

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it
  • A: We found the formula to be: (n^2 + 6)/12, but we don't know how, how did others solve it?
  • D: You can solve it by converting K to binary. And check the bits
  • E: You just need to know what is the probability one would change side in T seconds. It is: sum ncr(n, 2i) * p^2i * q^(n — 2i) which has a closed form. Then somewhat easy, you may O(n) dp or just looping :)
  • G: We did not get time to solve it. But it seems you need to have 5 arrays which will say for each position where is the first 1~5 in certain direction. And then simulate
  • H: Loop over the # of bet for winning team. You will get the sum of bets for loosing teams. Now distribute them. A special check is for P = 100. and 100 > P >= 50 is impossible.
  • J: For each question have a bitmask for the stundets who can answer it correctly, say this is: possible[0][i] for ith question. Now, possible[j][i] = possible[j — 1][i] & possible[j — 1][i + 1] and in this way build possible[0..k-1]. Now its turn to go down. For possible[k — 1] make solution[k — 1] which will contain 1 participant which is in corresponding possible[k — 1]. While going down, solution[j][i] = solution[j + 1][i] | solution[j + 1][i — 1]. And if it is not of size k — j add additional participants from participant list. So you get your answer in solution[0] array
  • K: say qi is the dist to i'th city. Take cumulative sum Sq. So going from i to j means: |Sqi — Sqj|. So sort all Sq's and try to take consecutive k Sq's. Check which one is minimum.
  • I am not sure:
  • C: for each side, extend its neighboring side outwards to get a triangle / parallel line. Now you know what should be the additional area of the extended triangle. Now since you know the area you will get a line where the peak have to of the extra point. see if there is any lattice point on that line and between the feasible boundary we defined earlier.
→ Reply