Hello, everyone!

Codeforces Round #353 (Div. 2) will take place tomorrow on the 16th of May at 19:35 MSK. I tried to make interesting problems, hope you enjoy them.

I'd like to thank GlebsHP for his help in preparing problems and MikeMirzayanov for Codeforces and Polygon.

Good luck!

**UPD** Scoring **500-1000-1500-2000-2500**

**UPD** Editorial

**UPD** Congratulations to winners!

Div. 2

Div. 1

Good luck and have fun

haha good luck

DIV 2冠军就是我!!!!!!!!!!!!!!!!!战斗吧jibancanyang

i'm looking forward to join contest . i hope i will be succesfull

Yes, I'm agree

Hello agree

Nice reply :)

:)

1

Is it rated?First!!!

My congratulations!

finally ,there he is

مبروك

Can you speak english? PLS!

write to google translate and learn it

مبروك :P

"Congratulations" (Google Translate)

I can write in a language that you do not translate into google translate (-_^)

Congratulations,you must be a real genius.You can write in a language that google translate can`t translate.

karekterli I مبروك you

Hazillashmudim! (It means "i didn't joke")

Haha!

()

:)

wrong answer :) But very near!

What does rated mean? Excuse me but I'm new to this website.

Welcome the CodeForces!

It means that you get positive or negative points depending upon your performance in the contest and your rank changes to Newbie, Pupil, Master, Grand Master ... etc

Currently you're unrated, when you participate for the first time your score is assumed to be 1500, and the points you earn will be added to it

Later contests will add to your actual score

OK I got it. Thank you :)

seems like no one likes you Mr Tweety :3wow. short and good description. hope to see some interesting problems :)

The least words with the most clarity is the best form of expression.

Good Luck... We hopefully, we will enjoy this Round..

komendart and his short announcements

Will Codeforces Round 366 (Div 2) be yours?)

Stop downvoting! I don't want to have negative contribution.

You don't want, but you will have.

.

What is misleading about his response?

.

deleted

He said that for a valid solution, there has to be at least one nut. This means that if there is no nut, there is no solution. It doesn't mean it is guaranteed that there is at least one nut. His response was clear, so you should blame yourself for misunderstanding what he said. :)

"Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut."

I don't find it misleading. This sentence means that it's invalid way if we don't make any breaks and bar hasn't nuts. And this sentence would be excess if it was guaranteed that bar has at least one nut.

Everyone who asked similar question got this sentence as response. By the way, it can be with the same probability my or GlebsHP's response.

I also failed system tests because I was mislead by the exact same answer you got. I'm still not quite sure what I think about it, it would've been easy enough to just answer yes or no to the question, since people were confused and asking directly, but I guess I just also learnt from it, and from now on will always include an if statement for special case like that if I'm in doubt whether it's in the test cases or not.

Best Wishes to All World Final teams. Hope this contest will be warm-up contest for Them.

Simple and clean description :)

I really enjoyed your last contest! Thanks for setting this contest.

Hope for doing much better.

I hope so too

As the description is short and simple , so I think the problem will become very short and simple :)

my first time here , hope to see some interesting problems

I hope you will be successful in this contest

Give me Downvote.........

Here you go!

Hope to pass Div2/C for first time :)

The same thing. Never passed it before :D

Interesting...

I don't have internet connection and electricity in my house, had to travel to another city 3 hours away because of contest. Hope the problems are really interesting please.

You must be really excited about Codeforces :)

It's only a minor contest for most people

If it's minor contest for you, keep it to yourself. Do not discourage others by posting such illiterate statements. It's major contest for all Div 2 contestants who have a chance to increase their rating and eventually end up in Div one one fine day after performing well. !

How can he be so neglectful...

Well, I'm sorry you feel this way. But codeforces is more than a minor contest. It is a community of dedicated and hard working programmers some of which work for some of the best companies in the world.

Before joining codeforces, I had did not know about many concepts in programming but thanks to codeforces I now do and am learning and improving daily.

I made a lot of cool friends here on codeforces and have even been contacted a recruiter through due to my blogging about codeforces.

So no its not just a minor contest for me. It is a chance to train with different programmers from all around the world and enjoy doing it at the same time.

Thank you.

šupak(azzhole)

What is the most important of it? "Interesting!" I hope I can enjoy it with my friends then, though I am a green hand.

Nice and short announcement....fine. :-)

Hope , closing ceremony time will also be as short as the announcement ...... plz

We will rise !

Auto comment: topic has been updated by komendart (previous revision, new revision, compare).My first contest. Feeling Exticed

I think one of the problems is about shortest statement :D Have a nice contest ;)

Scoring should be 500-1000-25000-500-2500 :)

500 — 1000 — 2500 — 1500 — 2500

I think it depends on perspective. I took 18 minutes to solve C, but 50 minutes to solve D. Mainly due to my inexperience with STL. While the idea for C is a bit less intuitive than D, the implementation is relatively more simple.

How to solve problem C ?

Let us note by

T[i] the transfer fromitoi+ 1 in some solution. Then the following equations must be satisfied:A[i] +T[i- 1] -T[i] = 0.for

i= 0, 1, ...,n- 1. Suppose that we knowT[0] =xthenT[i] =A[i] +A[i- 1] + ... +A[1] +x.We can manipulate

xand we want the maximum possible number ofT[i] to be 0. The best choice forxis the opossite of the most frequent number in the pref_sum table.So the answer is

n-kwherekis the frequency of the most frequent number in the sequenceA[1],A[1] +A[2], ...,A[1] +A[2] + ... +A[n].Wow! Nice solution!

What's the value of

T[i]? what does`transfer from _i_ to _i+1_ in some solution`

mean?How to solve C? I was finding maximum consecutive zeros(taking circular queue in consideration) and then subtracting it from n — 1. It gave WA on pretest 5.

incorect:

9

0 0 0 0 1 -1 0 1 -1

correct ans: 2

your ans: 4

i looked for consecutive zeroes that have the same prefix sum and got the best score from: n — number of zeroes with that prefix — number of consecutive intervals. Didn't work, but it does work on this test :(.

cycle array is given. Did you count it?

consider all zeroes

test:

1 -1 0 0 1 -1 0 0 0

answer is 2

Did you see that it was a circular array? :)

Well, I passed pretest, though I don't know if my answer is correct or not. Here, at first we take cumulative sum in another array, say, cum[i], where cum[i]=summation of initial array from 1 to i. Then, we check for the number which has maximum occurence in the cumulative array.Let the number of times it has occured be max. The answer is n-max.

same here!

what is 4th input in E?

We know as much as you!

I'm wondering if there is something very simple we can do for C, or if it was truly as hard as it seemed. Harder than D anyway.

My heart was broken.

Unsuccessful hacking attempt -50

Welcome to Codeforces, land of the trolls.

Very nice problem set!!

Auto comment: topic has been updated by komendart (previous revision, new revision, compare).Wow system testing started just after the contest finished! so fast! wonderful! :)

why I am always forgetting to use

long long:'(You maybe are so excited that you have found the solution, that you don't think about tricky test cases. You just go strait into the code. It's a common mistake. Just make sure you spend 10 seconds thinking about data types that you are going to use in your code when you solve a problem. Spending very little time double-checking your solution is worth getting wrong answer, specially in CF that tricky test cases are not usually included in pretests.

I'm curious, as to what your strategies were for C. D seemed more straightforward but C was so interesting I couldn't leave! Mine assumed that there are four optimal starting positions, and I just looped manually. Most likely my assumption is false; anyway what were your ideas?

I am getting Time limit exceeded on Pretest 6 on Problem D although my approach is nlogn: http://codeforces.com/submissions/Ishan.nitj

Your solution is N^2 in worst case (e.g. sequence 1 2 3 4 5 ... N)

thnks

Very nice contest, the problems were great, especially problem D. I don't know if I have the right solution though (I didn't send a source :( ), I have a solution involving Segment Trees with Lazy Propagation. What was your solution to D?

Hacked 3 times in Div2 A by the same guy... really? Link

:'( It was my fault -_-

How to solve D at all? Treap? How to build BST in O(N)? Or some kind of completely another solution?

No treap

make map of intervals (l; r) -> value at parent list. Initial (0 10^9 + 1) -> -1; 1) read num a;

2) find interval (l; r) -> ans for which: l < a < r;

3) if ans > 0 print ans;

4) add interval (l; a) -> a and (a; r) -> a

Suppose you're adding x. Find a = smallest number bigger than x, b = biggest number smaller than x (between numbers added until now). Now the answer is the one (of a and b) that was added more recently. You can find a and b with a set.

System testing was very fast !!!

Yes, the bad news come very fast :P

Time complexity for 10^9 passed in codeforces judge when I tried to hack the solution in problem A by giving a=1,b=1000000000,c=1 his code was if(c>0){ while(a<b)a=a+c; if(a==b)cout<<"YES"; else cout<<"NO"; return 0; } But when I provided the test case a=-1000000000,b=1000000000,c=1 I got successful hacking attempt.

on servers 10^9 fast operations go for ~0.8 seconds

I also hacked a solution for TLE, but before doing so I used the Custom Test Tab and saw, that

`1 1000000000 1`

gives`Used: 561 ms, 2036 KB`

, whereas`-1000000000 1000000000 1`

gives`Used: 1123 ms, 2036 KB`

and since time limit was 1 second, just the larger test case is valid for a hack.Problem C looks very similar to SRM683 Div1 Easy, O(n) Solution for that problem can be found here. The solution for this problem is also similar

Problem D was minor change from a recent HackerRank contest problem, which in turn also appeared in India IOITC 2015 Test 1, and also in some iteration of the COCI(saw it on PEG Judge,

~~not sure which olympiad~~).EDIT:

COCI, not CCC, my bad.

HackerRank version

COCI08 #3 BST

India IOITC version

Also on SPOJ, wow

Is the contest unrated or we just have to wait some time for the system to update?

Why does this code

doesn'tgive RE on 10 10 0?Division by zero (temp % c)

Maybe after seeing that temp is zero (temp%c), the rest is ignored, in the same way while(!q.empty() && q.front()==0) doesn't give RTE because if q.empty() is true, the check q.front()==0 is ignored :)

But it

doesn'tgive RE on test 0 1 0 also!You may not write ( number % zero )

I tried to hack but couldn't because this feature needed flash player. Seriously? Who uses flash player anymore??

Other than that very nice contest. The problems were challenging, and I really enjoyed it although I didn't have time to even read E :D

Is the contest rated or unrated

It is rated. I think they are finding the cheaters, my rank just decreased by 2.

My hacking attempt on http://codeforces.com/contest/675/submission/17938245 failed for testcase

`1 1000000000 1`

because the solution produced correct answer in`826ms`

. So close but yet so far.`-1000000000 1000000000 1`

took`1450ms`

. Should have tried the largest testcase.When do colors change?

It's already done

Hi Friends I am sure this a trivial question, but it would be really nice if someone could look into this. I gave these two submissions 17956219 and 17953624 for problem B div 2. Both are identical except using long long and long data type. But the solution with long gave wrong answer for

What could be the reason for this?

long = from -2 147 483 648 to 2 147 483 647 long long = from -9 223 372 036 854 775 808 to 9 223 372 036 854 775 807 I made one hack using this

Overflow is the reason. The answer may be 10**10 if sum=10*5 and the number of number that can be used is 10*5. Long data type stores 4 bytes of data whereas long long data type stores 8 bytes of data and 10**10 doesnt lie in the range of long data type. Thus an overflow occured and thus your answer was wrong.

the variable is long long ，but you define int.

What a TLE!

I used the generic

upper_boundinstead of the class specific 17957229 vs 17957298To have into account in future implementations.

Generic upper_bound on non sorted random access containers takes O(n) time. Protip: google C++ upper_bound.

Yes. In fact I found that reason after google a little bit, then I corrected it. I wasn't aware of that.

why in the result table some cells have a color background? http://prntscr.com/b4vv80

and others are red http://prntscr.com/b4vw4r

Because. You was be in the same room with them and you looked their solutions to hack. So green color shows that you look this solution and maybe red color means that it is the last solution you check for hacking.

Yes, I check and they are both at the same room with me. Looks like you're right, thanks!

Thanks a lot for your efforts and interesting problems :)

Why ALL my AC code was skipped?The solution gets accepted after resubmitting! Since I didn't use other accounts to submit the same solution or copy others code, how can I ask to retest my code.

https://community.topcoder.com/stat?c=problem_statement&pm=14174&rd=16653

Great DP in Problem E. It makes proper use of Greedy Algorithm!

A splendid round!!!But why not have some weekend round like before?It's really difficult for those students in other regions to get up after 12 during workdays.All in all,just suggestions.

Can someone tell me why using array to build BST causes Runtime Error?

I feel a little confused,and my submission was here

I watch others code which use the similar way and find that they also got

REintest4input:

`10 991309218 517452607 870021923 978357992 136426010 10601767 302627526 883615372 163475700 600546765`

Eh, I have not studied BST nicely(one more reason to concentrate in classes :P) but I think you are trying to make a tree using array which will require 2^n space(here n<=100000).

The use of unordered_map in problem C leads to a TLE . Why is that ?

Hashmaps have the worst case runtime of O(n) when elements get hashed to the same value multiple times.

Please post the Editorial.

Look at the post) http://codeforces.com/blog/entry/44902

WTF why is Problem D statement not available in English?

Also there is some draft version of Russian statement in this problem. I suspect that this is somehow connected with https://codeforces.com/blog/entry/45198

MikeMirzayanov, maybe you should look at this. Statements in "Scraps" link in Polygon are probably correct, I don't remember