Hello everyone,

I'd like to invite you to participate in a 2-hours Div2 round which will be held this Saturday, August 30th at 11:30 AM MSK. Div1 coders can take part out of competition, as usual. The problems were prepared by me and Archazey (B and C). I'd like to thank Gerald for helping preparation, Archazey for english translation and MikeMirzayanov for the Codeforces system.

The main characters of this round will be Caisa and Gargari,which have some interesting tasks for you. I hope you will enjoy the round. Good luck and have fun!

**UPD**: It will be used a standard scoring.

Here are the winners:

1.lymmd

5.nxihkke

Stats about hacks can be found here.

Editorial is here.

First time to take part out of competition :)

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

Congratulations ! Maybe you can become a nice couple (●′ω`●)

too late man I already got Engaged :P

Well that escalated quickly :P

ignore.

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

Second time!

I think this is the first round made by someone from Vaslui (my hometown, too) :D My round is coming soon :P

The day is just to sign up for a new term, and it's afternoon in China! we happen to have much time for it ^_^ !

Yes. I just think I saw it by mistake.

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

Very unusual contest time! :D

I think there will be a high decrease of the number of registrants!

Good Luck.

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

Oh! I didn't know these! Do the times have interference too?

Fortunately not, you can see them here

Thx very much, it help me much.

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

`4077`

registrants... :)In round 263 there were

`3988`

registrants...Please add time conversions :)

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

Oh, cool

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.`

Hahaha, I became used to clicking the links in announcement post to check.

That is an implication. But is it an equivalence?

Very nice. I will do my best to do this round and get >1700 rating.

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.

I wish you good luck. :D

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

finally a chance to participate in a good time :D

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

Converted Time Washington DC, District of Columbia, U.S... 3:30 AM EDT http://fc02.deviantart.net/fs71/f/2013/281/0/0/sleep_is_overrated__by_austin_comix_inc-d6ps3kj.gif

narcis_vs tnks for this contest :)

There wasn't any hurry for posting the blog :D

alert("dsjgds");

what does it mean? :)

XSS

Please link converted time

May be i will Miss this contest Due to My Exam

My exams ended 3 hrs before contest. Yay!

is there any contest for beginner problem solving to start practice with ?? HELP

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.

very excited about contest. First time to unofficially participate!!! Hoping to solve ABCD for first time :)

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

Good advice :). I'll probably start from C, try D+E, then go to AB

Also, do you read all of the problem statements before starting to work on any problems?

I want have a good grades in this contest,bless all!

thanks(!):D

I hope the problems have something to do with elegant graphs/dp/trees/combinatorics problems and not some greedy approach with a lot of conditions and corner cases!

Hope the problems will be interesting. Let's enjoy it. :)

this is my first contest

New genius one?

no, i'm not genius

Waiting for a nice problemset!!

good time for contest :) <3

What was the solution of problem D?

I starting taking the LCS of the first and seccond line. And then LCS the result with the third line and ... (LCS calculation was DP — But I called it recursively for the new check).

I got segmentation fault. Does anyone know the reason? Is my algorithm correct?

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

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.I think they should have accepted all of the possible answers.

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_{1}, ...a_{k}}, wherea_{i}means position ofxin i-th permutation. Now you create a directed graph — iff . Now an observation — ifu_{1},u_{2}, ...,u_{m}is a common subsequence, thenu_{1}, ... ,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 inO(n^{2}).Can you explain the graph creating part a bit please , I mean this part .

Sure. Let's look at positions of numbers 1 and 2 in our permutations. {

x_{1}, ...,x_{k}} are positions of 1 (i.e. in i-th permuation number 1 is onx_{i}-th position) and {y_{1}, ... ,y_{k}} are positions of 2.Now we create a graph with vertices labeled with 1,2,...,n.

When

x_{1}<y_{1},x_{2}<y_{2}, ...x_{k}<y_{k}, then we create a directed edge from vertex 2 to vertex 1. In other words, we create such an edge when in each permutation 2 comes after 1.it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

Thank you , a little question though , if the array was not a permutation , i.e there was repeated numbers , could we have solved the problem using similar approach ? I mean can the normal lcs problem be solved like this?

Thanks for nice explanation :)

it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

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

Pretest 2 for problem E seems so strange...... So many people get WA or RE on this......

Div.2 B — find max?

yup

What is the explanation of B seriously -_- . I first thought that it may be the maximum number . But I couldn't prove it. But at the last of the just before 3 min contest I see B was solved more than A , So , I just submitted by calculating the maximum number. I don't know if it is true though.

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.

Problem C?

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

When 1 hours remaining, then my father call me and come to eat pizza..:<

I solved A and B (for pretests) and I try to solve C, but I failed... and time was too short for me(I can use 1 hour..)

Nice contest Narcis and Mircea! I'm a little bit surprised that there are more pretest passed submissions on B than on A (because B was trickier in my opinion). A was very good for Div2. About C I would like to say that it's nice. I liked D the most, because it's really beautiful despite its very simple input. Initially I thought that E is some kind of HLD with segment tree, so didn't try it for long. Got the right idea in the last 20 minutes (some kind of sorting + DFS). Not the most prolific round for hacking though. Anyway, keep up the good work.

P.S.: Caisa is a really nice name for a task hero. Don't you think? (image) I'm curios what does Gargari comes from.

I missed a hack attempt in problem C. At 01:56 (4 minutes remaining), I saw a solution with overflow problem. I then wrote a code to generate worst case of 2000x2000 with all entries 10^9. Submitted at 01:59:57 ... It itself TLEd!... Then it striked that a 2x2 matrix would have been sufficient. LOL !! =(

What a contest! I hacked for the first time!

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

Does anyone know how to solve C?

I precomputed the sums for each position where a bishop could be placed in O(n^2), but I don't know how to find the pair of bishops without checking each possible pair.

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.

Why is this necessary? What if two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other ?

Give me example, please) (When two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other)

Oh sorry, Just realized that is not possible as as soon as you select a bishop , if you draw a line on the board along the square's diagonals , you have divided the board into two halves. Now if you place a bishop in another equivalent square (modulo 2) you have to cross this line which will have an intersection and that square will be attacked by both the bishops.

I have to disagree with you here. Two Bishops attacking each other will have to be in the same diagonal. There is a difference between "two bishops attacking each other" and "two bishops attacking the same cell". The problem statement failed to differentiate between these two. Read this wolfram article. Cell

`(2,2)`

and`(0,2)`

will both attack cell`(1,3)`

but they are not directly attacking each other.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

why so many people get wrong answer on pretest 5 in DIV 2 A problem ?

I didn't)

Well done!!!

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.

Hi, I am a newbie for Codeforces. I found that I was unable to view the results of pretest of my submissions. Everytime I clicked the number linking to the submissions which failed on pretest, the popup was just displaying my source code but no pretest results. And in the direct link of the submission was also just displaying the source. Any can help? Thanks in advance.

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

Does anyone know the second test case of C?

This is very good contest that I participate first time but I could not solve any problems :D

in problem C

change

ll mx1=0,mx2=0;

to

ll mx1=-1,mx2=-1;

Accepted :( :(

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

Same :D

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

I got TLE for using cin/cout :/

I got both the problem :p pity for me -_-

Too fast systest!!

When I saw my ranking it was at 30% testing. In a few (~30) seconds, after I again checked the dashboard, it was 100%. I was expecting it to be around 40 — 60 at that time.

this is unbelievably fast!

Please, could you tell how to count the sum that gives the black bishop using dynamic programming

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

cin/cout gets TLE for problem C and scanf/printf AC ? Seriously ? Nice...

Me too!I want explanation!

`cin`

is like a turtle. Very slow turtle.I agree !! I knew this happens on some OJs, but it never happened to me on CodeForces. Maybe the authors are inexperienced and missed that, maybe they should reeval.

Use

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

Did anyone else too misread problem C as placing bishops such that they do not attack each other, rather than placing bishops such that they do not attack any common cell. I wasted an hour on this before realizing I had misread the problem.

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.

Please publish a complete editorial and update ratings fast :)

Thanks

in problem B wouldn't it be sufficient to find the maximum pylon and print it out ?

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

For Prob A, if the input is

then, he can either buy just one for 2$ 80cents, and get 20 candies in return or, he can buy 2 worth 5$ 60cents, and get 40 candies in return. So, the answer should be 40 candies, and not 20.

I interpreted the problem in the above mentioned way. It was mentioned that he can purchase only one type of sugar, but it was not mentioned that he can purchase only one quantity of that type. I ended up wasting over an hour over this ambiguity.

Am I correct?

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 .

Same here. The problem statement was not clear. I did the same and ultimately was not able to solve this. I do think due to ambiguity of problem A . More people solved problem B.

Same with me! He can buy several kilos of sugar and get more candies for some cases. Problem has incorrect description I think.

Weak test cases for problem E. Even brutes are accepted.

TLE by cin and AC using scanf.

very upset by the contest.

Maybe test cases for problem E were generated randomly.

:( Just changed cin to scanf on problem C an got AC, it's ok to get TLE because of reading method or the most important part is the algorithm and it complexity ??

Si eu la fel :))

problem B is very very easy :D

As a Chinese I do not think there's no difference between "type" and "number".

Problem C got TLE just because of cin\cout.Without it I can become candidate master.Such a bad contest

Me too

Same

Why this solution is wrong? I used DP over bitmaks of set of sequences and looked for the longest common subsequence.

can anyone tell me why i am getting TLE in problem C my complexity is O(n*n) solution code LINK.

Maybe because

cinis very slowYou use cin. It's too slow. I made the same mistake

Nice Round!

it isn't surprising

Stop ZLD! Why you create so many accounts for div.2!

ZLD_submit_for_practice1 OrzSKYDEC hzwerOrz hellp zld3794954

TLE code ::: http://codeforces.com/contest/463/submission/7635306

AC code ::: http://codeforces.com/contest/463/submission/7642386

Difference is only a cin function :( too much pathetic :'(

Same here

Usually this n't happen in CF :( TLE for cin instead of scanf :(

Same here

nice round! +169 expert again! hoho!

congrats IvanJobs :)

Where is tutorial?!!

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

Country Wise Standings has been updated.

The E's system test may be too weak.

If the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time. There seems many AC solutions cannot pass this case.

The data maker by python:

Maybe I am wrong. Please reply to point it out.

Stats about hacks can be found here.

how can i solve C in O(n^2)? the number of black and white cells can be up to (n^2)/2

so.. for white_x for white_y for black_x for black_y

i thought O(n^4) but it seems wrong.. sorry for dumb question and bad english

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

Just got AC, Thanks

How about the following algorithm for C -- (I have not implemented or submitted it because I am way too sleepy and I just can't think, but I would be glad if someone validated this)

1) Pre-compute the sum of all diagonals.

2) For every diagonal, there will be exactly at most 2 diagonals where you cannot place another bishop. Except for these (potentially 2 diagonals) calculate the diagonal which will give you the maximum sum by iterating through all the favourable diagonals.

3) After doing this, simply iterate through all diagonals, and find

`sum(diagonal) + sum(max_diagonal_calculated_in_(2))`

. Output the maximum sum found here.This is O(n^2). Will this work?

The data of Problem E is too weak 7644499 The time complexity of his algorithm is O(q*height) Why can he accept?

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

In problem A Div 2, 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.

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

I am not really sure either.

I really appreciated with fast turtorial bcz some problem seems hard for me to understand. After understanding the div2(ABCD) problems, I wrote the why and how here.

wrote in chinese. Hope useful for the guys like me^_^

In the Div2. C question, I get a TLE when I use cin to scan numbers which is understandable. But when I use fast io for cin, cout; precisely this :ios_base::sync_with_stdio(false);cin.tie(NULL); I get a WA on test1, which runs correctly on my shell though. However, using scanf my answer gets accepted. I have always ignored such fumble. Can anybody please explain me how I can use cin, cout in this case and still not get a tle?

TIA.

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.