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

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?

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

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

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

Me too!I want explanation!

Use

ios::sync_with_stdio(0);

In case cin/cout is too slow, this line speeds them up

I wasted half an hour because i thought that they were rocks and i don't know how :D then i wasted another half thinking that they mustn't attack each other :D

strange contest time leads to weird results :D

Exactly I even coded that to realise at 1:42 the insane thing i did.

I calculated that max cost is 4n-4, only to realize that weights of the cells were input based. (i assumed 1!)

Same here. The problem becomes much harder with this "new" statement.

Yes it would be. Printing the maximum of the numbers would do.

Same with me,

I think for 1 10 0 70, answer should be 90 (because 3 times of same type can be taken) but for all the AC solutions, the answer gives 30...

WTH?!?!?

I made the same mistake and cost me 2 WAs. however, maybe the problem setter wrote this line there are n types of sugar in the supermarket, maybe he able to buy one. to inform us that he can buy only one pocket of sugar.

I think the problem statement should've been clearer .

Maybe test cases for problem E were generated randomly.

Si eu la fel :))

Me too

Same

Maybe because cin is very slow

You use cin. It's too slow. I made the same mistake

it isn't surprising

Same here

congrats IvanJobs :)

you can play clash of clans . IT's best.

Compute the value for each rightwards diagonal and leftwards diagonal . Now iterate through the whole 2D array , Find the value for that particular cell as (leftDiagVal(cell) + rightDiagVal(cell) — X[cell] ) and greedily update the answer for Odd(i+j) and Even(i+j) . //X[cell] is the value input in that cell Answer = Answer_Odd + Answer_Even

I found it so... Test is too weak.

"maybe he able to buy one" in the second paragraph?

I am not really sure either.

Here you can find information about sync_with_stdio function. The reason, why you are getting WA is you unsync your streams, so if you are using scanf and cin in one program (as you're using in yours), then you will get undefined result.

To use cin/cout with sync_with_stdio, you should not use scanf/printf. In this case it will work properly.