Hello!

Soon (on June 8 at 19:30 MSK) you are lucky to participate in Codeforces Round for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaly (gridnevvvit) and Danil Sagunov (dans).

We want to thank Gerald for help in preparation of this round, Delinur for translation of statements and MikeMirzayanov for marvelous Codeforces and Polygon systems.

Scoring will be next **500 — 1000 — 1500 — 2000 — 2500**.

Contest finished, congratulations to winners!

Good Luck!

Hope this round to be a bridge to be a div1 contestant for the first time , just hope

gl & hf

another hope not back to green :(

you will be down by around 95, so not green :)

how do you calculate the rating change ?

Why does my 6839434 for A fail?

Because you have WA

you break out of the loop but you don't handle the rest of input in that loop

Ex: 3 50000, 1 50000, 3 100000 1 110000, 3 120000 110000 120000,

Your code it will read it as if the 3rd k = 110000 because you break after the 1 in the 2nd

Because you used break;

So, you did not ignore the remaining entries of that seller, and the next entry (which was to be ignored) was taken as the number of products with next seller and that ruined your code. your code works fine iff either no one has cheap product or only last product is cheap.

fixed 6850039

Thanks, guys!

Good luck with preparing your second contest , Keep going for more =)

and I hope that the problems and the editorial will be reach with new and useful things to learn

This round is not second. This round is the ninth my round

The 236 round was your first round for both divisions and not your first round for Div2 only , now I see

thanks for clarification =)

Are there many hacks?

You rating curve is so interesting~

Hope everyone good luck and success for the this contest

can any one give me the links of other contests DIV2 made by gridnevvvit :) thanks

http://codeforces.com/blog/gridnevvvit

I have never been able to solve Div-2 C type questions during contest... I hope i do solve it this time :) Good luck everyone

start with C. This worked with me, hope it works with you also.

very nice suggestion :)

I guess that someone black will win this round again.

249 div 2 only

247 div 2 only

UPD: yeah, I'm right.

I think they are people which already have an old account at Codeforces but they just build a new account to become candidate master in 1 contest!

let them

I think making another account to compete in a div2 contest and be from top 10 ,that's the result of competing at div1 and lose every time or you can't make a significant score so you leave the real competing at div1 and try to stretch your muscles on a div2 players :)

Black? Dat's racist.

I don't think that what he was aiming to . Black is the non-rated contestant as he didn't enter any contest just as the color of your account

And give me a break , you are putting Hitler photo and talking about racism ? =D

I think

Hey, It's Hitler himself, Not just putting his photo.

A question: Why everybody says that the scoring will be announced later?! Couldn't they publish it earlier?!

http://codeforces.com/blog/entry/12378#comment-170490

Thanks :)

please upvote the above.

NO.

so mainstream ;)

give me '-' pls

Sure. ^_^

I think that's a bad idea according to amount of trolls around :D

Gd luck every one, hope I rise my rating this time :3 :D

Great round! Pretty interesting problems :)

Very hard D and E :(

Statements was unclear.

What thing is unclear for you in the statements? I will try to do better statements in the future

A problem, i read three times to understand statement. B problem, i didn't now is possible to collect any number of fruits(<b[i]) or you must collect all fruits from this tree.

Did you find the exit you asked for?

oh, i was nervous,i have made stupid mistake in A problem(i set INF 10^5 instead of 10^6)

wasn't unclear ... just a little bit hard to understand . ;)

yaap... statement was not clear to me too... :/

but the notes after each problems helps me a lot... thanks to author for that... :)

I agree, notes was useful.

How to solve problem D?

There were a few key points :

1) Number of swaps needed to make a permutation an identity permutation are N-C, where N is the number of elements and C is the number of cycles in the permutation. This can be proved using the statement 2 and 3 below (that it is unoptimal to swap outside cycle) and that a cycles of size M needs M-1 swaps to be sorted (provable by induction on M).

2) Swapping two numbers in the same permutation cycle increases the number of cycles by 1. This can be proved constructively (take a cycle C, swap two elements and see that two new cycles are made.)

3) Swapping two number from different permutations decreases the number of cycles by 1. Again, constructive proof.

We have some number of cycles in the given permutation P, and we need N-M cycles in the target permutation Q. Hence keep on making an inter or intra cycle swap depending on which is bigger; and greedily choose the smallest index for lexicographically smallest solution. Complexity

O(N^{2})The problem is tagged with disjoint-set unions. How can dsu's be used in this problem? What I did was to calculate the new disjoint cycles of the permutation resulting from every optimal intra/inter cycle swap.

DSU can be used, for example, for joining cycles to cycle containing vertex 1 (The first case in editorial).

Can you please provide a code where you have implemented the above idea ? Thanks.

Here is my implementation of the above idea, as requested.

How to solve B?

you must sort your trees by days and then model situation

i stored the number of fruits on tree

`i`

in`pp[i-1]`

and then iterated from`0`

to`n`

, picking as much fruits as possible. this is the submission http://codeforces.com/contest/441/submission/6845290 why is this approach wrong?Because you are summing the fruits you can collect to the Nth day...

Here in your code — Line 22 :

Should be :

UPD:That is one of your mistakes, but not that you got WA for.Did everyone run the loop till the maximum day value for problem B? :P It was a pretty good hack.

so what is the good test to hack them?

For example: 1 100 3000 200

Till max day + 1 of course :))

Yes, till max day + 1 :D The best way was to run it till <=3001

Good hack.. But in my room almost everybody run till <=3001 :) I have hacked only 3 submission.

Well, I ran till N :) Nobody hacked me, and I failed just on 26th test. How unfortunate.

system testing is faster than usual .

Hope that the rating system's to!

congrats for that

I'm new to CF and I read problem E first...

I'm old to CF and I also read problem E first...

what was the correct way to solve DIV 2 B problem.i approached by first solving for day[i-1] and then for day [i] ...but got wrong answer on pretest 5 http://ideone.com/mWCTzM

at first you should sort them by day.

have three integer variables

`curPicked`

,`prevDay`

and`curDay`

. Then try to pick as many fruits as possible from the trees of`prevDay`

and`curDay`

while making sure that`curPicked<=v`

.In my solution I created an array of 3000 elements for the days and for each day I saved all the different amounts of fruits that can be gathered on that day specifically. Note that the order doesn't matter.

then it's just a matter of using the above 3 variables and the array effectively while taking care of the corner cases.

Total time complexity: Θ(max of n)

Some days may be missing.

I see no reason, why you assumed that only for any particular day x, only one tree will have fruit at that day. Given your piece of code,

`day[st[i].day]=st[i].cap;`

.my mistake...at starting i remembered it but at last i forgot it.. AC by changing to day[st[i].day]+=st[i].cap; :'(

corrected...the days were repeated...did'nt noticed it just changed day[st[i].day]=st[i].cap; to day[st[i].day]+=st[i].cap; and AC :'(

same for me

waiting for editorials....

me too

Problem-C : Code implementation finished....contest 1 min remaining , when compiled--- several errors . After correcting errors...15 sec remaining>>>> finally, couldn't submit during contest !!!! Bad luck.. Anyways, contest problems are nice :)

Yeah. Finally solved three problem again..

Thanks for this round... :)

what about editorials?

after solving probelm, A I could have solved problem B but I went for E because I found it really interesting but i failed to solved it in the end. Was it a wrong decision?

yes

Can Any body tell me where is the main differnce between those two codes..???

I use max value for the last limit for first one. And Use 3000 as last limit in 2nd one... Why I got WA... Cant find it.....

I guess in the first code, you can still collect fruits that became available on day 3000, on day 3001, which you never visit, the second code, allowed for this case to occur, by having +2 beyond the maximum day.

Thank you.... Feeling like i am the biggest idiot in the world... thanks for pointing the mistake out....

Edited code of your first one : 6849997

just written

`3001`

instead of`3000`

. Hope, you have got the point.Rating is

`Updated`

I have a bad day , i had WA on test 1 in problem C because i was use printf %d with a long long int without noticing , i don't know that it really cause many problems , in my local compiler the answer was the expected but in codeforces test no.

Hope to back ( green ) soon :)

That was a really fun round, thank you gridnevvvit!!

i_love_gridnevvvit Why unrated?

Anybody help me out with C?

I tried solving the problem greedily

we need

`k`

tubes, each with size`>=2`

. Now`k-1`

tubes will be of size`2`

and the remaining points will be the last tube. However I didn't have enough time to figure out how to print the final tube in a way that satisfies the condition`for any integer i (1 ≤ i ≤ r - 1) the following equation |xi - xi + 1| + |yi - yi + 1| = 1 holds;`

I made it that way :) 6844587

I did it the same way. But got TLE.

why the hacks list is not shown yet ??

Edit: Now they appeared :D

Would you please tell me what is wrong for this code? It is for 441B — Valera and Fruits :

http://codeforces.com/contest/441/submission/6850959

Got it!, this is not optimal, because I should go for the trees that are getting rotten first.

Problem D was very nice for me; guess I learned about permutations solving it more than my recent abstract algebra course :D though I couldn't manage to debug my code in time :(

Thanks for the round!

Not sure what is wrong in — http://codeforces.com/contest/441/submission/6844819

I am getting the correct answer while running on 'GNU GCC version 4.7.2'. Please let me know.

Replies please

try to initialize the variable "selected" to Zero at the beginning

ohh I am sorry I wanted to give an up arrow and clicked down instead. I will change it .

Thanks a lot it works now — http://codeforces.com/contest/441/submission/6855224 Can you tell me what was the reason. It worked good when I tested in my compiler. Thanks again hellcoder

Round Stats

P.S.Take a look on the match winner(kuangbin10)and these accs:kuangbin9 kuangbin8 kuangbin7 kuangbin6 kuangbin5 kuangbin4 kuangbin3 kuangbin2 kuangbin1 kuangbin

6844888 I don't know why I get WA on test 11,I think my output at least in this test is correct.

Oh,I am sorry,I didn't understand the meaning of the problem C last night.

Me too, I didn't understand the problem C

I solve the problem B with O(n^2) (for 1 -> max_day {for 1 -> n}). If have test max_day = 3000 , n = 3000 then it will work O(3000*3000) = O(9000000), but it not TLE. I am surprising about this. Because this, I hacked some people with test 3000, 3000 and all unsuccessful. I am sad about this

9000000 operations it is very small amount to recieve TL.

gridnevvvit , O(10^6) works in 1s ? If not, how much second for working O(10^6) ?

Yes, it works. see my solution: 6850502

Thanks much !

Why can't I vote twice on a comment. It may happen that I voted somebody down by mistake but now I want to revert or give up

You can only vote once on a comment. So as need think carefully before vote for 1 comment. Good luck !

can we not have a feature to change the vote