Hello everyone

On Monday, December 19 at 19:35 MSK held Codeforces Round # 388 for participants from the Div.2. Participants from the Div.1 may participate out of the competition.

This round was prepared by Denis pitfall Bezrukov, Alexey dalex Dergunov, Vyacheslav Slamur Muravev, Egor Petruchcho Ponomarev, Pavel craus Semushin и Andrey Shlakoblock Gaidel.

For me and Slamur and Petruchcho this will be the first round. We hope that everyone will find interesting problems.

Great thanks to Gleb GlebsHP Evstropov for his help with the contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

**UPD:** You will be offered 5 problems and 2 hours for solving them.

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

Congratulations to the winners!

Div.2:

1. just29

2. tnbt

3. el_smurfo

4. SimB4

5. skydog

Div.1:

1. I_love_Tanya_Romanova

2. W4yneb0t

3. enot.1.10

4. gritukan

5. Um_nik

**UPD:** Editorial available here

It is incomplete without this. ** ** *****?

Yes, it is rated.

Why does the guy who answers that question get upvoted? Anything can happen on CF. :/

He is the writer, that's why :p

LOL didn't see that. Forgive me Master pitfall ! :P

Can one please help me As Scoring: 500-1000-1500-2000-2500 But whose rank is in be 2000 to 2200 Got negative ratings Please explain

Before updating your rating after the end of the round, for each participant his seed is calculated, that is the place that the participant is expected to take in this competition. Thus, two things are known for each participant — his seed (the expected place) and rank (the actual place). Depending on the difference between these two values, your rating increases or decreases. If the difference is higher, your rating changes more.

You can read more about it here: Codeforces Rating System — Codeforces

Fixed: It's held at the unusual usual time.

No, it is held at the usual unusual time.

It would have been much better to have these contests on two different days this week instead of having 2 contests on the same day and then not having any contest till next week.

If this is the time chosen by the CF management, there must be a reasoning behind it.

Acctually Codeforces round 386 and 387 is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. But the Codeforces round 388 is an usual Codeforces div2 round. That's why we have 3 contest in just under 24 hours, the first 2 is like mirrors of the Olympiad and the last is the usual round.

Time is usuall but nember of problem isnt : (

A previous contest had very fast system checking and rating changes. Hope this one will be the same! Though it is so unusual to write contest in the morning and then on the same day at the evening =))

Hope I will not repeat my usual mistakes and solve first three problem ASAP. Maybe life is nicer as Blue.

All the best !

Thank you. But It didn't happen. C was easier for me than B, but B eaten all the time :(

It will be!

epic comment :P

thx a lot for these consecutive contests (#388,#387,#386,#385)...it helps our ACM team for ICPC-Tehran Region

Wish me luck! I'm at only 25 points of Div. 1. These 2 days of contests have favoured me.

Good luck! And I wish I can be the witness^_^

Just 3 points, fighting!

Oh, you got blue! Congratulations!

Thx :D

Perfect time for programmers from Bangladesh :)

There are a great many of contests in the end of term :D

Expecting interesting and doable problems.Thanks

Codeforcesfor organising so quick rounds and really appreciable work done by all the problem setters.All the best everyone!!! :)Good decision the number of problems decreased to 5! (Pennyroyal_Tea this is not factoriel). thanks

I guess even tourist can't solve 120 problems in 2 hours, so 5! is too much I believe.

The joke is cold haha

You never know , he is GOD !

Hope not to drop after doing well last contest.

my 3rd contest on CF in 30 hours!

Good luck everyone ! Hope everyone gets what he deserves !

and now the pleasure comes to it's end...

I wish this contest will be great for all of us

I think, this is my first time when I Submitted 3 code, all got pretests passed. I hope it stays as good. I gave up on problem D and E.

Actually 5 submission, but the other two was wrong programming language, and forgetting reading input which make it fails on the first testcase.

lesson learned, if you hardcode the problem testcase: don't use the first example.

Don't give up yet!! You can do it!!

Also the first time for me by solving A,B and C!All three passed :D

Can someone explain problem E's statement?

First time solved 4 problems. Hope they will all pass :D

Your rating will go up like a rocket :)

Nice rating change :D Congratz!

Thanks :D

Look at your new rating color! Anyway, nice rating graph :)

congratoulation ✌

Bbye Blue

Was Blue for less than a day. Back to Cyan for me now!

You will be back to blue soon!

What's the C hacking case was please?

Mine was:

`21 DDDDRRRRRDRDRDRDRDRDR`

What should be the answer?

Answer is R

Why is it R?

I explained here

My answer is D

UPD: wrong

Yes, it's wrong.

`21 DDDDRRRRRDRDRDRDRDRDR`

: here first 4 D's will beat any 4 R's but one R in first R's group will stay anyway. So, after each full iteration we will have this sequence of state:`11 DDDDRRRRRRR`

=>`4 DRRR`

=>`2 RR`

, so R is winner.could you please explain test#21 of this problem? (7 RDRDDRD) i am getting R in this (correct is D).

RRDDRDRRDRDRRDDRDDRDDDWhat is answer?

The answer is R, isn't it?

Yes

What's the correct output?

What is the answer for that?

Well RIP my C :(

mine too :)

Hack case for C

:( :( :(

I think I will lose around 50 points.. I checked my program for B on wrong input, thought it was wrong and resubmitted it again.. Turns out it was correct earlier.. Lost 300 points, and fell 700(!) spots on the standings... :(

Very interesting contest, thanks to pitfall

Who else tried to simulate C? Worst decision of my codeforces life -_-

I got passed pretest with simulation.

I did... It was passing pretests with 998ms. So I rewrote it and now I realized my rewritten solution is wrong.

And I didn't even finish my first solution ;_; . Linked list and shit. I knew it was a hacking problem, so simulation felt safe. Never again would I ever again.

If you simulated using a queue, it was easy and fast. (And correct, I hope)

Queue didn't come to mind sadly. Sets take a lot of time to erase( from previous experience ), so I jumped to linked lists ;_;

You could simulate and even afford an extra log factor(I did this and got 778 ms main tests) for total O(n lg^2 n)

I used simulation and got Accepted

I simulated it, but I used next array (using DSU) to avoid TLE. Which is to jump over the cells that are already deleted. 23151066 my run time is 15 ms because the complexity in total is O(n).

I used simulation on input array with two pointers and bool array of deleted and got AC. You won't get TLE cause it's O(n*logn). 77ms in my case

I simulated it. I used two

`set<int>`

and`lower_bound`

in them. 23155161.PD.: Sorry for my horrible English.

I'm simulating using list as well, (well array because python doesn't have native list, but it behave like list)

Solution to B could easily be found on google.

Seems like editorial for problem B is published even before starting the contest. :3

Link

Finding vertices from midpoints of sides of a triangle.

Can someone explain why this interpretation of E is wrong?

Choose the segments: [2], [3], [1], [2, 3], [3, 1], [2, 3, 1]

For the first three, there is 0 chance of an inversion. For the fourth and fifth, there is 1/2 chance, so the expected value from those is 1/6*1/2*1 = 1/12. For the sixth, you can have [1, 2, 3] = 0, [1, 3, 2] = 1, [2, 3, 1] = 2, [2, 1, 3] = 1, [3, 2, 1] = 3, [3, 1, 2] = 2. So the expected value is 1/6 * 1/6 * 9 = 1/4.

Isn't the answer then 1/3?

You permutate the smaller segment but the whole array still exists.

It didn't take me much time to solve ABC, but failed to figure out the last two

I know that feel, bro. I hope we don't fall in our ranking

if your C solution is just deleting the first undeleted instance of opposite party (which apparently passes pretest) then it can be hacked. My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1, pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D.

What should be the correct answer?

How can the answer be D?

My answer is R, btw.

And I use the 'wrong' algorithm.

UDP:And I passed the system test.Everyone here seems to misunderstand what he meant. He said the first undeleted instance not the next one.

My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1,If he meant the next undeleted instance, he would write "pos 2 kills pos 3" and so on.pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D.My solution is just deleting the first undeleted instance of opposite party,

and it PASSED the system test.

How solve E?

Consider positions i and j, then element at pos-j can be less than element at pos-i only if we choose a segment that covers both i and j and then choose an appropriate permutation.

Suppose we fix the segment, then above prob = P(for any r-length segment) = (put j before i if i is placed at pos=k) = 1/r*(sum(k=1..r) (k-1)/(r-1)) = 1/2.

So, just calculate number of segments that cover positions i and j(for all i,j) and multiply overall by 0.5.

1. For i<j a[i]<a[j] we have sum P=(i+1)*(n-j)/(n*(n+1)) to our final result.

2. For i>j a[i]>a[j] we have to sum P=1-(i+1)*(n-j)/(n*(n+1)) to our final result.

Both can be done similar to finding inversions either using divide and conquer(like my solution: http://codeforces.com/contest/749/submission/23156836 ) or BIT for O(n*log(n)).

linearity of expectation

for a pair

i,j, such thati<jthe probability ofjbecome more thaniispwhere , so ifa_{i}<a_{j}, addpto answer else add 1 -pto answer. To do this inO(NlogN) , use bit.Can you explain a little more? i and j affect other indices as well. Can you show that linearity is justified here?

No more contests? But I got used to these consecutive contests :(

They were really fun though, thanks codeforces :)

How to solve C without simulating it?

Actually you have to simulate it, but in an efficient way. One way is to use queues, you can use, 1 for all people who is available to vote, other for people in R and other with people in D. The trick here is to realize than in every "iteration" people alive is greatly reduced.

I was trying D with square root decomposition. In each bucket, I maintained how many times a number is occuring in cnt[bucket][x] and tot[bucket] is the number of elements in this bucket. Finally start from last bucket and if count of numbers (given in query) in present bucket equals to the tot[bucket], then this bucket is useless and go to bucket-1. I couldn't submit and check though. Has anyone done like this?

Link to code

D was awesome ! However, I couldn't finish it's coding before the contest ended. I was using segment tree and storing bids in it. Was I going in correct direction ?

YES :D. I use the same solution :)

How to solve D?

i used parallel binary search but i guess its probably overkill

I used the following approach.

Let's insert every people into set. And just delete peoples in query when query comes. Now last element of set is people who won. And now you can erase last element of set and find money. After everything is done you should insert everything you deleted.

Did this solution passed system tests?

yes

Sir I used the similar approach but i m getting TLE (Time Limit Exceeded)

I inserted all auctions in a map with keys as the amounts (since they are distinct) I stored all amounts and auctioners in two arrays(named as arra,arrp) to store sequence in which the auctions were made.

Now in each question, I deleted the k elements and on deleting each one of such k element , i check the position of this deleted auction in arrays arra and arrp .Let it be pst. Then i check if pst-1 and pst+1 have same auctioner. if yes i delete the auction at pst +1

I m getting TLE . This is my code

How did u check the condition if we remove an elemment its prev and next may be same How to remove right one?

Even if we ignore that for q questions we are inserting k elements in the set or map each insertion/deletion taking log(n) time giving total time complexity of O(q*k*log(n)) where n <= 200000 and q<= n and k <= n will this approach satisfy constraints?

You are deleting all of k people's bids, which can be equal to n some times if you sum the number of bids for each k peraon. This way there can be a test case with 2 people, each made 100,000 bid, and 200,000 queries asking you to delete these 2 people.. this way the complexity will be O(n*q*log(n)) which is too much.

Then sir what is the correct approach?

You must keep only one version of each person (only the last bid) and sort them by their last bid in a set for example. now if you remove the k people deleted, then the total complexity for all queries will be O(x * log(n)) where x is the sum of all k s which is at max 200,000. After removing the k people, the person who won is in the end of the set. To determine in which bid this guy won, you should have a vector for each person which his bids. You can do a binary search to find the answer. now before moving to the next query. Add the deleted people back to the set. also total of O(x*log(n)).

i used a set to put every person's "best" bid in it. i also made sets for each individual person which contained all of their bids. Now for every query , i traversed the bestbid set from end, when i found the bestbid whose bidder is still available (to do this i used binary search on all bidders who didnt come). the bidder no can be known using this,let him be y.but the bid maybe lesser than the bestbid of this person,so i again travelled the bestbidset to find another such person who came. if his bid was x , then i have to search bid greater than x in y's bids.i used lowerbound for this purpose.i use x=0 if no x is available.

why does this code passess while this does not for problem B? I only used 'cout<<3<<endl' instead of 'printf("3\n")' in the pretest passed solution :/

You shouldn't use printf with ios base synchronisation turned off.

The order between printfs and couts has no guarantee

Because you use

std::ios::sync_with_stdio(false). If you use this line in your code then it's better not to use scanf/printf. It will be a mess because iostream and stdio can't sync thus the order of output won't be same as you expected.bummer i didnt know that i only saw on a blog of cf that it makes cin and cout as fast as scanf and printf and thats y i was using it just like that :(

C test case 21 anyone? :(

Extremely fast system testing...

Wow this system testing was faster then the time it took me to fall from expert to specialist

The C is easier than B, but I failed C.

`:P`

In my opinion, B was much easier.

My solution C simulating statement is accepted. is there any solution without simulating?

In problem B, Test Case 4:

1000 1000 -1000 -1000 -1000 1000

Ans shouldn't be 3?

3 1000 -1000 1000 3000 -3000 -1000

-3000 and -1000 does make a parallelogram with other 3 points, doesn't it?

Yes it does.

My silly mistake. Stupid I am. :|

For all case answer will be three and one can easily get the solution in google.

A little bit changed in problem would be better.

Is it just me or was the system testing really really fast ????

:)

Yeah, I`ve also noticed this

Hi guys,

Could anybody tell me where is the editorial for the problems? Got stuck in C.

Thank you very much!

It's not posted yet but U can look at my solution here if U want...my code

:)

So what's the real solution for C please , I'm pretty sure i'll be around 1899 because of this C haha.

I used a queue to simulate..

You can use set to simulate the optimal moves.

The solution I used is

`O(nlogn)`

. The current candidate removes the next voting candidate of the opposing party. Use`std::<set>`

to keep track of available voters.I kept two treesets (ordered sets for c++) holding the indexes of each R and each D. starting from 0, I simulated each D skipping the next valid R, and each R skipping the next valid D. What I would do is delete them from the tree set when someone was skipped. Additionally, Tree sets allow you to query the lowest number greater than a given index in log(n) time. So my solution was O(n*lg(n))

I think simulation is the correct solution. It can be proved that after each step, the total no of non eliminated voters will be at least halved. That guarantees atmost log(n) steps of the simulation. Using queues the simulation can be done in linear time. So the overall complexity is O(nlogn).

The pretests of C are very weak

When you finish your code and it gets AC just after contest ... :(

lol i understand that,it happened to me twice today ... mrning and night :(

that is better than not getting the solution

Great! Two contests and I was first in my room in both! :)

Today is definitely my lucky day...

What the ***k is going on C on 21!!!

7 RDRDDRD How the ans is D for this case ? :/

R at pos 1 will ban pos 2 from voting.

R at pos 3 will ban pos 4 from voting.

D at pos 5 will ban pos 6 from voting.

D at pos 7 will ban pos 1 from voting.

Now string is RDD.

Pos 1 bans pos 2.

Pos 3 bans pos 1.

So D.

RDRDDRD

INITIALLY R-1,3,6 D-2,4,5,7

POS=1 R-1,3,6 D-4,5,7

POS=3 R-1,3,6 D-5,7

POS=5 R-1,3 D-5,7

POS=7 R-3 D-5,7

POS =3 R-3 D-7

POS =7 R- D-7

ANS D

everyone will play optimally.

RDRDDRD ->R.RDDRD ->R.R.DRD ->R.R.D.D ->..R.D.D ->..R...D ->......D

hope you understand.

find difference between this two solutions:

http://codeforces.com/contest/749/submission/23151466 http://codeforces.com/contest/749/submission/23162519

except that they are stupid

jury take a long time to check your solution , jury's problem

Why RE36? Problem C

link

S1.erase (pos); u[*pos] = 2;

You are deleting the iterator before accessing it.

Okey, thanks)

can someone say why in C : 7 RDRDDRD must be D ? i traced it and found it is R

R at pos 1 will ban pos 2 from voting.

R at pos 3 will ban pos 4 from voting.

D at pos 5 will ban pos 6 from voting.

D at pos 7 will ban pos 1 from voting.

Now string is RDD.

Pos 1 bans pos 2.

Pos 3 bans pos 1.

So D.

First two R-s kill their neighbor D-s.

It turns to RRDRD, where the third D is about to vote. Next you expell the fourth R -> RRDD, the rightmost D is voting.

RDD -> D wins

mmm, now i see, i didn't think that killing the 1st unkilled instance would make a difference

In problem C, many submissions fails with test case:

8 DRRDRDRD

answer is R ??

yes

Almost TLE (**1996 ms**). http://codeforces.com/contest/749/submission/23157019

Lol...the system testing was fast so I guess CF will take its time on the rating change :D

They didn't..

nice contest!

Wait, what?

"Became Expert" instead of "Became Candidate Master"

"Became Specialist" instead of "Became Expert"

Update:ok, it was fixed. :-)My solution to problem C

keep 4 variables how many D's are left ( cntd ) , how many R's are left (cntr) , how many D's will be removed (remd) and how many R's will be removed (remr) also keep a boolean array (ban) to know if the current char is banned or not.

now iterate over the string if you found a 'D' you check first if it is banned or not , if not you check the variable remd which is incremented when an 'R' is encountered if remd was zero this means that the number of 'D's to be removed is zero, so you survive this round and also get to vote to ban an 'R' so you increment remr (so that next time you iterate on an 'R' char you ban it and decrease remr since you already banned one 'R' )

you keep repeating this while(cntd && cntr) so you will exit the while loop whenever the number of R's is zero or the number of 'D's is zero

then its easy to determine which party have won if cntd ==0 then 'R' won otherwise 'D' have won

my submission link : http://codeforces.com/contest/749/submission/23153380

Similar solution

pitfall Plz reply, Why am I skipped?

becuase you are cheater!

You sure about that?

possibly because in any of your submission your code matches with someone else code if it happens even in one problem only then also your contest is skipped i guess you shouldn't try to cheat next time

problem D today... let's do a binary search.... ohh... let's do that again... just one more time :3

hahaha .. true that

Guys help. my compiler shows right answer but displays another answer on judge's compiler. why is that ? am i submitting my code using the wrong compiler ? my code

Is there any variable that is used uninitialized? Different compiler on different machines will assign different values to those variables;

You'll see the true code from pitfall. Just wait.

My compiler does not even allow it to compile, because

Variable rf is not initialized, so it gets a rubbish value which can be 0. thus rf = 0 => no while loop => !rf is true => printed answer is D.

Thanks!

I can't find bug in my code. According to other contestants my algorithm is OK, but it contains bug. Can someone help me please?

LINK: http://codeforces.com/contest/749/submission/23159913

Line 59:

Cur + 2 is incorrect. There can be more than one bid of same person after mid value. Check this case:

I know, but (this) second binary search just needs to find the second not deleted element. It doesn't matter if it is from the same person as first binary search. And I think, that my answer to your test case is OK (my program outputs 1 3).

UPD: Thank you very much, now I understand what is the problem.

Dealing with an odd issue with problem B my solve is here https://paste.ubuntu.com/23655011/ it's showing every thing ok in my IDE but showing less output in codeforce

Input 0 0 1 0 0 1

my IDE output 3 -1 1 1 -1 1 1

codeforce output 2 1 -1 1 1

remember the order doesn't metter

Same, changed set to map and got TLE(yet the output was correct)

std::set contest :(

I think there are like 5-7 players from div1 with fake accs in top10 of div2. Is this legit? Why are not such people get banned?

The only important thing in this site is learning. If someone's first priority is high rating update then why should we bother? We need to concern about how much we learn new things from every contest and can apply them in the future. May be banning them is a solution but its not the best solution. Cause there will always be fake ids. So just ignore them and keep focusing on learning new things. Thanks :)

Missed

Dbecause of not checking if the lower_bound exceed the range. Such a disappointment :(Ummm...tutorial???

:)

Regexing in C — 23162742 (more readable version — 23154376)

Can one please help meAs Scoring: 500-1000-1500-2000-2500But whose rank is in be 2000 to 2200Got negative ratingsPlease explainYour rating change depends on your position in the standings not on problems scores .

If your position in the standings was better than your expected position(you can sort the registerants in the contest by rating to get an idea of your expected position in the standings before the contest starts) your rating increases otherwise it decreases .

Hoping some C++ expert can help me understand this issue.

Here is my submission to problem D: http://codeforces.com/contest/749/submission/23158205

Strange behaviour

1. It fails for 2nd query on #56. If I run the code on local, I observe the 2nd query is indeed answered correctly.

2. It fails on #56 when C++ 11 is chosen, but fails on #54 when C++ 14 is chosen.

My local env:

Apple LLVM version 8.0.0 (clang-800.0.38)

Target: x86_64-apple-darwin16.1.0

Thread model: posix

Mac OS sierra 10.12.1

Deleting iterator/element from map, then using its values like a boss? Slight changes makes it accepted: http://codeforces.com/contest/749/submission/23164706

Hey, thanks !!! Should have noticed it.

Can anyone provide me the test case 54 of 749C - Voting or any shorten form of it ?

23166401 and 23166364 are nearly the same. Yet one passes and the other fails on testcase 10! I believe that the largest difference is the use of vector reverse in the failed submission, but how would this matter?

UPDATE: I found you've reverse the relationship so what I said was wrong , now I didn't see what's wrong either.

UPDATE2: I was stupid and compared with the wrong submission number, actually you did forget to reverse the binsearch function

Oops. Thanks!

DIV 2 PROBLEM D http://codeforces.com/contest/749/submission/23409556 http://codeforces.com/contest/749/submission/23175395 The first code gives TLE on Case 10,the second one gets accepted. Can someone help me in figuring out what is wrong in Code 1 that gives the verdict as TLE though the approaches used are same ?