Всем привет!
В понедельник, 19 декабря в 19:35 MSK состоится Codeforces Round #388 для участников из второго дивизиона. Участники из первого дивизиона могут принять участие вне конкурса.
Для вас раунд готовили: Денис pitfall Безруков, Алексей dalex Дергунов, Вячеслав Slamur Муравьев, Егор Petruchcho Пономарев, Павел craus Семушин и Андрей Shlakoblock Гайдель.
Для меня, Slamur и Petruchcho это первый рейтинговый раунд. Надеемся, что все пройдет хорошо и каждый участник найдет для себя интересные задачи.
Выражаем благодарность Глебу GlebsHP Евстропову за помощь в подготовке раунда и Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
UPD: Вам будет предложено 5 задач и 2 часа на их решение.
Разбалловка: 500-1000-1500-2000-2500
Наши поздравления победителям:
Div.2:
1. just29
2. tnbt
3. el_smurfo
4. SimB4
5. skydog
Div.1:
1. I_love_Tanya_Romanova
2. W4yneb0t
3. enot110
4. vintage_Vlad_Makeev
5. Um_nik
UPD: Разбор доступен по ссылке
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
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 : (
Контест от самарских троллей, это должно быть интересно!
Hope so we will enjoy :)
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!
thx a lot for these consecutive contests (#388,#387,#386,#385)...it helps our ACM team for ICPC-Tehran Region
After many contests, the number of problems are now 5 =))) We have a usual contest, with usual time, usual number of problems, and usual duration =))
You forgot to mention usual scoring.
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 Codeforces for 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!
What's the C hacking case was please?
Mine was:
21 DDDDRRRRRDRDRDRDRDRDRWhat 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).
What 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 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>andlower_boundin them. 23155161.PD.: Sorry for my horrible English.
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, 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. If he meant the next undeleted instance, he would write "pos 2 kills pos 3" and so on.
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://mirror.codeforces.com/contest/749/submission/23156836 ) or BIT for O(n*log(n)).
linearity of expectation
, so if ai < aj , add p to answer else add 1 - p to answer. To do this in O(NlogN) , use bit.
for a pair i , j , such that i < j the probability of j become more than i is p where
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.
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.
:PIn my opinion, B was much easier.
Хороший контест, и задачки интересные
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.
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
Мне тут рассказывали, что я не умею оценивать div.2 раунды. Дак вот, по моим неадекватным критериям это один из самых интересных div.2 раундов на CF. Спасибо. Все 5 задач были интересные и крутые.
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. Usestd::<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...
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://mirror.codeforces.com/contest/749/submission/23151466 http://mirror.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://mirror.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://mirror.codeforces.com/contest/749/submission/23153380
becuase you are cheater!
You sure about that?
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;
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://mirror.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 D because of not checking if the lower_bound exceed the range. Such a disappointment :(
Ummm...tutorial???
:)
Regexing in C — 23162742 (more readable version — 23154376)
Hoping some C++ expert can help me understand this issue.
Here is my submission to problem D: http://mirror.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://mirror.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!