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

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 *p*_{i} 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.

Lets denote the number of character *x* in *s* by *C*_{s}(*x*). Similarly *C*_{t}(*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 *C*_{s}(*x*) and *C*_{t}(*x*) while iterating through positions.

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 2*d*^{2} 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 2*d*^{2}, the overall number of steps is approximately 8*d*^{6}.

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 *f*_{j} (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 *f*_{j} and try to feed 0, 1, 2, \ldots first students in this order. We have 400^{2} states and 400 transitions from each state.

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

find 1 difference=)

lucky

no=) vice versa.

9th test was pretest, firstly pretest got ac, but after contest it got tle. I could easily optimise it a bit on contest to get 100% AC, but it didn't fails from the beginning.

I think problem is in String.split because my solution got AC 781 ms.

it is not the big problem, i think.

http://codeforces.ru/contest/254/submission/2742493 — just initializing vector with 5001 element give stable ac=)

http://codeforces.ru/contest/254/submission/2742524 — or using ArrayList, like you.

and println(str + " " + str) not fast

yes, i know it, i just didn't care about it, because got ac on pretests=)

I had problem like u :|

Задача D.

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

так как площадь двух областей взрыва не более 2 * (

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

d^{2}крыс, т.к. после первого шага максимум столько клеток посещено, а после второго тоже просто в лоб, т.к. мы два раза посетим 2d^{2}клеток, т.е. в принципе, если крыс больше, чем 4d^{2}, то ответ -1.Круто, спасибо. Просто где-нибудь в векторе сохранить их координаты, получается?

именно,

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

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

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

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

so you should submit fast enough solution

we are awalys appreciate you .

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

How can I write fast python input and output. I use readline().split() to read on problem A which got a TLE.

“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?

problem C

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

Ok，thank you.I see.

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

always2*d^2 cells — it actually reduces its size with d with each new rat.Can you please repair the system for this round: http://codeforces.com/contest/254/submission/3038666 (I have a similar one for prob A)

Anyone? Thanks

Can anyone further explain the problem E? I have a solution, but it works for some problems and not for the other ones. http://ideone.com/LW19fV

I know the solution is on the right track, but maybe I am missing something? For example, do you have to feed all friends who are with you that day or can you just feed some and as many as you can?

http://codeforces.com/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).