### Vovuh's blog

By Vovuh, 19 months ago, ,

Hello!

Codeforces Round #479 (Div. 3) will start on May 6 (Sunday) at 14:05 (UTC). It will be the first Div.3 round in the history of Codeforces. You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to Ne0n25 for testing the round.

UPD: Thanks a lot to testers dreamoon, eddy1021, step_by_step and egor.lifar who agreed to test the problems and found the mistakes. Now we are ready to start the round!

I hope that you will like the problems. If suddenly something does poorly with difficulties of the problems, then we will adjust the difficulties in the next Div. 3 rounds.

Briefly about myself. My name is Vladimir Petrov, I am studying at the 3rd year at Saratov State University and from the high-school I am studying at SSU Olympiad Training Center. In ICPC I participate in the team "Saratov SU Daegons" with PikMike and Ne0n25. I like reading and watching science fiction. I’ve read "Song of Ice and Fire" 3 times and wait for publication of 2 more volumes.

Good luck!

UPD2: Editorial

UPD3:

Congratulations to the winners (official results):

Rank Competitor Problems Solved Penalty
1 cMartynas 6 69
2 nimphy 6 117
3 iman12 6 124
4 mandinga 6 128
5 raffica 6 144

Congratulations to the best hackers:

Rank Competitor Hack Count
1 greencis 36:-8
2 Tlalafuda__Tlalafu 10:-1
3 STommydx 9:-1
4 dalex 8:-7
5 dreamoon 4:-3
6 shnk 2

97 successful hacks and 297 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A kuzmoid 0:01
B c650Alpha 0:04
C Milhous 0:08
D Milhous 0:11
E s0mth1ng 0:09
F DoveDragon 0:14

• +451

 » 19 months ago, # |   +32 What is the relationship between div3 & div2 problems. For instance A div1 is equal to C div2
•  » » 19 months ago, # ^ |   0 This contest is for div3 only. I do not think there will be a relationship between div2 and div3. I mean can something be easier than Div2A? Maybe Div3A+Div3B+DivC are so close to Div2A. We will see after the round :)
•  » » 19 months ago, # ^ |   0 This contest is only Div3 , so i don't think there's any relationship with Div1 or 2.
•  » » 19 months ago, # ^ |   0 "We plan to include in these rounds simple training problems that will help beginner participants to gain skills and to get new knowledge in a real contest."
 » 19 months ago, # |   +21 I found a mistake for you :)) Please correct it.
•  » » 19 months ago, # ^ |   +26 Thank you, it is fixed now!
 » 19 months ago, # |   +8 So will there have Educational Round like the time before updating? :P
 » 19 months ago, # |   +8 Finally!
 » 19 months ago, # |   +23 Last three lines was awesome . :D
•  » » 19 months ago, # ^ |   +5 :P
 » 19 months ago, # |   +8 "The round will be hosted by rules of educational rounds..." Honestly, It's really boring! Given that this is a div3 and problems should be easy.. Then what is the use of the hacking phase ??!!
•  » » 19 months ago, # ^ |   +179 We will experiment with formats of Div. 3 rounds, but there are some reasons to start with rules of Educational Rounds: I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack for non-trivial problems tests in Educational rounds much more complete than pretests in regular Codeforces round. my plan is that Div. 3 rounds will not affect regular Div. 1/Div. 2 rounds in terms of schedule. It means that Div. 3 rounds (as well as educational) can't use time of KAN to coordinate them. They completely prepared by writers with my little help. It is much easier to write a round by rules of Educational Rounds than Codeforces: issues in writer solutions/validator/checkers affect a round less, less requirements on completeness of tests, etc.
•  » » » 19 months ago, # ^ |   +9 This is what I have been waiting for long time: "**I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack**". Hacking is a good way to develop debugging skill. But a div3 participants should not spend the whole time trying to hack a problem just to increase rating instead of solving another problem.Thanks Mike.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   -18 But what about the feeling of DIV3 participants. I really enjoyed codeforces round DIV1 / DIV2, due to div1 and div2, DIV3 is also should not be affected. div3 also must be same as daily codeforces round not educational type.
•  » » » » 19 months ago, # ^ |   0 As Mike said, div2 rounds are not affected. So you can just ignore div3 rounds.
 » 19 months ago, # |   +23 First time I saw about myself in any round announcement.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +12 You might want to take a look at this!
•  » » » 19 months ago, # ^ |   +9 Your link is not clickable. Check it.
•  » » » » 19 months ago, # ^ |   0 where you saw you?
 » 19 months ago, # |   +7 It's rated for me so :D
 » 19 months ago, # |   +23 unofficial participator for the first time :) :D
 » 19 months ago, # |   +5 Why extended ACM-ICPC? Why not like a normal Codeforces round?
•  » » 19 months ago, # ^ |   0
 » 19 months ago, # |   +44 Will I become Div.4 user if I lose rating in Div.3 contest?
•  » » 19 months ago, # ^ |   -15 As of 5/5/2018, there is no such thing as a Div. 4 user. The lowest is Div. 3.
•  » » » 19 months ago, # ^ |   +52 Dude, don't you know about sarcasm?
•  » » » » 19 months ago, # ^ |   +8 and neither humor
 » 19 months ago, # |   -14 Hello, If this round is following Educational Round formats than I want to bring something to your notice. See the picture attached. My friend solved Problem A and his solution for problem C failed. I solved Problem C and my solution for problem A failed. I just want to point out that Problem C was tougher than Problem A and anybody who solves tougher question should get better rank. I think people will say that it is for learning new skills and I should not concern myself with the rating. But I still think that this is unfair.
•  » » 19 months ago, # ^ |   0 Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy.So, I think, there will be no issues with Div3 problems, as at some points, we will figure out that it is eventually too easy, regardless of which problem in a contest (A, B, C, D, E, or even F).In other words, soon we will realize none of any Div3 problems will be any tough to be obliged to be distinguished.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +9 Still, the point system is better than the penalty system in my humble opinion.
•  » » 19 months ago, # ^ |   +2 ACM-ICPC scoring is used in many contests.If you don't like the format of educational round, you don't have to participate.If you don't want to be rated because of these rounds, you can always do virtual participation of solve problems regardless.
•  » » » 19 months ago, # ^ |   -6 I am fine with whatever format you want to use, I am asking is it fair?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   -21 1) You complained about the rules of the contest.2) You just said "I am fine with whatever format"3) ?????????4) Now you ask if the rules are fair.Yes, they are since your signed up knowing them.As I said, if you disagree with this type of scoring just don't participate. If you are annoyed at messing up on problem A check over your code more before you submit.
•  » » » » » 19 months ago, # ^ |   +19 Hmm, thanks for helping.
 » 19 months ago, # | ← Rev. 2 →   0 One more chapter is going to open from May 6 (Sunday) at 14:05 (UTC)..!!
 » 19 months ago, # |   -39 Div3 => noobs?
•  » » 19 months ago, # ^ |   +15 once you, too, was thus noob
•  » » 19 months ago, # ^ |   +25 Hey bro cyan isn't too hot either. We're all noobs, just some less nooby than others.
•  » » » 19 months ago, # ^ |   -12 Effective...
 » 19 months ago, # |   +39 So which one do you like better? The books or the TV show? Vovuh
•  » » 19 months ago, # ^ | ← Rev. 2 →   +52 I like books better than the TV show, but the TV show is also wonderful =) Especially Natalie Dormer =)
•  » » » 19 months ago, # ^ |   0 You've probably meant Natalie Dormer
•  » » » » 19 months ago, # ^ |   +9 Oh, yes, you are right, i made a mistake
 » 19 months ago, # |   -11 Can't Wait :D****
•  » » 19 months ago, # ^ |   -29 Still messi is better than ronaldo
 » 19 months ago, # |   -17 Hoping For short Problem statement
 » 19 months ago, # | ← Rev. 3 →   -10 As CF is introducing div3 for begginers, it is also good to change title/color to make it interesting for begginers, like 1000-1200 is begginer, <1000 is newbie !!
 » 19 months ago, # |   -120 Earn bitcoins while browsing the Internet https://getcryptotab.com/1065838
 » 19 months ago, # |   0 Looking forward to concise problem statements without unnecessarily long storylines!
 » 19 months ago, # |   -54 I think it's need to make div 4 for under 1000.
 » 19 months ago, # |   +10 Div3 finally comes! No more falling scores!
•  » » 19 months ago, # ^ |   +8 One can only hope^_^
•  » » » 19 months ago, # ^ |   +9 OK, then just bless!
 » 19 months ago, # |   -27 is it rated?
•  » » 19 months ago, # ^ |   -17 lol
 » 19 months ago, # |   -35 tourist do you want to join us in div 3 :) ?!!
•  » » 19 months ago, # ^ |   +36 don't worry, they'll open div 0 for him
•  » » » 19 months ago, # ^ |   -25 for tourist? I think Petr has higher priority in the current time.
•  » » » 19 months ago, # ^ |   -10 see who will put problems for him Your text to link here...
•  » » 19 months ago, # ^ |   +4 He does not even need to look to the problems to solve them. :)
•  » » » 19 months ago, # ^ |   +12 lol.u can't solve some problem even by reading them :)
 » 19 months ago, # |   +17 Will div 3 participants be allowed to take part in div 2 contest?
•  » » 19 months ago, # ^ |   +8 Obviously...
•  » » » 19 months ago, # ^ |   0 Will it be rated for div 3 contestants?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 when it is only div 2 contest then the user who's rating is less than 2100 can participate in this round and when both div 1 and div 2 round will be held , user who's rating less than 1900 can participate in div 2 contest as a official participant.... official means rating will be update
 » 19 months ago, # |   0 How many problems will be there?
•  » » 19 months ago, # ^ |   +1 You will be offered 6 problems
 » 19 months ago, # |   +7 Waiting for a DIV2 contest. The sooner, the better. The more, the merrier. :)
 » 19 months ago, # |   0 "8093" Registration in Div 3 !! wow <3 .
 » 19 months ago, # |   -6 I usually solve C in div2..Which prob i should choose to solve in div3 ??
 » 19 months ago, # |   -6 Problem A : Print "Hello World"
 » 19 months ago, # |   +6 HTTP Response: 500, 502. Website failed.
 » 19 months ago, # |   +50 20 minutes of penalty is too much.
•  » » 19 months ago, # ^ |   +3 for a 2-hour contest, indeed. 20 minutes seems better with 3~5 hours contest.
 » 19 months ago, # | ← Rev. 2 →   -35 Failed at BDon't understand what C is askingInput #1 of F is wrong? Surely largest is 5~ cba to attempt as maybe I'm misreading like CRIP, time for gaming instead
 » 19 months ago, # |   +11 AH ? I can't register while the contest is running !What a pity!
 » 19 months ago, # |   +67 20 minutes of penalty is too much.I used 19min to solve all the problems.But I got 1 penalty.. doubled the time..
•  » » 19 months ago, # ^ |   +18 20 mins of penalty is standard ACM rules. It encouages coding correctly instead of coding fast, which I think is ok. Also, the contest is targeted at people who can't solve all problems in 19 mins :)
•  » » 19 months ago, # ^ |   0 Penalty is calculated as the sum of times each problem solved (+ 20mins penalties), not as the time of the last solution. So it's not doubled because of that, don't worry :)
•  » » » 19 months ago, # ^ |   +2 You're right.. But I got "502 Bad Gateway" for 30 mins LOL
•  » » » » 19 months ago, # ^ |   0 So? That's completely irrelevant to the discussion. Nobody cares how well you did in a div3 contest, mate.
 » 19 months ago, # |   +31 Thanks Vovuh for this round , and thanks MikeMirzayanov for Div3 !!! This is the first time that i am able to solve all problems .
 » 19 months ago, # |   0 Spending 30 minutes to solve the last problem. Is it a little bit slow compared to how such contestants like me (1800s-rating guys) are supposed to be?
 » 19 months ago, # |   +25 Why are there some (not all) unrated accounts in the official standings?
•  » » 19 months ago, # ^ |   +3 What exactly? Please, give me some examples of such handles.
•  » » » 19 months ago, # ^ |   +22 official rank #1 for me is readers5 and rank #4 T_van for example
•  » » » » 19 months ago, # ^ |   0 That happens pretty often in div2 if not all the time, even in older contests.My guess has always been that some of those are smurf accounts created by high rated people just to be on the top spots in a contest. A lot of them are legit skilled people on their first contest, but some are left inactive after one contest.
•  » » » » » 19 months ago, # ^ |   +8 Yes but the thing is that it's not supposed to happen with the new div3 rounds.
•  » » » » » » 19 months ago, # ^ |   0 Sorry, you're right. Forgot that.
 » 19 months ago, # |   -42 I think this was too easy even for div 3.
•  » » 19 months ago, # ^ |   +11 I agree. In Div 2, very few experts (the highest eligible rating) solve the set. In this one nearly every specialist and their mother solved it (not really but you get the idea). You never see 200+ eligible participants solve the set in a round.
•  » » » 19 months ago, # ^ |   0 Yes, It should be a little harder so only about 50 or less gets full. NOT 200. Even me solved the whole set! Maybe it should be for users whose rating less than 1400
 » 19 months ago, # |   +10 First time in my whole life! I solved all problems! (but... It is div3)
 » 19 months ago, # |   0 Holly cow, I'm experiencing something in Java I never ever experienced in a contest!For problem "C" I'm doing a sort using Arrays.sort. My code times out (it takes more than 2 seconds for testcase 6). But, if I randomize a little bit the input, i.e., instead of doing:  a[i] = in.nextInt(); // "in" is the input stream I do:  a[(i + (n / 2)) % n] = in.nextInt(); the solution passes!Does anybody know how can this be?
•  » » 19 months ago, # ^ |   0 It seems that there are arrays that take O(n^2) time to sort in Java, using Arrays.sort(): http://codeforces.com/blog/entry/4827Most likely test case 6 is such an array and was designed to discourage people to use the O(nlog(n)) solution instead of the linear one...
•  » » » 19 months ago, # ^ |   0 Is there simple linear solution for C?
•  » » » » 19 months ago, # ^ |   0 Yes, you can use quickselect to find the k-th smallest element in an array in linear time: https://en.wikipedia.org/wiki/Quickselect
•  » » » » » 19 months ago, # ^ |   0 In C++, you're right (because there is std::nth_element). But I mean that in many standard libraries, there is sort, but there isn't nth_element. So in this languages linear solution will be much harder.
•  » » » » » 19 months ago, # ^ |   +5 No, quickselect has a worst case of n^2, similar problem to your sort
•  » » » » » 19 months ago, # ^ |   +1 Quickselect have O(n^2) worst time, nth_element in C++ have O(n*logn) worst time, but here is Medians of medians algorithm (or Introselect variation), which have O(n) worst time.But it's not simple (or not obvious at least).
 » 19 months ago, # | ← Rev. 3 →   +32 It seems the difficulty is something like:Div3 A, B = Div2 ADiv3 C = Div2 BDiv3 D, E = between Div2 B and Div2 CDiv3 F = Div2 C
•  » » 19 months ago, # ^ |   +1 I think Div3B is too simple for Div2B
•  » » » 19 months ago, # ^ |   0 Possibly. Honestly Div2 A and B feel more or less the same difficulty, at least in my opinion. Only thing I've seen is that Div2 B sometimes has annoying edge cases, so yeah you're probably right, it's probably A level.
 » 19 months ago, # |   +21 Intially i was not able to look at question and was getting a continuous error of Bad Gateway 502
 » 19 months ago, # |   0 :(
 » 19 months ago, # |   0 I Accepted F after contest finished 1 sec...(Sorry for my poor English)
 » 19 months ago, # |   0 how can solve the ploblem c?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Case 1:- If k=0 then check if arr[0]=1. If yes the print -1 else print arr[0]-1.  Case 2:- Ifk==nsimply printarr[n-1] Case 3:- Check the value of arr[k-1]. If arr[k]==arr[k-1] then print -1 else print arr[k-1] This is sample test case 2.This is all in a sorted array.
•  » » » 19 months ago, # ^ |   0 oh ,i forgot to judge if arr[0]==1, anyway,thank you!
•  » » 19 months ago, # ^ |   0 Sort the elements, and the k'th element (1-indexed) is your answer. If k = 0, then just subtract 1 from the first element.The no solution cases are when the k'th element equals the k+1'th element (why?) and when k=0 and the first element is 1, because subtracting 1 would be outside of your range (you may be tempted to try to be clever and subtract 2 so you don't have to handle that case separately, but that fails if the smallest element is 2).
•  » » » 19 months ago, # ^ |   0 I don't get how, for k=0, there could be an answer different than -1.I mean, as I read it, there is no x «such that exactly 0 elements of given sequence are less than or equal to x.», regardless the value of the first element. Am I missing something?What exactly do you mean by «because subtracting 1 would be outside of your range»? I guess you refer to the range [1, 10^9], but why should I subtract something?Thanks
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 k=0.Output a number x such that 0 (no) elements from the sequence are less than x.If the smallest element in the range is l and max is r.Then.If you take an element >r then all elements will be less than r and k=0 will not be satisfied.If you take an element>=l and element<=r then some elements in the range will be less than x and again k=0 will not be satisfied.As for last case if l==1 then you can output 0 because no(0) elements will be less than 0. However since the answer must be in the range[1,1e18], in this case the answer will be 0. For all other cases output l-1.
•  » » » » 19 months ago, # ^ |   0 Say your sequence is 10 26 4, and k=0.Simply output the number 3, and that is 0 elements from the sequence are less than or equal to 3. If the smallest element is 1, then there is no answer that is in the range from 1 to 1 billion.
•  » » » » » 19 months ago, # ^ |   0 That make sense. I should have been less superficial. Or more, depending on how you view it :) Thanks Kognition and horcrux2301
 » 19 months ago, # | ← Rev. 2 →   0 Can E be solved using this logic: LINK
•  » » 19 months ago, # ^ | ← Rev. 2 →   +5 if you mean E,E is simple. Just for each connected component see that every node is connected to exactly 2 other nodes.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I tried this for problem D.Take a boolean array check[n] and mark all as false. Then I tried making chains. Take the first element and mark it as true and this will start a new chain. Then for each other false element in array check if it can be added to the chain started by this element, either by appending it to the beginning or to the end. If yes mark this as true too. For beginning, check if the new element divided by 3 is equal to first element in chain or if new element multiplied by 2 is equal to first element in the chain. Similarly we do for the end.However, I couldn't figure out how to decide a way to print all these chains in a valid manner. Is there any way to do figure this part out.
•  » » » » 19 months ago, # ^ |   +1 I think your approach is wrong or maybe i understood it wrong anyways this is what i did: A move consists of dividing by 3 (if divisible) or multiplying by 2. This means given a number we are taking away 3's and giving it 2's. So a state once reached will never be reached again. Why? Because to reach that state either you need to multiply by 3 or divide by 2 both of which is not a part of move. So what we can do is treat every element as starting element once and try generating the sequence from elements available. If all the elements are used you can just print that sequence.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 This can be done by thinking of an array as a directed acyclic graph, and do a topological sort.
•  » » » » » 19 months ago, # ^ |   0 No need for directed graph...just make undirected edges and start from any end that fits into any one of given two operation.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Thanks, soham_1234. I got it.Can you check out the link I shared? There is a formula given to get the count of all cycles. Is it correct?
•  » » » » 19 months ago, # ^ |   0 No, take the graph4 6 1 2 2 3 3 4 4 1 1 3 2 4Number of edges = 6. Number of vertices = 4. Number of connected components = 1. 6-4+1=3, but the answer is 2 because there is only one connected component and it isn't a cycle.
•  » » » » » 19 months ago, # ^ |   0 Got it. Thanks.
•  » » » » 19 months ago, # ^ |   0 it has defined cycle differently not the traditional cycle we know of. See the examples and diagrams.
 » 19 months ago, # |   0 The contest page was not visible for the first 10-15 minutes, and the problems were not accessible for the mentioned period (well,at least for me). So will it be justified to keep it rated?
 » 19 months ago, # |   0 Can someone help me? http://codeforces.com/blog/bakrocker
 » 19 months ago, # | ← Rev. 2 →   0 was this contest rated as written in the blog ?! "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." I didn't see any rating for the problems.
•  » » 19 months ago, # ^ |   +3 Ratings will be changed after whet Open Hacks Phase ends (in 12 hours approx)
 » 19 months ago, # |   +47 GOGOGOGO SO FST LKE A SNIC X
 » 19 months ago, # |   +4 Thnx Vovuh for your efforts in making harder pretests. Really Appreciate it ! :-)
 » 19 months ago, # |   +4 The round was good! Even though problems were easier quality remained high. It kind of reminds me of Atcoder Beginner Contests.
 » 19 months ago, # | ← Rev. 2 →   +4 Angel.Yan (rank 578)'s submissions and __beyond (rank 581)'s submissions are almost the same (the differences are libraries, useless fors, spaces, blank lines). I believe they are cheating. Correct me if I'm wrong. Vovuh
 » 19 months ago, # |   0 problem C ;Output Print any integer number x from range [ 1 ; 10 9 ] such that exactly k elements of given sequence is less or equal than x . If there is no such x , print "-1" (without quotes).equal to not equal than Vovuh
•  » » 19 months ago, # ^ | ← Rev. 2 →   +3 Thanks, but next time please send it via private message.
•  » » » 19 months ago, # ^ |   0 I can just delete the comment if you want !
•  » » » » 19 months ago, # ^ |   0 Not necessary =)
 » 19 months ago, # |   0 Can anyone please explain why this submission got TLE while this one got AC ? I just changed the language from Java to C++. There was no I/O issue as well. I was clueless about my solution getting TLE and then in just hit and trial I converted it to C++ and it got accepted. :(
•  » » 19 months ago, # ^ |   0 Vovuh explained here: http://codeforces.com/blog/entry/59281?#comment-428862"6-th test is anti-qsort test especially for Java solutions. Replace int with Integer and it will be ok."
•  » » » 19 months ago, # ^ |   0 Oh! Okay. But when it says specially for Java solutions, isn't it a bit unfair? Anyway, Thanks for the contest Vovuh ! :)
•  » » » » 19 months ago, # ^ |   +29 If I didn't add this test, somebody else would. So it's fair i think
•  » » » » » 19 months ago, # ^ |   +1 Okay, got it Vovuh . Thanks for the Contest !
 » 19 months ago, # |   0 The fixed problem at the beginning will affect penalty and so the rating changes.., many contestants have 2 or more problems tested at the same time and submitted earlier so..
 » 19 months ago, # |   0 Is it possible to solve problem E using disjoint set union?
•  » » 19 months ago, # ^ | ← Rev. 6 →   0 my idea, maybe wrong. dsu = new DisjointSetUnionWithRollbacks for component in componets: flag = 1 for edge in component.edges: dsu.add(edge) for edge in component.edges: dsu.erase(edge) if dsu.numIgnoredEdges > 0: flag = 0 dsu.add(edge) ans += flag UPD: solution 2 dsu = new DisjointSetUnion for component in components: [head: tail] = components.edges flag = 1 for edge in tail: if dsu.add(edge) == EDGE_IGNORED: flag = 0 ans += flag In fact, we are to check, if after each edge deletion, component becomes tree.However, this solution is very complicated.Simpler ones: component is good if each node touches 2 edges component is good if it contains k nodes and k edges (sorry, it turned out to be wrong)
•  » » » 19 months ago, # ^ |   +38 "2. component is good if it contains k nodes and k edges"Actually, this approach is incorrect as this is not a cycle component.
•  » » » 19 months ago, # ^ |   0 I tried this problem using disjoint set union. If I find a cycle, I checked if the degrees of the nodes having this edge is 1. If they aren't 1, that means that connected component is no longer a valid cycle. If they aren't in the same connnected component, then I check if any of them were part of a cycle. If they were, then I change that value to 0, signifying that the corresponding cycle is no longer a cycle. Can someone tell me what I'm missing here? I got a Wrong Answer on test case 18.
 » 19 months ago, # |   0 Really we enjoy this contest . Thankyou Codeforces team
 » 19 months ago, # |   +6 Look at what Tlalafuda__Tlalafu does in hacks section (for problem B). He specifically wrote several solutions with this kind of code if (n == 3 && t == "LOL") { cout << "MEM"; return 0; }And then he hacks himself several times.Is this kind of behaviour legal in codeforces?
 » 19 months ago, # | ← Rev. 2 →   +6 Why can't I hack solutions on C++17? The system gave me an "Unexpected verdict" several times on different solutions. Please rejudge all the hacks with this verdict, it is very important.UPD: I can't even hack my own solutions which aren't on C++17. What's wrong, Codeforces?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +1 Could you please explain the test you used to hack so many F solutions? I tried to find something in common in the solutions you hacked but failed to see the pattern. Your test seems to be tricky.
•  » » » 19 months ago, # ^ |   +11 Div 3 noobs like me didn't know that using unordered_map makes the solution O(N^2).http://codeforces.com/blog/entry/44731
•  » » » » 19 months ago, # ^ |   0 So, this was an "anti-hash" test against STL's unordered_map... I'm new to Educational Rounds so I didn't think people actually use dirty tricks like anti-hash and anti-quicksort. I don't get why people do this but this broke all solutions with unordered_map instead of map. Well, learned something new, won't be using unordered_map on contests next time :)
•  » » » » » 19 months ago, # ^ |   0 I believe this hack does not necessarily mean that you should not use unoredered_map at all. The thing is, the standard hash function which accepts integer values does nothing, it just returns the same number it accepts, so there is no problem with hashing itself.The problem is solely with buckets count, because in a hash table there is a remainder operation "key % buckets_count" and in case if you take a lot of numbers with the same remainder, unordered_map will work slowly.However, if you use it and call reserve(10000000) in the beginning, you will fix the amount of buckets to be over 10 millions and the hack simply would not work anymore. The maximum time conplexity will not be more than 100n, which is enought to pass 1 second time restriction.Correct me if I am wrong.
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +9 This wasn't exactly what I meant, but I agree that reserve() will work for F. The problem is that this workaround will only work for this particular problem because of the 10^9 restriction. Given less tight bound (10^18) it will still fail.And with 12-hours open tests you can even generate counter test for any particular hash function from universal family (not necessarily identity) and any particular buckets_count. The only way to protect against this attacks seems to be random sampling of hash function from universal family with good source of entropy.The point was — why do you even need to bother about such details on a contest if you can just use map instead? It might be a bit slower but at least it has worst-case guarantees and it allows you to focus on a problem itself.Problem solving is fun. I don't think it's fun to protect against hashmap-attacks.
•  » » » » » » » 19 months ago, # ^ | ← Rev. 4 →   +5 I see, I would myself prefer map container to make sure my solution will work.I was just too disapointed by the fact that a programming contest makes us choose the structure which 10 times faster in 0.0001% cases and 10 times slower in 99.9999% cases, that is why I tried to figure out the way how to use unordered_map and remain unhacked.Anyways, codeforces is not only about good ideas of solutions, it also requires us to know the low level of how c++ works, it is just as it is.
•  » » 19 months ago, # ^ |   +19 I think it's because some of the author/tester solution fail on the same test.
•  » » 19 months ago, # ^ |   +16 Testers' solutions receive time limit exceed, because of this your hack gave an "Unexpected verdict". I hope I have fixed it now. Sorry for long delay.
 » 19 months ago, # |   0 Will there be any tutorial for this round??
•  » » 19 months ago, # ^ |   0 It's already posted, here
 » 19 months ago, # |   0 is it rated for newbie ?
•  » » 19 months ago, # ^ |   0 Yes
 » 19 months ago, # |   0 Hello Vovuh. My rating is 1500 because I hasn't joined any contest before. However you said "if your rating is less than 1600, then the round will be rated for you." So why I'm not rated after this contest.
•  » » 19 months ago, # ^ |   0 The contest has not done with the large test case. So we need to wait for the final result and you will see your ranking changes.
 » 19 months ago, # | ← Rev. 3 →   0 i passed all of the problems!! yayyy
 » 19 months ago, # |   +6 When will system testing start?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +4 Yeh same question,i wonder how can i know when the sys test will start ? the contest just said "Finished"
 » 19 months ago, # |   +1 When will the ratings be updated?
•  » » 19 months ago, # ^ |   0 Ratings are updated as of posting this.
 » 19 months ago, # | ← Rev. 2 →   0 Pls, somebody explain, how my solution http://codeforces.com/contest/977/submission/37965169 for Problem F was hacked. But when i changed "unordered_map" to "map" it got accepted. It seems realy strange to me
•  » » 19 months ago, # ^ |   0 Afaik Unordered_map is slower than normal map.
•  » » » 19 months ago, # ^ |   +1 That'_s not true. unordered_map is getting slower when many hash collision happens. Otherwise, unordered_map is much faster than normal map.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 unordered_map is based on Hash table. Normally a search operation of hash table works in amortized(1) but worst is O(N) (caused by hash-collision). std::map, on the other hand, is based on red-black tree, which has O(logN) complexity in search operation on average. Your solution was hacked by anti-hash test.
 » 19 months ago, # |   0 Why unrated participants get rated in this round?You said that they need to do at least 2 Div.2 contest and solve at least 1 problem to get rated
•  » » 19 months ago, # ^ | ← Rev. 2 →   +13  Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you. ` So although unrated participants are not trusted, they are still rated.
•  » » » 19 months ago, # ^ |   -7 But why they but them in a separate room?
 » 19 months ago, # |   0 Can anyone tell me what's wrong with my F approach? 37990081
•  » » 19 months ago, # ^ |   +3 You ignored MAP[A[i]] that was originally stored.test : 9 10 11 12 8 9 10 11 10 11ans = 4 yours = 3
•  » » » 19 months ago, # ^ |   +3 Oh.. i thought map in c++ overrides values that exists already just like in Java
•  » » 19 months ago, # ^ | ← Rev. 2 →   +3 Yes, so change your "//m.insert(mp(a[i], m[a[i] — 1] + 1));" to "m[a[i]]=max(m[a[i]],m[a[i]-1]+1);", and this is the AC code which has a little change from your code
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 Yes, i got AC, thank you ;)Thought C++ maps work as Java maps where you just use map.put(v1, map.get(v1 — 1) + 1) and it overrides v1 value if exists
 » 19 months ago, # |   +7 How about the ratting changes? Can a people get the same ratting changes if he got the same place(among rated people) in div 2 and div 3 contests?
 » 19 months ago, # |   0 It's a wonderful effort for beginners like us to learn and improve !
 » 19 months ago, # |   +1 It grow the internal effort of beginner programme,make hope to became a good programmer, I like it
 » 19 months ago, # | ← Rev. 2 →   +18 You might also would like to take a look at the incredible achievement of Tlalafuda__Tlalafu, who made 10 wrong submissions for problem B and found bugs in all of them! Думаю, что вам также будет интересно увидеть невероятный успех Tlalafuda__Tlalafu, который не поленился отправить 10 неверных решений по задаче B, а после этого смог обнаружить баги в каждом из них!
•  » » 19 months ago, # ^ |   0 He just hardcoded a wrong output for some random input 10 times... is this sarcasm?
 » 19 months ago, # |   +16 is no one here concern about rating inflation? In a normal div2 round, it seems like there's usually about 100 users who will be promoted to expert and some of the expert will drop, but this round, there seems to be about 250 promoted with 0 expert demoted.
 » 19 months ago, # |   0 I would request the host to conduct more number of Division 3 contests. I am sure that many other users like me with rating less than 1600 are finding it difficult to solve Division 2 problems easily and obtain better ranks. I would suggest to conduct 1 Division 3 contest for every two Divison 1/2 contests so that we can gain confidence and hopefully aim to perform better at Division 1/2 contests. I would like the opinion of other people too. Thanks.
 » 16 months ago, # |   0 great round