Nerevar's blog

Codeforces Round #155 (Div. 2) — tutorial
By Nerevar, 12 years ago, In English

254A - Cards with Numbers

For each x from 1 to 5000 store a list L(x) of such indexes i that ai = x. Then just check that all lists have even size and output the elements of each list in pairs.

254B - Jury Size

One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day d of the preparation add pi to the number of distinct jury members that have to work on problems on day d. Then the answer is maximum calculated sum over all days. Be careful with the year 2012.

254C - Anagram

Lets denote the number of character x in s by Cs(x). Similarly Ct(x) is defined. Then the minimum number of changes required to get anagram of t from s is equal to . Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values Cs(x) and Ct(x) while iterating through positions.

254D - Rats

Choose arbitrary rat (for say, the leftmost of the upmost). It's cell should be cleared. Make a BFS that never goes further than d from this cell (we will call such a BFS by d-BFS). It will visit approximately 2d2 cells in the worst case. So, we have to blow the first grenade in one of the visited cells. Lets check every visited cell as a candidate. Make a d-BFS from the candidate cell. Some cells with the rats will not be visited. That means that they should be cleared by the second grenade. Choose arbitrary cell with a rat that was not cleared by the first grenade. Make a d-BFS from it. All cells visited by this BFS are candidates to blow the second grenade. Lets check every such cell. Checking a cell again means making a d-BFS from it. If this BFS visits all cells that were not cleared by the first grenade, that we have found a solution. As every d-BFS visits at most 2d2, the overall number of steps is approximately 8d6.

254E - Dormitory

The problem can be solved by dynamic programming: denote as D(n, r) the maximum rating that we can achieve in the first n days with the condition that we have r kilos of food remaining from the day n - 1. It is obvious that if we decide to feed k friends on some day, the better way is to feed k friends with the lowest fj (of course we consider only friends that live with Vasya on that day). So we need to sort all available students in the order of increasing fj and try to feed 0, 1, 2, \ldots first students in this order. We have 4002 states and 400 transitions from each state.

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

Comments Comments (28)
| Write comment?
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

http://codeforces.me/contest/254/submission/2734441 http://codeforces.me/contest/254/submission/2741882

find 1 difference=)

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

Задача D.

Как, после первого шага, быстро найти первую, не убитую крысу? А после второго, как понять, всех ли мы убили?

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

    так как площадь двух областей взрыва не более 2 * (d2 + (d + 1)2) = 290, а значит крыс тоже не больше, то можно и в тупую посмотреть

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

    просто влоб, бежим по всем крысам, мы пройдем максимум 2d2 крыс, т.к. после первого шага максимум столько клеток посещено, а после второго тоже просто в лоб, т.к. мы два раза посетим 2d2 клеток, т.е. в принципе, если крыс больше, чем 4d2, то ответ -1.

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

      Круто, спасибо. Просто где-нибудь в векторе сохранить их координаты, получается?

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

        именно, голубчик голубушка

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

    Не читал разбор, я делал так: если крыс больше 290 то ответ -1 — мы не сможем убить больше при d<=8; находим две самые далёкие крысы (просто x*x+y*y), рассматриваем просто два квадрата со сторонами 2d+1 и центрами в найденных точках — это центры возможных взрывов, причём других центров быть не может. Ну а теперь нужно просто по найденным двум центрам проверить убивают ли они всех крыс — от каждого пускаем ширину и смотрим все ли крысы убились.

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

I think that judging system didn't work properly during the contest. I got some TLE on test#9 for problem A, with my O(N) algorithm. after some TLE , I got AC with the same code :-?? it's funny that, at the final tests I got TLE on test#9 again :D and after the contest, that code got AC :-??

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

    You got AC with 968/1000ms. It's OK, that execution time slightly changes. You have to write more fast code to be sure. +/- 50ms is quite little time.

    BTW, your solution is too slow because you flush(use endl) too often. If you will use '\n' you'll get faster solution. (I was wrong, throught, it doesn't help a lot. GCC helps here, twice faster:) )

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

      u'r right, tnx. but that's not fair, the test should be passed or not. my rank is badly decreased for this reason :((

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

        so you should submit fast enough solution

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

      we are awalys appreciate you .

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

Problem C reminds me with yesterday's SRM .. the Div1-250 pointer, but for sure it was with small constraints.

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

“For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position.” How to decide whether the optimal answer can contain this character in that position or not?

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

    problem C

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

    Calculate the minimum number of changes that we will need if we place this character. Compare this number with the optimal answer.

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

There was some discussion in Russian about problem D, which I didn't quite understand (go figure!). There is an alternative solution, leading to the same running time.

Step 1 First check if the number of rats is > (d + d + 1)^2 + 1. If that is the case, return -1 immediately — there is no way how to blow the bombs as to cover more than this number. Actually, my solution fails because I didn't add 1 to the sum, i.e. off-by-one error :)

Step 2 For every rat, run a d-BFS to find the cells, where a bomb should be to kill it. As the rats are 4*d^2 and the d-BFS takes 2*d^2, this step takes approximately 6*d^4 operations. Sort the cells for convenience later, making it 4*d^2 * (2*d^2 * log(2*d^2)) = 16*d^4*log(d) (don't know why you are using operations insted of Big-O notation, but I'll stick with your way. I guess for a such a small d it kind of makes sense).

Step 3 Then, similar to your solution, do a single BFS from any rat (it should be covered by at least one bomb). Any of the covered cells is a candidate for the first bomb. Try all of them.

Step 4 For each of them, iterate through all rats. If the rat is covered by the bomb, skip it. As we have found the cells, covered by each rat in step 2, this can be done in O(log(d^2)) per rat. Otherwise, maintain a set of feasible cells, where the second bomb can be. That is just the intersection of the current set of feasible cells with the cells, possible for the current rat. As we have sorted the cells, this can be done linearly. 2*d^2 cells for the first bomb, 4*d^2 rats to check, each of them requiring 2*d^2 operations — 16*d^6. However, in practice it is much much faster, because the set intersection cannot contain always 2*d^2 cells — it actually reduces its size with d with each new rat.

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

Can you please repair the system for this round: http://codeforces.me/contest/254/submission/3038666 (I have a similar one for prob A)

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

http://codeforces.me/contest/254/submission/21400911

Can someone help point out where did I messed up? I think my code should also work in O(d^6).

→ Reply