Also for me, I'm not waiting for it as hard as I waited before :)

But you can solve problems ,but your ratings will not change :)

Second time!

Yes. I just think I saw it by mistake.

I'm from China too.It's a good contest time:)

That is because in the same day there will be topcoder SRM + Hackerrank 101 hack august

It will surely increase there are a great number of chinese coder will join:)

4077 registrants... :)
In round 263 there were 3988 registrants...

You can check time conversion from contests -> current contest and click on the time given :).

According to this comment, you are not a programming contest addict... :P

You know you are a programming contest addict when : You have become the master of converting timezones to your country's standard time.

Best of luck! I hope I take part in this contest(I don't like the time of this contest) . If I do, I wish I atleast become blue again.

According to my own experience, I think that you will stay in expert for a few rounds before getting to div1

Not a good time for US though: 12:30 AM to 3:30 AM depending on the time zone...

narcis_vs tnks for this contest :)

what does it mean? :)

Ну извини) ладно летом и в выходной такое время. То еще можно написать. А если в будни и для московского времени, кто-то работает, кто-то на учебе. Не особо подходящее).

P.S. Хотя в этот раз для меня отлично вышло. В 19.30 не успел бы написать)

My exams ended 3 hrs before contest. Yay!

Take any previous contest in virtual mode, for beginners DIV 2 is the place. Why not try the last contest itself : Click here Simply register and familiarize yourself with how a codeforces round actually is.

Since solving AB doesn't really give you anything and there's no rating to lose, you should start from D or E. These div2 contests are a true golden mine for trying out risky new approaches :D

thanks(!):D

New genius one?

я сначала также подумал, что можно купить не 1, а несколько пакетов сахара

Нет, там ничто об этом не говорит, кроме 5 теста

В супермаркете всего имеется n различных видов сахара

Какое максимальное количество конфеток в качестве сдачи Caisa может получить, если купит ровно один вид сахара?

Я здал задачу, но до сих пор не понимаю, можно купить только 1 мешок какого либо вида сахара?

Если можно покупать много мешков, то на тест 1 10 2 30 у автора не правильное решение

Уже понял, Каиса хочет купить только 1 сахар

Я вообще сначала норм понял задачу, но одно лишнее условие написал, поэтому ВА3. Потом стал думать, что этот придурок таки хочет несколько пачек купить и ВА5. Успел решить Б, С (упала на частном случае) и Д, и только когда до конца оставалось 1-2 минуты — понял как должно быть.

My idea was same too, but this technique wouldn't pass the sample I/O. I mean if there is several subsequence with same length , which one would you consider ? For example

between

1 4 2 3
4 1 2 3

you have 1 2 3 and 4 2 3 , which one would you choose for 1 4 2 3 , here it is obviously 1 2 3 eventually you have to try all the sequences. I think there are some other technique.

You must use suffix automat.(Sorry for mistakes ) :D

This problem is as like as SPOJ: X-MEN
Difference is in the problem of spoj, we have to find out LCS between only one pair. But In D of this round, we have to find out LCS between each pair. And it is possible, as maximum value of k can be 5.

*** The problem of SPOJ(given above) can be converted into LIS... Then I solved it in nlog(n).

Your algorithm is not correct, because there could be more than one LCS.

The solution is quite simple — for every you make a vector V_x = {a₁, ... a_k}, where a_i means position of x in i-th permutation. Now you create a directed graph — iff . Now an observation — if u₁, u₂, ..., u_m is a common subsequence, then u₁, ... , u_m is a path in our graph. So now your problem is to find the longest path in a graph. But this is a DAG, so it is easy — you can either make a topological sort, or just brute it in O(n²).

That will have problems in case of multiple LCSs. Eg, consider (1,2,3,4,5), (1,2,3,5,4) and (4,1,2,3,5). First two have two LCS : (1,2,3,4) and (1,2,3,5). If you took only one, and that was (1,2,3,4), then you will get final answer 3, whereas the final answer is 4.

The trick here is that input is a permutation (no repeats). Hope this gives a hint to those who still want to think about D.

i donot think u need all of that there is a very important observation which is for every sequence the numbers are found only once so u can save the index of every digit for every sequence and try to start with any of them but u will need to know the last digit taken so that the sequence in valid then u check if all the numbers are in valid position (after the last number) u add this digit in all the sequences to the solution so the state will be (last digit taken) and u will have a loop on the all the digits except the last one trying to choose any valid digit sorry if it seems a little bit messy or alot

yup

It seems to be obvious that in each step the current energy is equal to h[0] — h[current_step], so you just need to increase h[0] (from 0 to max(h[]))

Instead of increasing height of some pylons you can just increase on all your money height of the first pylon, answer would be the same because increasing height of the first pylon just increases your starting energy. So you calculate minimum energy on the way and then add this energy (or 0) as a height to the first pylon.

make dp matrix for 4 diagonal you will need 4 dp arrays for that one to add dollars from up-left and from bottom-left , up-right , bottom-right.
then make another dp matrix to collect all of them dp[i][j]=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3*mat[i][j] --> mat[i][j] is original value we subtract 3 of them because we add the same cell 4 times and we need just once.
one observation is that the one bishop will be on white cell and another will be on black one (like a chess board) because problem statement says that "there is no cell that is attacked by both of them" if you tried to put both on white cells you will see there is a cell attacked by two , try it
so just loop on all i,j in dp and take maximum in black cells and maximum in white one and result is the sum.
feel free to ask

Потому что сдача будет равна семи долларам и 70 конфетам

Вы за $10 покупаете сразу целый "вид" сахара, который стоет $2 30ct. Вам дают сдачу $7 и 70 конфеток.

у меня также было, решилось добавлением пробела в конец файла

В конце вывода зачем убрали '\n' ?

		if (i + 1 < N)
			cout << endl;

Если бы апдейтов было много, то, возможно, было бы так. С таким маленьким их количеством можно спокойно все перестраивать и чистить.

Думаю можно запрос второго вида можно за линию делать(их не больше 50 по условию), то есть обновлять значения до корня.

а как нужно решать задачу с помощью персистентного массива?

С: Если слоны стоят на одном цвете (шахматной доски), то линии их атак обязательно пересекутся. Значит решаем отдельно для одного слона на белых клетках и для другого на черных. Просто перебираем позицию, а сумму можно посчитать динамическим программированием.

D — суффиксный автомат. Нa e-maxx.ru почитай, там в разделе суффиксный автомат в самом низу про наибольшую общую подпоследовательность нескольких строк.

Я в D сделал так: сначала построил ориентированный граф по первой перестановке. От i - го элемента до всех, кто справа. Затем повычеркивал ребра, которые противоречат остальным перестановкам. А далее задача о максимальной подпоследовательности на полученном графе. Вроде работает =) O(K * N² * logN)

Тогда почему же Вы не реализовали D и E?

UPD: да еще и С

What a contest! I was hacked for the first time! :/

Find the best bishop for (i+j)%2=0 and the best bishop for (i+j)%2=1, then add them. Like the board for chess.

colors of bishops should be different

You don't need to check each and every combination of pairs. It is stated in the problem statement that "No position should be attacked by both the bishops", this made the problem simpler.

Now you need to check the max for bishop on black positions and max for bishop on white position and add those. Thats it :)

If you look carefully then you will see the board is bipartite.A white bishop cannot attack a black one. So find the max black diagonal and max white diagonal. answer is the summation.

Oh, I missed that part. Thanks!

Well , I think you know what a white cell and black cell in chess is. Now see , if you place a bishop in a black cell than you can't put the other in black too. because then they would attack atleast one common cell . try drawing it in paper. So , the problem is no bishop lines intersect each other. so you calculate for each one seperately like this

//first bishop
for(int i=1;i<=n;++i)
  int j;
  if(i%1)
     j=1 // for second bishop , j=2
  else
     j=2 // for second bishop, j=1
  for(;j<=n;j+=2)
    // calculate sum from fourcorners
  if(sum>bishop1Max)
     //change max value and position

I didn't)

they thought they can buy more than one pocket with sugar

This is tricky test case. 1 9 9 0 Output:0 not -1

i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.

если купит ровно один вид сахара

this is only possible during practice. In contest You have to figure out by yourself :)

You can't see your output.. You have to figure it out yourself

That is the intended behavior during a codeforces round. You do not get to see the pretest that caused your program to fail.

You can not see pretests during the round. You must find a wrong test and mistake in your solution yourself.

You cannot see pretests during the contest ;)

Or use <= instead of < when comparing. I had the same bug unfortunately ^^

Same :D

Same things happen with me Killever ; At least this contest was unofficial for me :P

I got TLE for using cin/cout :/

Уже высвечиваются :)

cin'ом считывать долго, напиши в начале main'на ios_base::sync_with_stdio(0) и получишь accepted.

The better solution is to use array sum[2][N*2]. sum[0] — sums of LT-RB diagonals, sum[1] — sum of LB-RT diagonals. To calculate such array you need only two formulas:

sum[0][i+n-j-1] += a[i][j]
sum[1][i+j] += a[i][j]

Then the answer for (i,j) is sum[0][i+n-j-1] + sum[1][i+j] - a[i][j]. That's all.

Just like Prefix sum