By BledDest, history, 11 months ago, translation, ,

Hello Codeforces!

On November 23, 18:05 MSK Educational Codeforces Round 33 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

As an experiment, the round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were prepared by Mikhail PikMike Piklyaev, Vladimir 0n25 Petrov and me.

Good luck to all participants!

UPD: Editorial.

I also have a message from our partners, Harbour.Space University:

Be sure to join these courses to sharpen your programming and data analysis skills:

Combinatorics and graphs with Sergey Nikolenko, Researcher, Steklov Mathematical Institute at. St. Petersburg. He is a computer scientist with vast experience in machine learning and data analysis, algorithms design and analysis, theoretical computer science, and algebra.

Algorithms and Data Structures with Edith Elkind, Professor University of Oxford, Department of Computer Science. She researches game theory and the computation of social choices. She looks at the decisions involved in multi-agent systems such as auctions, elections and co-operative games.

Big Data Analysis: Mapreduce, Spark, BigTable/HBase, Distributed Data with Pavel Klemenkov and Alexey Dral. With HDFS, MapReduce, Spark, and NoSQL, students will master and sharpen their knowledge in basic technologies of the modern Big Data landscape.

Parallel and Distributed + High Performance Computing with Dalvan Griebler. The name says it all. Learn how to run your programs faster.

List of all courses:

27.11.17 — 15.12.17 — Image and Video Analysis with Archontis Giannakidis

27.11.17 — 15.12.17 — Linear Algebra with Archontis Giannakidis

08.01.18 — 26.01.18 — Text Mining & Translation with Sergey Nikolenko

08.01.18 — 26.01.18 — Combinatorics and graphs with Sergey Nikolenko

29.01.18 — 16.02.18 — Security analysis of networked objects with Yaroslav Rabovolyuk

19.02.18 — 09.03.18 — Security Operations Center and Cyber Threat Hunting with Sergey Soldatov and Teymur Kheirkhabarov

19.02.18 — 09.03.18 — Calculus with Dmitry Ivankov

12.03.18 — 30.03.18 — Malware Reverse Engineering with Vladislav Stolyarov, Victor Chebyshev and Boris Larin

09.04.18 — 27.04.18 — Incident Response & Digital Forensics with Konstantin Sapronov and Ayman Shaaban

09.04.18 — 27.04.18 — Linear algebra with David Zmiaikou

30.04.18 — 18.05.18 — Statistical Data Analysis with Evgeniy Riabenko

30.04.18 — 18.05.18 — Probability theory with Evgeniy Riabenko

21.05.18 — 08.06.18 — Parallel and Distributed + High Performance Computing with Dalvan Griebler

21.05.18 — 08.06.18 — Algorithms and Data Structures with Edith Elkind

11.06.18 — 29.06.18 — Big Data Analysis: Map Reduce, Spark, BigTable/HBase, Distributed Data with Pavel Klemenkov and Alexey Dral

Register for your spot

•
• +309
•

 » 11 months ago, # |   +51 What are the exact rules of the rated contest? Since it's non-standard CodeForces round, you could have included more details about it.Will hacks count into result? Will the ranking be like usual Educational rounds?
•  » » 11 months ago, # ^ |   0 I think it's first time, when educational round become rated. Hope problems will have short statements not as this announcement. Wish everybody luck and high rating...!
•  » » » 11 months ago, # ^ |   -26 Wubba lubba dub dub
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   +1 I hope the round will be unrated, because the query sometimes was more than 35 pages, and it was unreal to solve task without lost time.
•  » » 11 months ago, # ^ |   -9 just like common div2 games,so take it easy and enjoy it.
•  » » 11 months ago, # ^ |   -21 bazsi700.It's div2 contest...
 » 11 months ago, # |   +12 Are there going to be pretests?
•  » » 11 months ago, # ^ |   +9 I hope not, so that this contest would really feel different.
•  » » » 11 months ago, # ^ |   0 Does it's harder than another contest div2 only ??
•  » » 11 months ago, # ^ |   +36 No, the rules will be completely the same as on the previous Educational Rounds. After the contest we will build standings with Div. 2 participants only and update ratings according to taken places.
•  » » » 11 months ago, # ^ |   +34 And what about hacks? Will they change rating?
•  » » » » 11 months ago, # ^ |   +6 I guess answer is NO, because if anyone who belongs to Div 2 and doesn't participate in contest, but have some successfully hack then what is happened? Also anyone can hack a lot of solution, then it arise a big problem in rating change.
•  » » » » 11 months ago, # ^ |   -33 They won't. Your rating change depends on your language. For example I use C++, so C++ gives me more rating.
•  » » » » » 11 months ago, # ^ |   0 is that true???here??
 » 11 months ago, # | ← Rev. 3 →   +248
•  » » 11 months ago, # ^ |   +230
•  » » » 11 months ago, # ^ |   -16 And it's gonna happen soon
•  » » » » 11 months ago, # ^ |   -23 And you gonna become newbie soon
 » 11 months ago, # |   +15 24 hour open hacking phase ?
•  » » 11 months ago, # ^ |   +21 Yes!
 » 11 months ago, # |   +43 About the rules of rating distribution:After the hacking phase the participants from Div.2 will be sorted according to ICPC rules (by number of solved problems, and if the number of problems is equal, by penalty). Then the rating will be redistributed according to places in Div.2.There will be pretests, and the number of them will be larger than in regular Codeforces Rounds, but we don't guarantee that if the solution passes pretests, it will pass system tests. This might be inconvenient for some participants, but remember that this round is experimental, and we may make ERs unrated again after this round (or change the rating distribution system in ERs).
•  » » 11 months ago, # ^ |   +3 Does the number of successful/unsuccessful hacks made during the hacking phase affect your rating like in normal Codeforces rounds?
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +35 The number of hacks a person made won't affect his/her place in this round.
•  » » » » 11 months ago, # ^ |   +6 Why won't affect ? If I will hack someone who solved 1 problem more than me, he will fall and I will in place upper :)
•  » » » » » 11 months ago, # ^ |   0 What if he is in upper place after you hack, or lower place before you hack...:p
•  » » 11 months ago, # ^ | ← Rev. 2 →   +9 A couple of proposals:You may divide all rating changes by 2 (do it "half-rated") due to specificity of edicational rounds.Add small score bonuses for successful hacks (hacking is useful for community, so it should be rewarded)
•  » » » 11 months ago, # ^ |   -16 Saw some guy giving the exact same suggestion some months ago and getting some umpty number of downvotes
•  » » » 11 months ago, # ^ |   +19 Anyone can hack a lot of solution. Then it will be a big problem, if there any bonus for successful hack.
•  » » » » 11 months ago, # ^ |   0 -1 penalty or -5 penalty with 1 successful hack will solved this problem
 » 11 months ago, # |   -23 Is there going to be more rated Educational rounds?
 » 11 months ago, # | ← Rev. 2 →   +22 I can't wait to see how rated educational will work. Good luck to everyone!
 » 11 months ago, # |   +31 So as i understood it will be a cf round with educational problems which are really nice, with rating system like atcoder and cs academy, no hacks(because they don't count into the rating). What can be better in the world than this???
 » 11 months ago, # |   -26 Is it rated? And if it is rated, can it became unrated?
•  » » 11 months ago, # ^ |   -10 yes it is said in the blog post.
 » 11 months ago, # |   -11 I think that you should write into the description with really big letters that is rated because some don't see it very well.
•  » » 11 months ago, # ^ |   +14 I think, someone doesn't understand trolling
•  » » » 11 months ago, # ^ |   -16 xdd
 » 11 months ago, # |   -21 So, CF is moving to ACM-ICPC style permanently? There will be no hack during contest in near future or soon? :)
 » 11 months ago, # |   +3
 » 11 months ago, # |   0 Make next educational contests rated
 » 11 months ago, # |   +3 So will system tests happen after the 24 hour hacking period so that hack cases can be added into the system tests?
•  » » 11 months ago, # ^ |   +25 Actually, we add hacks into system tests in each ER.
 » 11 months ago, # | ← Rev. 4 →   +8 You say: Educational rounds primarily pursue educational and training goals, rather than competitive ones. But edutcational is rated. Don't be so
 » 11 months ago, # |   +55 Paradox :D Last official rated rounds — unrated. Next official unrated round — rated.
 » 11 months ago, # |   +5 Will the rating change after the contest ends or it will change after 24-hour hacking phase? If it change after 24-hour hacking phase, will hacks affect to a participant's rating?Hope this round will be the best rated Educational Round ever.
•  » » 11 months ago, # ^ |   0 Of course rating change after 24-hour hacking phase, because final system test occur after 24-hour hacking phase. Hack means a wrong solution, so rating must be affect with hack.
 » 11 months ago, # |   +2 OMG! That's good!
•  » » 11 months ago, # ^ |   0 Yeah!
 » 11 months ago, # |   0 What is the influence for penalty if I hack others? I have a suggestion. If I hack others successful, I got -10 min penalty, otherwise, I got 20 min penalty
 » 11 months ago, # |   +8 Is it "Rated"?
•  » » 11 months ago, # ^ |   0 What are the exact rules of the rated contest? Since it's non-standard CodeForces round, you could have included more details about it. Will hacks count into result? Will the ranking be like usual Educational rounds?
•  » » » 11 months ago, # ^ |   0 So as i understood it will be a cf round with educational problems which are really nice, with rating system like atcoder and cs academy, no hacks(because they don't count into the rating). What can be better in the world than this???
 » 11 months ago, # |   -6 Will all Educational Codeforces Rounds be rated?
•  » » 11 months ago, # ^ |   0 Maybe
•  » » 11 months ago, # ^ |   +11 Can you read announcement?
•  » » » 11 months ago, # ^ |   -16 Can you answer?
 » 11 months ago, # |   +17 Rated educational contest: ACM with semi-freezing for the entire contest including yourself
 » 11 months ago, # |   +6 Codeforces probably will be more and more interesting!Come on!
•  » » 11 months ago, # ^ |   -11 Go out
 » 11 months ago, # |   +3 http://www.reactiongifs.com/r/gc.gif Is it "Rated"? :O
 » 11 months ago, # |   +1 That's just a suggestion. You can add another Rating Criteria say Educational Rating and make all the Educational Round rated based on the usual rating system or any other rating algorithm.
 » 11 months ago, # |   +6 It'll feel more different if there would be no pretests and 1 day hacks.
•  » » 11 months ago, # ^ |   0 :p
•  » » 11 months ago, # ^ |   +3 It's experiment
 » 11 months ago, # |   -20 Is it rated?
•  » » 11 months ago, # ^ |   +20 Any educated person can read this blog. Sorry to say, you can't!
•  » » » 11 months ago, # ^ |   -17 Any educated person wouldn't write answer to this comment. Sorry to say, you did(((
•  » » 11 months ago, # ^ |   -6 NO, It isn't
 » 11 months ago, # |   -13 I can not more agree with the dicision
 » 11 months ago, # |   +8 finally there will be Edu. Round in my contest list :-)
 » 11 months ago, # | ← Rev. 2 →   -54 Why this page is not included in "HARBOUR SPACE UNIVERSITY" page as Educational Codeforces Round 32 Announcement? UPD: It was updated.
 » 11 months ago, # |   -24 I'm a newbie =)) everry body who can help me how to study as well in IT
•  » » 11 months ago, # ^ | ← Rev. 2 →   -15 First, you have to beat tourist in a contest
•  » » » 11 months ago, # ^ |   +4 And me. hahaha
 » 11 months ago, # |   0 Good luck to everyone! We're all eager to know how this will work! Anyway, I want to mention that I'm okay with frequent changes of how the contests work, but I would like to maintain the situation of having one weekly contest that isn't rated(besides of other rated contests). What do you people think?
•  » » 11 months ago, # ^ |   -13 Watch your goddamn mouth
 » 11 months ago, # |   0 Is score will be Based on the time of submission??
•  » » 11 months ago, # ^ |   0 yes, penalty = sum_time + (amount of unsuccessful submits) * 20
•  » » 11 months ago, # ^ |   -10 No, it will be based on your code. How long is it, it depends on size of your code.
 » 11 months ago, # |   +3 best thing to an educational round :D
 » 11 months ago, # |   +25 Again 30 pages queue :\
•  » » 11 months ago, # ^ |   +16 Long queues always sucks !!!
•  » » » 11 months ago, # ^ |   -17 Like you
•  » » 11 months ago, # ^ |   -14 And again you couldn't solve medium problems
 » 11 months ago, # |   +22 Experiment Failed. ( Long Queues )
•  » » 11 months ago, # ^ |   +13 I think long queues are not cause of round type.
 » 11 months ago, # | ← Rev. 2 →   +12 12 minutes to surpass the queue (and received a WA after that). Either Codeforces server is running into trouble again, or you guys haven't anticipated enough about the number of submissions in educational contests...UPD: Things are getting a lot better now. Can't compensate the issues, but still cheers ;)
•  » » 11 months ago, # ^ |   -10 It's not our problem. So what do you want?
•  » » » 11 months ago, # ^ |   0 Actually, it is. The pressure of waiting for judgement for your "threshold" problems — that means the "just right" problems, hardest you can solve in a contest — is increasing dramatically due to long queues. Also, nobody enjoys an environment with bugs and issues. They should be reported so that the administrators/moderators or the contest setters could figure out and attempt to fix it.
 » 11 months ago, # |   -6 Is it rated?
 » 11 months ago, # |   0 In queue for more than 15 minutes!
 » 11 months ago, # | ← Rev. 2 →   +15 Codeforces improves significantly!! There are only 27 pages of queue now.
•  » » 11 months ago, # ^ |   -7 Exactly like you
 » 11 months ago, # |   +6 I think new diagnostics of solutions in c++ failed the crash-test...
 » 11 months ago, # |   0 Why is the answer for a 3rd test case in problem D is 2? No explanation given as well as this question is also not well framed.
•  » » 11 months ago, # ^ |   +4 The answer is indeed 2. I am not sure whether I am allowed to give you an explanation in the middle of the contest.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Optimal: 1 2 3 4 5 Mornings 0 +5 0 0 +11 Day Balance 0 0 0 10 10 Evenings -5 0 10 -11 0 In check-days we have non-negative balance, balance always less or equal than d.Answer: 2 deposits.
•  » » 11 months ago, # ^ |   0 i was a bit confused too, but then i got that we can put some money to account before 0 operation comes in the evening
 » 11 months ago, # |   +14 I think contest is going well.Queue is for having many test cases than regular contest :) Though sometimes it is bothering,but well enough comparing with bad pretest.
 » 11 months ago, # |   +8 I hate D.Why you don't give an explanation to example when you know many people can't understand it clearly?
 » 11 months ago, # |   +1 Is it Rated?
•  » » 11 months ago, # ^ |   0 ***, ** **.
 » 11 months ago, # |   0 How to solve E?
•  » » 11 months ago, # ^ | ← Rev. 4 →   +28 first preprocess all the lowest prime factors, factorials and their inverses up to 1e6+5. Then for each x find the powers of each prime in x. You can need to distribute each power in y buckets. (basic stars and bars problems) Also to accommodate negative integers see that you can have even number of negative numbers. So final answer will be:Calculate 2y - 1 by fast exponentiation. So time complexity: O(t * log(max(x, y)))
•  » » » 11 months ago, # ^ |   +34 If you want to calculate then counting factorials up to 1e6 + 5 is not enough.
•  » » » » 11 months ago, # ^ |   +11 Ah yes. 1e6 + 50 should be enough
•  » » » » » 11 months ago, # ^ |   -24 Stop, I can't understand your formula above. Can you write in details, please? I would thank you :)
•  » » » » » 11 months ago, # ^ |   0 What's 't' ?
•  » » » » » » 11 months ago, # ^ |   +5 Number of testcases
•  » » » » 11 months ago, # ^ |   0 Thats where I got hacked :(
•  » » 11 months ago, # ^ |   -15 Yes, I couldn't solve it too. How to solve it guys?!)
 » 11 months ago, # |   +1 Anyone who failed a pretest got screwed with penalty time.
•  » » 11 months ago, # ^ |   0 So don't fail the pretests
•  » » » 11 months ago, # ^ |   +9 Good idea. I'll remember to keep this in mind for next time.
•  » » 11 months ago, # ^ |   0 Are you happy now?
 » 11 months ago, # |   0 The submission 32583028 got TLE, but then 32586076 got AC while I only changed the compiler from "GNU C++17 Diagnostics" to C++11 (and lld to I64d). How to explain this phenomenon?
•  » » 11 months ago, # ^ |   +26 With such two diagnostic launches, the performance of the program suffers tremendously (the program is executed 5-100 times slower and requires more memory), but often it's worth it.
•  » » » 11 months ago, # ^ |   0 Oh... My fault. TwT
•  » » 11 months ago, # ^ |   +16 Please, read my post http://codeforces.com/blog/entry/55902
•  » » » 11 months ago, # ^ |   0 Thank you! I'd be more careful next time.
•  » » » 11 months ago, # ^ |   +32 Maybe add a warning beside the language name, something like (slower) or (only for debugging)? not everyone who has not seen the blog post will know about this
•  » » 11 months ago, # ^ |   +3 You must not have seen the blog post. "GNU C++17 Diagnostics" runs much slower than the standard compiler as it checks for certain errors in your code. Check http://codeforces.com/blog/entry/55902
•  » » » 11 months ago, # ^ |   0 I thought it was just adding additional checks into the code...
 » 11 months ago, # |   +8 Will rating be calculated according to your standings without Div 1 participants (kind of like Div2 rounds with out of competition Div1 competitors) or like a combined round?
•  » » 11 months ago, # ^ |   0 I think it maybe a Div1+Div2 round and only to rate for Div2
•  » » » 11 months ago, # ^ |   0 Okay, based on what Bleddest said, I think it'll be according to your standing among Div 2 competitors only. Correct me if I'm wrong."After the hacking phase the participants from Div.2 will be sorted according to ICPC rules (by number of solved problems, and if the number of problems is equal, by penalty). Then the rating will be redistributed according to places in Div.2."
•  » » » » 11 months ago, # ^ |   0 Oh, Thank you. I didn't see that.
 » 11 months ago, # |   0 hi i cant find the bug in my code can anyone help ? http://codeforces.com/contest/893/submission/32598508
 » 11 months ago, # |   +4 For those who got WA on test 49 on D and later got AC, what logical error did you find?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 diff here 32594374 and here 32596916my idea was to use two limits mn - mx which the balance should be one of, I missed the case I meet a 0 and not update my mn to at least max(mn, 0) because if that value is below zero, some cases might add to mn which would fail my condition of failing which is mn > d it means you just can't achieve the goal!Hope this helps!
•  » » 11 months ago, # ^ |   0 While propagating the extra money that you are adding you need to keep in mind that you do not end up decreasing sum below 0.Go through this once.Let me know if you are unable to understand something
•  » » » 11 months ago, # ^ |   0 What is wrong with my solution here. I understood your point, but I am always keeping my sum equal to d when sum>d and subtract the reduction from excess. So in my case, I can't decrease my sum below 0. 32597627
•  » » » » 11 months ago, # ^ |   0 well you need to check if your present sum < 0 Only then that is required... You need to find the minimum exchanges.I guess thats the only difference between our code
•  » » » » » 11 months ago, # ^ |   0 It worked. Thanks :D
•  » » » » » 11 months ago, # ^ |   0 can someone help in D? I have taken record of extra money and current balance. here is my implementation: http://codeforces.com/contest/893/submission/32602778
•  » » » » » » 11 months ago, # ^ |   0 you should try to put this if(bal+ex>d) { ex=d-bal; }before putting thisif(bal>d) { cout<<"-1\n"; return 0; }or something like this
•  » » 11 months ago, # ^ |   0 I honestly don't know I got it in the last 3 minutes so after that I started changing small things in my code (I didn't even know if the changes were going to do something or not) and then submitting the code I sent like 5 submissions in 5 minutes I was like crazy.Anyway a few of my submissions got AC but I don't know if it's going to stick.
 » 11 months ago, # |   0 could someone help me with problem c I keep getting wrong answer on test 7 link to my solution: https://goo.gl/95gxqy
•  » » 11 months ago, # ^ |   0 Try LONG LONG INT
•  » » 11 months ago, # ^ |   0 you havent considered the smallest oneI think you've missundestood the problem.you can go throught this , hope it helps
•  » » » 11 months ago, # ^ |   0 thank you for your help but I can't understand the code because I'm beginner :(
•  » » » » 11 months ago, # ^ |   0 go throught dfs and connected componenets...it'll help
•  » » » » » 11 months ago, # ^ |   0 I will try to understand thx for your advice
 » 11 months ago, # |   0 Can someone help me in D http://codeforces.com/contest/893/submission/32592296
•  » » 11 months ago, # ^ |   0 if(f[i]==0 && cur+mar>=0) cur=0,mar-=cur;mar-=0 does not update mar.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0
•  » » » » 11 months ago, # ^ |   0 It should be mar+=cur since cur is negative.
•  » » » » » 11 months ago, # ^ |   0 Thanks :) It seems my brain has stopped working :P from the fact that I could have solved E if not wasted time on D
•  » » 11 months ago, # ^ |   +1 I solved using segment tree lp. And why this line? "if(f[i]==0 && cur+mar>=0) cur=0,mar-=cur;
•  » » » 11 months ago, # ^ |   0 Segment Tree is not reqd See this http://codeforces.com/contest/893/submission/32584069 mar stands for margin that we can use when we have previously visited bank
•  » » » » 11 months ago, # ^ |   0 Oh the solution is so simple...
 » 11 months ago, # | ← Rev. 2 →   0 who can share some hacks to show where people made mistakes?
 » 11 months ago, # |   0 How to solve D ???
•  » » 11 months ago, # ^ |   -13 There is no contest results yet. So contest is in progress. You shouldn't ask solutions of others, boy ya!
•  » » 11 months ago, # ^ | ← Rev. 3 →   +13 Here is my submission: 32585910.First, I took the prefix sums of all a[i] in the array I called day. I also saved which days a[i]=0 in the array check so I know which days the balance needs to greater than 0. Notice that the balance on day j is day[j].Since the balance on day j is day[j], we need to make sure that day[j] >= 0 n days that a[j] = 0. If day[j] < 0, we want to deposit money that morning. Since we want to add money for the minimum number of days, we want to add as much money as possible when we are depositing money. If we add x money to day i, the amount of money on days i...N all increase by x. Therefore, The maximum amount of money we can add on the morning of day i is D-( max(day[j] for j = i...N) ). To calculate max(day[j] for j = i...N), create an array mb where mb[i] is max(day[j] for j = i...N). Loop backwards to create mb. Now, if on day i a[i]=0 and day[i] < 0, we can deposit D-mb[i] that morning. We now need to store that days i...N have D-mb[i] more money. Create a variable add which stores how much money has been added in the mornings.If at any point day[i]+add > D, print -1 because the account has more than D burles. If a[i] = 0 and day[i]+add < 0, deposit D-(add+mb[i]) but deposit at least 0-(day[i]+add), otherwise the account will have negative balance. So add += max(D-(add+mb[i]), 0-(day[i]+add)).
•  » » » 11 months ago, # ^ |   0 Thanks a lot :)
•  » » » 11 months ago, # ^ |   0 __"we need to make sure that day[j] > 0 n days that a[j] = 0" shouldn't it be "day[j]>=0"?
•  » » » » 11 months ago, # ^ |   0 Fixed. Thank you!
 » 11 months ago, # |   -8 Can someone explain me problem A in more detail??? I can't figure out my solution(((
•  » » 11 months ago, # ^ |   0 start with 2 people (1 and 2), 3 is sitting out. then start a loop and check if 1 wins then swap 2 with 3, so now the players become 1 and 3. 32591094 will tell you the logic. it becomes obvious once you do it by hand.
•  » » » 11 months ago, # ^ |   -11 Oh my god, I roundly got the idea. But can you write the details please :)
•  » » » » 11 months ago, # ^ |   0 initial players 1,2. spectator:3. the result has to be between players.so the result has to be 1/2. if result=1, spectator=2, player=3. swap between loser and spectator.if result=2, spectator=1, player=3now players: 1,3 spectator: 2 ....it goes on till the end
•  » » » » » 11 months ago, # ^ |   -6 Ok, but when we will reach the end? I can't get it(
•  » » » » » » 11 months ago, # ^ |   0 end is the end of input elements. array size
•  » » » » » » » 11 months ago, # ^ |   0 Oh yeah, I'm that stupid... But... I'm sorry again, what is the array size....
•  » » » » » » » » 11 months ago, # ^ |   0 "The first line contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played."-- This n is the no of array elements or size
•  » » » » » » » » » 11 months ago, # ^ |   +8 Ohh.. I know, I'm so stupid. But how to swap players. That's a problem.
•  » » » » » » » » » 11 months ago, # ^ |   0
•  » » » » » » » » » 11 months ago, # ^ |   +22 Go to toilet then have a dinner, again go to toilet and players will be swapped.
•  » » 11 months ago, # ^ |   0 You just have to simulate the game, Alex and Bob start playing and Carl is spectating. So if Alex wins ( if the number is 1 ) you change Bob who lost with Carl , now Alex is playing with Carl if the number is 3 means that Carl wins, so you have to change the players again.... Do this until you find some absurd ( the person who wins is the spectator ) or until the movements finish.
•  » » » 11 months ago, # ^ |   +1 Oh yeah, I got your idea. But I don't know how to implement it. Can you help me please ^_^:)))
 » 11 months ago, # |   0 for problem C, shouldn't DFS with connected components get me the correct answer? I am failing 5th test case. 32595477
•  » » 11 months ago, # ^ |   +6 for starters, your array should have a size of at least 100001, because you're storing everything 1-based.In general, it's a good practice to add 5 elements more to your limit to avoid these problems.
•  » » » 11 months ago, # ^ |   0 thanks. I am a fool. 32601419
•  » » » 11 months ago, # ^ |   -35 Why count him as starter? He has better potential than you. He tries to solve hard problems. NOT LIKE YOU. So you should get your tongue tied.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +30 Oh my god, he didn't call BeardAspirant a starter. It's just a way of speaking. It's similar to: "Firstly, your array should have a size of at least 100001 ...". And why the hate? Also, who are you to decide who has better potential? Stick to what concerns you.
•  » » » 11 months ago, # ^ |   +6 in general for competitive programming. Generally, you should be very sure about which indices are actually accessed.
 » 11 months ago, # |   0 i solved problem D using segment tree lp. what is the simplest way to solve D?
•  » » 11 months ago, # ^ |   -52 To write the code.
•  » » 11 months ago, # ^ |   +3 I explained my solution here.Hope this helps!
 » 11 months ago, # |   +4 Must we wait till the end of hacking phase to know the rating change?
•  » » 11 months ago, # ^ |   +1 Yes, because people's solutions can still be wrong.
•  » » 11 months ago, # ^ |   -23 Actually, no. However, it depends on you.
 » 11 months ago, # |   0 Codeforces give or take points in this contest?
•  » » 11 months ago, # ^ |   -16 It depends on your rating. In your case (pupil), you won't get any points. For example, in my case (newbie), I will get exactly more than 2500 points.
•  » » » 11 months ago, # ^ |   +2 thanks for the info.
 » 11 months ago, # |   0 thanks a lot for problem F's time limit
 » 11 months ago, # |   0 Pls, someone tell me, is it correct solution for D?http://codeforces.com/contest/893/submission/32601001
•  » » 11 months ago, # ^ |   -20 I think your solution is incorrect. But problem is not in your idea or in your code. Sorry to say, Your problem is in your name... Maksim... Maksim... Maksim.. I really feel sorry about you(
 » 11 months ago, # |   +3 How to solve problem F??
•  » » 11 months ago, # ^ |   +1 Build a merge sort tree on the of the tree in DFS order. When merging, remove elements so that value is non-decreasing and depth is non-increasing. Then each query becomes over this range, what is minimum value if depth is maximally (depth(x) + k). Solve this by having a fenwick tree or doing a binary search.
•  » » » 11 months ago, # ^ |   0 thanks man
•  » » » 11 months ago, # ^ |   0 Can you please elaborate your solution ?
•  » » » 11 months ago, # ^ |   0 Can you explain the 'process' function in your code? Or, what are you trying to achieve using the fenwick tree?
•  » » » » 11 months ago, # ^ |   +1 Yeah that code shouldn't work, and doesn't properly implement what I said above, but I guess it's hard to find tests that make it TLE. I'll write up a cleaner commented version and link it here later today.
•  » » » » » 11 months ago, # ^ |   0 Thank you so much.
•  » » » » » » 11 months ago, # ^ |   +1 Alright, here we are. This solution is , but runs in around 2.5 seconds (TL is 6 sec).First, run the DFS to get a list of nodes in DFS order. Then, build a segment tree on these nodes. For each segment, we keep a map from depth to the minimum value at that depth. Then to get the answer for a segment and a depth d, take the minimum value over all depths <= d on that segment. To do this quickly, use prefix minimums or a fenwick tree. The fenwick tree is overkill here, but would support updates quickly.Prefix Minimums: http://codeforces.com/contest/893/submission/32656954Let me know if you have any more questions!
•  » » » » » » » 11 months ago, # ^ |   0 I have used segment tree, instead of fenwick and prefix minimum. Although, I am getting accepted, can you tell me, why is it running so slow ? (3.4s)
•  » » » » » » » » 11 months ago, # ^ |   +1 Segment trees just run slower than fenwick trees or prefix mins. They have a higher constant cost.
•  » » » » » » » » » 11 months ago, # ^ |   0 oh okay. Thanks man! You have been really helpful.
 » 11 months ago, # |   +126
•  » » 11 months ago, # ^ |   +6 It is a way to gain hack scores
•  » » » 11 months ago, # ^ |   +20 Your scores won't get affected due to hacks in this round.
 » 11 months ago, # |   +8 How to solve E ?
 » 11 months ago, # | ← Rev. 3 →   +8 getting TLE in c++17 and clang++17 Diagnostics and accepted in c++14. How?
•  » » 11 months ago, # ^ |   +14 Follow this comment thread.
 » 11 months ago, # |   -22 Round should be unrated. Very long queue
 » 11 months ago, # |   0 How to solve A?
•  » » 11 months ago, # ^ |   0 You can just simulate the game: have three boolean variables / array of 3 bools and then update them based on who wins.If the bool variable corresponding to the player who wins is false (e.g he could not have played in the first place), print -1 because such a win is impossible
•  » » 11 months ago, # ^ |   0 You can have 3 variables, these can be 2 on and 1 off, then you are reading and only ask if it is on or off, if it is off the answer is "NO", if it is on you change the three variables to its opposite, then you return to change only the variable read and repeat the process until finished. If you finish without problems the answer is "YES".
 » 11 months ago, # |   +1 Really nice problems!
 » 11 months ago, # |   +8 For problem C, I have seen that (in hacking phase) many contestants have used dsu using two arrays — cost, parent. But my code shows memory limit exceeded on test 4 with 10^5 sized array — 32587358
•  » » 11 months ago, # ^ |   0 You forgot to return a value in the second case of your par function. You are compressing a path but not returning it.Hope that fixes it.
 » 11 months ago, # |   0 I made the following observations on E. 1: the number of prime factors of x cant be more than 20. And there can be atmost 8. even when it is 8 it is > 1e6. So build a dp table for binomial co efficient. 2: In order to find the prime factors modify seive table to hold the largest prime factor dividing it. 3: Split x into prime factors. And count the number of walls. (Combination with repetition). and using binomial coefficient we can make C(y+w+1, y) choices ( here 1 is for the number '1'. since i can include it). But here i got stuck. since in these y factors different prime numbers can be different number of times in which i ve to use permutation with repetition (to arrange within them). But how to apply it here. And after that choose any 2, 4, 6,.. numbers in y numbers and again multiply them with the permutations (for choosing negative. ) here also i got stuck. Can someone plz help me
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 Your logic is correct. For your last part, consider the binomial theorem expansion of (1+x)^n. Sum of all n choose k is 2^n.Now put x=-1. You will see that sum of all n choose odd k= sum of all n choose even k. Hence, the sum of n choose even k= 2^(n-1).Also, note that the sequence starts from 0 and not 2.
•  » » » 11 months ago, # ^ |   0 Yes. it is correct for nC2 + nC4 + .. . But i can arrange within them. So it will be (n!/(rep1! * rep2!...)) * (nC2 + nC4 + ..). so how to calculate the (n! / rep!), rep1 = number of times prime factor 1 is repeating. rep2 is no of times factor 2 is repeating.... . for eg, suppose if i ve 2, 2, 3. then i can arrange them in 3!/2! = 3 ways(here n = 3, rep1 = 2, rep2 = 1) . so i ve to multiply that with the answer. here there is 2 times 2 hence i put 3!/2!. But when i choose y numbers, i dont know how mnay numbers repeat how many number of times. So how to solve that.
•  » » 11 months ago, # ^ |   +13 There is a very simple idea in which you don't have to worry about repetitions -- Let's represent the given number x as it's product of prime factors. Observe that each prime factor is independent of other. So we can calculate the answer for each prime factor independently and multiply it with the final answer. The pseudo code will be something like this:  res = 1 for each primeFactor in x: c = number of times that primeFactor occurs in x. res *= numWays(c, y) res *= power(2, y - 1) //Now res is your final answer. Now the problem reduces to finding numWays(c, y) efficiently. Observe that we have c apples and we need to distribute them to y people such that a person might not get any apple. So the numWays is just ncr(c + y - 1, y - 1). So the final idea is:  res = 1 for each primeFactor in x: c = number of times that primeFactor occurs in x. res *= ncr(c + y - 1, y - 1) res *= power(2, y - 1) //Now res is your final answer.  Hope it helps
•  » » » 11 months ago, # ^ |   0 thanks man
 » 11 months ago, # |   +1 Can someone explain, how to solve F in detail ?
 » 11 months ago, # |   +17 Perfectly matched problems for DIV2. Thanks to authors & testers:)
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 Problems were nice, but I think E is easy for Div2E, maybe it can be D of Div2 :)
 » 11 months ago, # |   +7 ratings?
 » 11 months ago, # |   +17 No system testing?? The standing page says its the final standings, i thought hack tests will be added before final standings.
•  » » 11 months ago, # ^ |   +1 When the hack phase ended, they announced that the solutions will be rejudged on hacks soon.
•  » » 11 months ago, # ^ |   +1 It looks like it's system testing now.
•  » » » 11 months ago, # ^ |   +16 It's being done at a mind-blowing speed as well..
 » 11 months ago, # |   0 When we can see the mew rate?
•  » » 11 months ago, # ^ |   +5 We have to wait for them to rejudge the solutions with the new tests and then they'll update the ratings.
 » 11 months ago, # |   +5 sorry i mean new rate
 » 11 months ago, # |   +35 I think if educational rounds will be rated in the future too, I think a feature should be added, the system testing percentage one like normal rounds.
•  » » 11 months ago, # ^ |   +11 agree
 » 11 months ago, # |   +18 System test is too slow................................................
 » 11 months ago, # |   +7 really nigga :| its still testing
•  » » 11 months ago, # ^ |   0 Long queue in contest means long system test.
 » 11 months ago, # |   0 In Div 2 C (Rumors),I don't really understand why my first submission isn't working and second is working. I only changed how I set my data type (for example from long long, I switched to typedef long long ll). My first submission results in a wrong answer on test case 5. I am really curious what did I do wrong, so I can know for next time. I didn't change anything in algorithm.My first submission:http://codeforces.com/contest/893/submission/32631226My second submissionhttp://codeforces.com/contest/893/submission/32631196
•  » » 11 months ago, # ^ |   0 Look you change the size of graph, in the first solution, if you add edge (99999, 100000), you have problems
•  » » » 11 months ago, # ^ |   0 Ohhh, so I made a mistake by typing 100000 on a vector instead of 1e5+10
•  » » 11 months ago, # ^ |   0 vector v[100000]; and long long niz[100000]={0};  your adjacency list size as well the cost array will not store the 1e5th node values, there is no spaces to it.
 » 11 months ago, # |   0 Hey mikemirzayanov do you need my laptop? I guess it will help the system for judging.
•  » » 11 months ago, # ^ |   -8 hahah, this has to be the longest systest ever, and no progress indicator too.
 » 11 months ago, # |   +2 When can i see my new rating?
 » 11 months ago, # |   +9 System Testing is finally OVER !! How long will it take for rating changes to reflect? :D
 » 11 months ago, # |   +3 If I had +65 rating in combined list, shouldn't I have more rating in only Div 2 list? Am I wrong?
•  » » 11 months ago, # ^ |   +8 Same, I had +77 but ended up with +2??
•  » » » 11 months ago, # ^ |   +2 same here i got +89 but finally it increased by +27
•  » » » » 11 months ago, # ^ |   +6 same here, +45 combined, -25 actual rating change
•  » » » » 11 months ago, # ^ |   +10 +46 == -11 :/I think rating predictor might have been offset from div1 participant, but it should not be THIS drastic.Also, as described by Psycho12Killer there are some other issues where rating change doesn't make sense.
•  » » » » » 11 months ago, # ^ | ← Rev. 10 →   +3 my friend had + 108 but ended up with +124
•  » » » » » » 11 months ago, # ^ |   0 Yes, rating changes are going up/down/everywhere. Many are now providing examples of unfair/nonsensical rating changes. I really hope this issue is resolved.P.S Good for your friend :)
•  » » » » » » » 11 months ago, # ^ |   0 yeah , but it's really weird because CF predictor never gives less than the original rating change :)
•  » » » 11 months ago, # ^ |   +6 I had +68, ended up with -2
•  » » 11 months ago, # ^ |   +1 +80 but ended up with -8.Looks like those who got 4 or more AC had big increases in rating. Those with just 3 heavily suffered from rating loss, regardless of time penalty
•  » » 11 months ago, # ^ |   0 Same, CF-Predictor predicted +115 , got +33 only.
 » 11 months ago, # |   +7 I didn't understand the rating change fact. Before this contest i had a rating of 1510 and i became 74 (in division 2) and my rating increased by 104. There is another person who became 304 and his rating increased by 98 (his previous rating was 1530). Is it because this is an educational round and things are handled differently???
 » 11 months ago, # |   +3 CF Predictor show +74 Rating and Got +8 . don't know how they calculate it .
•  » » 11 months ago, # ^ |   +6 cfpredictor count with div1(( It shows + 56, get +1
•  » » » 11 months ago, # ^ |   0 so is there a problem? :| I am finding this odd.Will the ratings be updated again? :|
•  » » 11 months ago, # ^ |   +6 CF predictor +35 Rating -35 Became Specialist
 » 11 months ago, # | ← Rev. 2 →   +7 Div 2 only,Rank 55, previous = 1811, increase = + 125, new = 1936,Rank 77, previous = 1795, increase= = + 24, new = 1819.Also,Rank 7, previous = 1891, increase = +193, new = 2084,Rank 10, previous = 1757, increase = + 141, new = 1898,Looks very odd in my opinion, especially the second one.
•  » » 11 months ago, # ^ |   0 I gave an example above that is odder.
•  » » » 11 months ago, # ^ |   0 My second one now.
 » 11 months ago, # |   +22 Is there anything wrong with rating changes? BledDest MikeMirzayanov
•  » » 11 months ago, # ^ |   +12 Yes The Rating seems to be super mega unfair ?????
•  » » 11 months ago, # ^ |   +16 Prediction might be correct :/
 » 11 months ago, # |   +27 Isn't this weird!
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 Yup, that's wierd :p , i guess ratings will be recalculated...
 » 11 months ago, # |   +3 Rank 612 — rating 1640 => -42 Rank 1771 — rating 1695 => -53Why?
 » 11 months ago, # | ← Rev. 2 →   +3 I was 1526 and finished 441st in the contest and my rating went down, IT WENT DOWN.. HOW AND WHY???
 » 11 months ago, # |   0 These ratings are unfair ! Moderators please look into it. Some ambiguous result belowBEFORE CONTEST: User 1: Initial rating 1342 User 2: Initial rating 1120 AFTER CONTEST: User 1:(Contest rank div2: 1636) Final rating 1368 (increase of just +26) User 2:(Contest rank div2: 1816) Final rating 1214 (increase of +94)
 » 11 months ago, # |   -23 I don't think I will be joining rated educational rounds again , I will stick to regular rounds. Waiting for a day for rating change and systems tests + weird rating change (no thanks)
•  » » 11 months ago, # ^ |   0 You should also note this is experimental/first time they are doing such a contest, it is very possible they will fix this for this contest and future contests.
•  » » 11 months ago, # ^ |   0 Exactly ! If this is how experiments turn out, I will refrain from participating in "rated" educationals from now on. I was so positive and excited about new ratings...but now I am depressed as hell.
•  » » » 11 months ago, # ^ |   0 I was excited about going back to Expert after a long time but no, 18 points decreased, fantastic...
•  » » » 11 months ago, # ^ |   +6 It's just a number bro
 » 11 months ago, # |   +14
 » 11 months ago, # | ← Rev. 3 →   -41 Round should be unrated because the problems were very easy
 » 11 months ago, # |   +1 Just an assumption: Maybe while rating they considered only points i.e. number of questions solved. So all those who solved the same number of questions were ranked equally from rating point of view. I assume this seeing the anomaly in the comment section.
 » 11 months ago, # |   +5 looks like the new rating is based on the number of problems you solved, not your standing on this contest. It is unfair to change the rating rule without announcement before the contest.
•  » » 11 months ago, # ^ |   0 I think it's true, but i think it's very unfair
•  » » 11 months ago, # ^ |   +46 I'll fix it soon.
•  » » » 11 months ago, # ^ |   +6 ❤
•  » » 11 months ago, # ^ |   +1 http://codeforces.com/blog/entry/55950?#comment-396665 here they have mentioned that ranks will be sorted by penalty. They probably missed the penalty part.
 » 11 months ago, # |   +7 It's fixed, the ratings. Thank You.
•  » » 11 months ago, # ^ |   0 It's still not right.
•  » » » 11 months ago, # ^ |   0 I also see this.
 » 11 months ago, # | ← Rev. 2 →   -11 I solved 3 and initially my rating was increased by +26, which itself was less, and now they have revised the ratings and now it is +3 only. Seriously? -_-
 » 11 months ago, # |   +13 Very Good contest, I like it, very very good. Make more contests PLZ.
 » 11 months ago, # |   +13 Good Contest
 » 11 months ago, # | ← Rev. 3 →   +8 I noticed that the rating changes did not apply on the Rating page.
 » 11 months ago, # |   0 what the hell!!!!!!!!!!!!!How you count the rating ???? which process it has changed????
•  » » 11 months ago, # ^ |   +4 Dude your rating has increased by 101 points. Are you really that angry?I mean its all right to know how the rating changes work but you wayyy more angry than some of the other participants who've had their ratings decreased in spite of expecting an increase.
•  » » » 11 months ago, # ^ |   0 Dude I know my rating has increased.But I Want to know how they count the ratings.... That's It.
 » 11 months ago, # | ← Rev. 2 →   0 My rating increased by 6 and now it shows -11..why?
 » 11 months ago, # |   0 Hello codeforces i am new here can plzz somebody tell me about the ** hacking phase** round that started after the contest .. i dont know what i have to do in that round !!!
 » 10 months ago, # |   0 Can someone help me out with the E problem in this contest!!!Here is my code https://ideone.com/k8VHd2I don't know why its giving the wrong answer on input: 624 892Output should be 223068204,but it gives 243208479Thanx in Advance !