### McDic's blog

By McDic, history, 4 months ago, ,

다시 만나서 반가워요, 코드포스! (Nice to see you again, Codeforces!)

I'm again happy to introduce you to Codeforces Round #589 (Div. 2). Please look at following information for details:

The listed handles below are contributors. Thank you for all who listed!

For this contest, I tried to improve following things:

• Reasonable difficulty: At my last contest, less than 200 official participants managed to solve at least one of DEF. Especially, 1182D's problem difficulty rating is 2500 and 1182F's problem difficulty rating is 2900(no official solvers!). This is not good for Div.2 participants. In other words, my first contest was hell. So this time, I tried to make my second contest to have more reasonable difficulty than my first contest.
• Stronger data: There were 300+ successful hacks and almost 2000 sysfails at 1182B. At this time, I splitted testing phase into early phase and late phase. I'm bit worried, but I believe data will be stronger than my last contest.
• Compact statement: I remember many people complained about 1182C's super complex statement. I made very compact statements for this round. There is no problem with more than 10 lines of statement(except I/O section) in this contest.

I hope everyone can enjoy my second contest. Thanks in advance!

UPDATES:

1. If you want to discuss problems in chat after contest ends, come https://discordapp.com/invite/algorithms and you can enjoy discussion.
2. I have deleted my last problem(G) from this contest during testing period. I really wanted to include that beautiful problem in my contest, but nobody solved that problem for a week. That problem will be appeared in another Div.1 contest.
3. Scoring distribution is 500(A)-1000(B)-1250(C)-1750(D)-2250(E)-2750(F).
4. Editorial: https://codeforces.com/blog/entry/70162
5. Congratulation for winners!

WINNERS (updated):

1. PositionZero
2. supy_2
3. hitman623
4. lzqaq
5. skypool
6. LittleBeetle
7. Tsypkokokokoko
8. i_love_gnar
9. 8-_-8 (handle mentioning is not working on his handle)
10. wdk1745

• +1581

 » 4 months ago, # |   +185 McDic orz. It will be a great round!!!!!!!!!!!!!!
•  » » 4 months ago, # ^ | ← Rev. 3 →   -52 i don't think so. my arguments: 1. one 2. dva 3. tree (derevo)
•  » » » 4 months ago, # ^ |   +47 my arguments: McDic
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +20 McDic is geniosity O_o
•  » » » » » 4 months ago, # ^ |   0 McDic is so cute
•  » » » » » » 4 months ago, # ^ |   -13 aryaman is so cute
•  » » » » » » » 4 months ago, # ^ |   +13 farmersrice is cuter
 » 4 months ago, # |   +228 I like the compact statement part
•  » » 4 months ago, # ^ |   +52 The ghost is adorable awww
 » 4 months ago, # |   +136 This what they call learning from your failures :)
•  » » 4 months ago, # ^ |   +4 Yup, this is the best example of learning from the past.
 » 4 months ago, # |   0 Ideal time! I wish good luck to all of the participants!
 » 4 months ago, # |   +19 Wa! Another Korean round!
 » 4 months ago, # |   +10 I can still remember the last round QAQ. I get a wrong understanding on B.
 » 4 months ago, # |   +13 Congrats on your round McDic O_o
•  » » 4 months ago, # ^ | ← Rev. 2 →   +34 $\color{purple}{O \text{_} o \text{ !}}$
•  » » » 4 months ago, # ^ |   +7 O_o
•  » » » 4 months ago, # ^ |   +2 O_orz!
•  » » 4 months ago, # ^ |   +25
 » 4 months ago, # |   -14 Another Korean round! I think this round is well-prepared. Wish your high rating!
 » 4 months ago, # |   +285 I've never seen someone post about their previous mistakes on a round, and talking about how to make the next one better. What a good way of making the most of constructive feedback. I'm eager to see these improvements in the round. It would be cool if this example is followed by other contest writers. And by other writers I mean GreenGrape.
 » 4 months ago, # |   +23 Thanks a lot:)There is nothing better than Compact statement！look forward to a wonderful contest!
 » 4 months ago, # |   +18 My code was hacked for the first time in your previous round :). Hope this round will be fun.
 » 4 months ago, # |   +49 Many successful hacks is not bad. As long as these hacks are not if (n == 1).
•  » » 4 months ago, # ^ | ← Rev. 2 →   +73 But 2000 sysfails in B are bad.
 » 4 months ago, # |   +5 sounds like an awesome round Good Luck :D
 » 4 months ago, # |   +3 GOOD LUCK
•  » » 4 months ago, # ^ |   -43 NO
•  » » » 4 months ago, # ^ |   +6 Contributed to you being the lowest my fellow human :)
•  » » » » 4 months ago, # ^ |   0 tkx
 » 4 months ago, # |   0 finally .... tow of my solutions was hacked last round ... thanks you ,,
 » 4 months ago, # |   0 I hope it will be very good because it is hard
 » 4 months ago, # |   +14 I love how you are trying to improve your contest. Hope it will be a great contest! :D
 » 4 months ago, # | ← Rev. 2 →   +11 Welcome back McDic after 4 months with a new contest;
 » 4 months ago, # |   0 thanks for the improvement :)
 » 4 months ago, # |   -72 It must be unrated,right?
•  » » 4 months ago, # ^ |   -16 Rated?
•  » » » 4 months ago, # ^ |   -85 The comment is hidden because of too negative feedback, click here to view it
•  » » » » 4 months ago, # ^ |   -112 The comment is hidden because of too negative feedback, click here to view it
 » 4 months ago, # |   +1 Thanks a lot for all the hardwork. Particularly, reflecting on the previous mistakes is great <3
 » 4 months ago, # | ← Rev. 2 →   +42 Interesting blog . truly to say , I read every word of a blog (about contest) after a long time !!!!
•  » » 4 months ago, # ^ |   +7 so many world :D
 » 4 months ago, # |   +7 Is this some special round? I have never seen such upvotes on any contest announcement blog before.
•  » » 4 months ago, # ^ |   0 Twice the pride, double the fall
•  » » » 4 months ago, # ^ |   0 I hope that does not happen.
•  » » » 4 months ago, # ^ |   0 You dare question the power of McDic?
•  » » » » 4 months ago, # ^ |   +10 Is that a kind of fetishism?
•  » » » » » 4 months ago, # ^ |   -7 No, he is objectively a god
 » 4 months ago, # |   +28 First time to see someone writing on the past mistakes. Hope for a good round :D
 » 4 months ago, # | ← Rev. 2 →   0 McDic make me "out of competition".
 » 4 months ago, # |   -59 Soo much upvotes before a contest. Seriously what if this guy(dude) is like a politician who's promising what he can't execute?
•  » » 4 months ago, # ^ |   +82 after all, he admitted his mistakes in the last contest and is trying to make this one better.That's why he deserves these ups.
•  » » » 4 months ago, # ^ |   -33 Admittance doesn't matter, Results do. Y'all should at least wait and experience first. I guess that's why it's quite easy to scam y'all
•  » » » » 4 months ago, # ^ |   0 maybe you are right. anyway we'll see if it's a better one just a few hours later
•  » » » » 4 months ago, # ^ |   +46 I am in super pressure. QAQHope there will be no fatal issue on my second contest.
•  » » 4 months ago, # ^ |   -7 agree.
•  » » » 4 months ago, # ^ |   +2 why your comment has only 7 downvotes but still light coloured?
 » 4 months ago, # |   0 I will prove myself in this contest...In Shaa Allah.
 » 4 months ago, # |   -27 WTF? Why so many upvotes?
 » 4 months ago, # | ← Rev. 2 →   +10 In ready to compete in excellent contest!
 » 4 months ago, # |   0 Imagine if after all the upvotes the round isn't better than the previous one lol that would be funny as hell XD (just kidding I think it will be good)
•  » » 4 months ago, # ^ |   +13 Thats why I always keep my vote till the end of the round
•  » » » 4 months ago, # ^ |   +5 Ah geez, Rick, you shouldn't be so cynical
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Am f***ing Rick Sanchez C137, I can be what I want :D
 » 4 months ago, # |   -7 something new
 » 4 months ago, # |   0 nung nung
 » 4 months ago, # |   +7 It seeming a well-prepared contest. I think it will be an enjoyable one.
 » 4 months ago, # | ← Rev. 2 →   -53 I like nice weather :)
 » 4 months ago, # |   -19 i wish to you all It will be Great Round for all of us
 » 4 months ago, # |   -29 I suspect too many hacks or fst for B
 » 4 months ago, # | ← Rev. 2 →   -39 sorry
 » 4 months ago, # |   -17 More generic test case would have been better to understand problem B.
 » 4 months ago, # |   -16 One of those rounds where the pupils do A,B and then keep refreshing the ranklist for 1 hr.
 » 4 months ago, # |   -38 I hope you will not set problems with 4 levels of definitions in the future. And I hope coordinators will not approve such problems in the future.All that I can do now is to vote a blog down, but it was boosted by orzing schoolboys to 1k+, so probably it won't get downvoted. Or can it? There are 13k participants...
•  » » 4 months ago, # ^ |   +57 you are salty
•  » » 4 months ago, # ^ |   +3 I have no problems with multiple definitions as long as each of them is clear enough. Anyway, if you hate definitions, you may enjoy this gem 1120A - Diana and Liana.
•  » » » 4 months ago, # ^ |   +46 I have problems when the definitions are recursive. In today's problem we have 4 levels: 1) prime 2) g 3) f 4) answer. It is hard work to build a full picture of the problem in the head, it takes a lot more time than thinking of a solution and coding that problem. I think I'm not alone here.The problem you mentioned have many definitions and it is bad, but they are parsed easily.
•  » » » » 4 months ago, # ^ |   0 Fully agree with you
•  » » » » 4 months ago, # ^ |   +12 I think the examples given in statement does really help me understand how to connect all those definitions. I agree that it's not a good problem but your original comment seems to be a bit excessive. McDic do you mind explaining why do you have to include $x$ and $prime(x)$ in this problem? I feel that it does nothing but add a negative value to the problem.
•  » » » » » 4 months ago, # ^ |   +12 My original statement for C was full of math. I simply changed part of them to English sentences, step by step.
 » 4 months ago, # |   +33 This contest brought to you by the number $1000000007$
•  » » 4 months ago, # ^ |   +5 And I used $998244353$ from my template in E, and could not debug that :( Otherwise the code was correct.
 » 4 months ago, # | ← Rev. 2 →   -28 deleted
 » 4 months ago, # |   -60 damn wrong alarm about the good round. damn wrong.
 » 4 months ago, # |   -24 ARGH! Could you do less number theory problems next time?
•  » » 4 months ago, # ^ |   +63 By less you mean 0? I see 1 "number theory" problem.
•  » » » 4 months ago, # ^ |   -22 C and E is pure math, no programming at all. F i dont know.
•  » » » » 4 months ago, # ^ |   0 F is definitely not math.
•  » » » » 4 months ago, # ^ |   +15 Ok, I can agree that C felt a bit "mathy" and the statement was a little off-putting, but labeling E as pure math is just wrong.
 » 4 months ago, # |   -43 It is about math, not about programming.If you want to do a programming contest you can go to a programming contest site. Oh, wait...
 » 4 months ago, # | ← Rev. 2 →   +39 I feel like C's statement could be improved by using consistent variable names. I mean sth. like $\prod_{i=1}^{n} f(x,i)$ with $f(x, i) = \prod_{p \in prime(x)} g(i, p)$ where $g(i, p)$ is the maximum....would be much more understandable, or not?
•  » » 4 months ago, # ^ |   +13 It is not understandable either way.
•  » » 4 months ago, # ^ |   +49 CF team requested me to use less formula, but use more english sentence
•  » » 4 months ago, # ^ |   +54 The first version of this problem by McDic was like this. However, not every CF user knows this. Since we wanted to make the problem clear for everybody, and in the same time short enough, we decided to rewrite the statement using simple English words.
•  » » » 4 months ago, # ^ |   +22 Makes sense, but still could've defined $g(y, p)$ instead of $g(x, p)$ to be more consistent with the definition of $f(x, y)$.
•  » » 4 months ago, # ^ |   +1 calculate the number of N! for the prime P in X are NUM ,so the answer are the product of quickpow(P,NUM).
 » 4 months ago, # |   0 What was pretest 15 for C?
•  » » 4 months ago, # ^ |   0 15 pretest3 450283905890997363answer is 137055211
•  » » » 4 months ago, # ^ |   0 Thanks, I get this
 » 4 months ago, # |   +4 What the hell is pretest 5 in C
 » 4 months ago, # |   0 How to solve C ?
•  » » 4 months ago, # ^ |   0 For each prime in the prime factorization of x, it will appear in the answer exactly k times, if it appears k times in the iteration of 1 to n, so for instance, if n = 8, and x = 2, then the answer is 2^7. Now, how to count them fast? Simply count all n/prime^i, for all i, such that prime^i <= n. call this value sum. this can simply be done by calculating first n/prime, then n/prime/prime , etc. After this, calculate prime^sum, multiply to answer. Iterate for all primes.Unfortunately I'm getting a WA on test case 5, so I'm probably wrong somewhere, but I can't figure out where.
 » 4 months ago, # |   +9 How to solve E and F?
 » 4 months ago, # | ← Rev. 2 →   0 If I sent two correct decisions, which one will count?
•  » » 4 months ago, # ^ |   0 The most recent one I believe...
 » 4 months ago, # |   +25 Modforces :)
•  » » 4 months ago, # ^ |   +10 actually ($10^9 + 7$)forces
 » 4 months ago, # |   +18 I had to wake up at 5:50 am on a Sunday morning to write the contest, but it was (mostly) worth it!Good job McDic.
 » 4 months ago, # |   0 Whats B pretest 6???
 » 4 months ago, # |   0 How to solve E, I tried memoization, for all pairs of n,m size of grid, got TLE though....
 » 4 months ago, # |   +40 I found D's problem statement a bit vague, the line "All set should not be empty", I believe it could have been written as "No set should be empty". What about you guys?
•  » » 4 months ago, # ^ |   0 Good English
 » 4 months ago, # |   +1 What is pretest 4 in Problem B ?
•  » » 4 months ago, # ^ |   0 For instance : 2 2 0 0 1 1
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 4 4 2 0 3 1 1 3 0 3I don't know why the answer is 0 instead of 4. Do you know?
•  » » » 4 months ago, # ^ |   +1 Red is for row constraints and blue is for column constraints, check is where there has to be a black cell and 'X' is where there has to be a white cell so as you can see in the 3rd row 4th column there is a contradiction. Hope this helps
•  » » » » 4 months ago, # ^ |   0 Yes, I didn't get from problem statement that the input could be invalid. Thank you.
 » 4 months ago, # |   +53
•  » » 4 months ago, # ^ |   +17
•  » » » 4 months ago, # ^ |   +8 MikeMirzayanov isn't this code obfuscation?
 » 4 months ago, # |   -6 Pretest 12 in D? how to solve D?
 » 4 months ago, # |   +17 13444 Registered users, new Record?
 » 4 months ago, # |   0 what is pretest 13 in C?
 » 4 months ago, # | ← Rev. 2 →   +3 Is the intended solution of E $O(n ^ 3)$ DP? I saw someone passing E with this complexity, unfortunately mine TLEd at test 3. submission: 61507994
•  » » 4 months ago, # ^ | ← Rev. 2 →   +4 Mine passed with that complexity, you shouldn't use fastpow in such a deep loop, just precalculate every power.
•  » » » 4 months ago, # ^ |   +16 Thx for ur advice, the constant factor really sucks To be honest, a 2000 ms would be more reasonable
•  » » » » 4 months ago, # ^ |   +8 As far as i know, TL is 1s to cut off $O(n ^ 3 * log(n))$ solutions.
•  » » » » » 4 months ago, # ^ |   -8 Wow a log(250) is only 7, but it surely kills
•  » » 4 months ago, # ^ |   +3 Yes, it can be solved in $O(n ^ 3)$.My code: pastebin
•  » » 4 months ago, # ^ |   +8 $O(n^2)$ inclusion-exclusion, I guess.
•  » » 4 months ago, # ^ |   +5 can you please explain your approach ?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 It is somewhat similar to BZOJ 1801: [Ahoi2009]chess. U may read it’s solution if u know Chinese.The idea is to calculate $f(i, j)$, the number of combinations such that there are $j$ columns having at least one $”1”$ after filling up $i$ rows. Then the answer is $f(n, n)$.I believe u can derive the transition formula on ur own :)
 » 4 months ago, # | ← Rev. 2 →   0 I submitted the exact same code twice by mistake, and got -50 for it? :X
 » 4 months ago, # |   +13 That feeling when you find out that your code actually matched the samples before the end of the contest but as a matter of fact you forgot what the sample actually was in the first place so you thought your code had mismatched the sample and didn't submit codeA life-saving tip- don't keep yourself unfed for 16 hours before any contest.
 » 4 months ago, # |   -15 can someone tell me what's problem with my solution for problem — > 3 https://codeforces.com/contest/1228/my
•  » » 4 months ago, # ^ | ← Rev. 2 →   +33 dude, that link will send everyone to HIS/HER submissions page lol
•  » » » 4 months ago, # ^ |   -14 it's cool bro. It show my entire mind and you need to find out bug from that.
•  » » » » 4 months ago, # ^ |   0 not your mind, whoever clicks on that.
•  » » » » 4 months ago, # ^ |   +16 although this reply doesn't have a link, it sent me to google translate, and I still don't get it -_-
 » 4 months ago, # |   0 How come score 1250 for C while 1000 for B?Is C seriously easy for 2500 contestant?
•  » » 4 months ago, # ^ |   +5 Well, yes
•  » » 4 months ago, # ^ |   +8 hi wookje i am your big fan
 » 4 months ago, # |   0 Such an awesome contest . I got to learn so many amazing concepts.
 » 4 months ago, # |   +1 In Problem B Div 2, Please help me know why my code is getting runtime error in TestCase 6?https://codeforces.com/contest/1228/submission/61498112 (commented code)
 » 4 months ago, # | ← Rev. 2 →   +8 Although I had a terrible performance on problem D, I like the succinct Title Description very much.The simpler the topic is, the more favorable it will be for those who are not proficient in English, and the more favorable it will be for fair competition.Thanks a lot.
 » 4 months ago, # |   0 why this submission https://codeforces.com/contest/1228/submission/61492705 passed? Does here j var will not be overflowed?
•  » » 4 months ago, # ^ |   +1 The culprit is #define int long long 
•  » » » 4 months ago, # ^ |   0 oh, exact -_\
 » 4 months ago, # |   -18 Thanks for 3 combinatorics tasks. I liked them a lot. I think every math codeforces round should have 3/6 math tasks.
•  » » 4 months ago, # ^ |   +13 Can you clarify to me which 3 tasks are combinatorics?
 » 4 months ago, # |   0 Well, a lot of stsfails at B again?
 » 4 months ago, # |   +23 For problem D, you can also use this approach: Sort each adjacency list and hash it using Rabin Karp Every node with the same hash is part of the same partite.
•  » » 4 months ago, # ^ |   +3 In fact, you don’t need to use hashing — you can just store set of vectors
•  » » » 4 months ago, # ^ |   0 Thanks for pointing that out. I forgot that std::vector implements == and < operators.
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 Wow that's really neat solution. Here's my solution using the above idea.Please ignore my naive question in old revision.
•  » » 4 months ago, # ^ |   0 How to solve D?
 » 4 months ago, # |   +12 Wowwww... Great contest <3
 » 4 months ago, # |   +21 D seems to be an easy version of DOOFST in Codechef September Challenge.
 » 4 months ago, # |   +20 The round was awesome! But why would you warn the contestants about integer overflow in problem C? Isn't it a part of the problem to figure it out by yourself?
•  » » 4 months ago, # ^ |   +14 Many blue testers struggled in that. That's why I warned.
•  » » 4 months ago, # ^ |   0 And why even have $10 ^ {18}$. Problem would have been equally interesting with $10^9$
 » 4 months ago, # |   +4 How the System Testing done so quick even after such large number of participation
•  » » 4 months ago, # ^ |   +58 Lol.The question you asked matches the expression with your profile icon
 » 4 months ago, # |   0 Was the diagram for the sample input/output for 1228D - Complete Tripartite added partway through the contest or after the contest? I don't remember seeing it when I solved the problem.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 I think it was kind of bug. That picture was here for eternity.
•  » » » 4 months ago, # ^ |   0 Ah, okay, thanks!
 » 4 months ago, # |   +11 Thanks for the problem C test 3 overflow warning.
 » 4 months ago, # |   +3 Can you please fix the problem D?It mentions that "not all vertex sets should be empty" while it implies "all vertex sets should be non- empty" (which I figured out after the contest ended). Both statements are very different.
•  » » 4 months ago, # ^ |   +2 No, it mentions "All vertex sets should not be empty."
•  » » » 4 months ago, # ^ |   +43 This doesn't mean All vertex sets should be non-empty. All vertex sets should not be empty -> There should exist at least one non-empty set.
•  » » 4 months ago, # ^ |   +6 At first I also thought that some vertex sets can be empty but not all of them.
 » 4 months ago, # |   +8 Although a bit too many math problems, still a great round it was, I believe.I really enjoyed problem D. I haven't solved problems that require sharp observations for so long.Now I'm also curious about your problem G. Anyway, thank you for such a great experience!
 » 4 months ago, # |   0 I am literally losing my mind :/ , can someone explain why in problem C when in this code 61512229 I add this line "if (a==0||b==0) return false;" in line 10, I get WA in TC3? 61512212 , i mean it says overflow, but adding "if (a==0||b==0) return false;" should'nt give a different verdict in this problem :/ should it? someone pleaseeeeee help ;(
•  » » 4 months ago, # ^ | ← Rev. 2 →   -10 McDic first of all great contest thanks :D , second please help, seriously I am lost for words, I feel like the problem is from CF compiler itself, I am seriously losing it here...... I just added an "if" which doesn't even get to do anything there in TC3 but still get TC3 WA ;(
 » 4 months ago, # |   0 Position Zero! This is Tendo Maya. (((
 » 4 months ago, # | ← Rev. 2 →   0 Thanks to McDic, I'm purple ^_^
 » 4 months ago, # |   +5 Great contest thanks to McDic. Hope to make another contest!!!!!
 » 4 months ago, # | ← Rev. 4 →   +15 the system test of problem D is too weak.UPD: maybe using "too weak" is unappropriate, but I think it's a big slip.most submissions can't pass #48(it was added after system test).input: 3 1 1 2 output: -1 
•  » » 4 months ago, # ^ |   +46 I am sorry about such issue. I considered 7 types of graph and that was not enough :(
•  » » » 4 months ago, # ^ |   -67 How is a simple sorry justified for those who lost rating due to more wrong solutions accepted for Problem D?
 » 4 months ago, # |   +10 What happened to the candidate with 3rd rank.All his solutions are shown skipped?
 » 4 months ago, # | ← Rev. 2 →   +24 McDic Thank you for this awesome contest.
 » 4 months ago, # |   0 How to solve B. I could not find any idea
•  » » 4 months ago, # ^ |   0 The Editorial is Published . https://codeforces.com/blog/entry/70162
 » 4 months ago, # | ← Rev. 3 →   +3 I have a headache of problem C statement and tutorial. Very hard to understand the problem.
 » 4 months ago, # | ← Rev. 3 →   +3 Problem C.Does taking modulo with LLONG_MAX really matters?with %LLONG_MAX ACCEPTEDwithout %LLONG_MAX WRONG ON TC3By the way in local compiler both code were giving same answer.
•  » » 4 months ago, # ^ |   +20 Signed integer overflow is actually undefined behaviour; in your WA example, the compiler notices that you're diving a*b with b and automatically replaces it with a, meaning that your if condition never triggers. When you're doing %LLONG_MAX the compiler actually calculates the expression.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +6 But multiplication and division are in different instructions. So it should be like two long long int numbers multiplied and stored in another long long int variable(if it overflows wrong value stored here). Then in another instruction division takes place and should trigger if condition in my code.Or may be codeforces compiler is more smart then my local compiler :( that it can combine two different instructions, which is unexpected.REF. Same method for int is used here . Which should work for long long int also.
 » 4 months ago, # |   +5 While trying to hack during the contest I came across these submissions and I feel like this submission and this submission is almost the same and has been purposely modified to escape plagiarism. I request the officials to take appropriate action.
 » 4 months ago, # | ← Rev. 5 →   +5 For problem D,I don't know how to prove it, but this seems to be a solution. Observe a valid graph focusing on the degree of edges. In common cases, if a graph is valid, it can be divided into 3 sets, and the degree of vertexes in every set is n - size_of_this_set , and they should be the same. (so in a valid graph, it could have 3 type of vertex at most)When add all possible degree values up, the sum is 3n - sum_of_size_of_every_set, that is, 2n.Denote all possible degree values as a set $S={ s_k }$ .There are only four cases: case 1: S.size() = 1, which means every vertex has same degree $s$ . There should be $s+s+s = 2n$. The construct scheme is arbitrary, while every n/3 vertexes are in a set. case 2: S.size() = 2, $S={s_0,s_1}$ . If the graph is valid, there should be either $s_0+s_0+s1 = 2n$ or $s_0+s_1+s_1=2n$. The construct scheme is divide one type of vertexes in half .(actually, the number of this type must be even.) case 3: S.size() = 3, $S={s_0,s_1,s_2}$ . If the graph is valid, there should be $s_0+s_1+s2 = 2n$. Hash three types of vertexes into ${1,2,3}$. case 4: S.size() >=4 , -1. Seems enough , but I got Wrong answer on test 1461514754. Because it's not necessary and sufficient condition.So, in case 3, I make a check of all the edges to see if it's not valid, and passed all the test cases (for now).My solution: 61514951BTW：Nice round.BTW2：Sorry for my awkward expression...
 » 4 months ago, # |   0 It was a great contest although I didn't get to participate in it. Problem C was a very interesting and challenging problem. I feel bad for not participating this round.
 » 4 months ago, # |   0 For question C of this Contest I have a Problem.In my editor the code is compiled and run succssfully and giving the correct answer but in codeforces editor it is giving wrong answer. I want to know why this is happening??
 » 4 months ago, # |   0 Hi, How can I avoid overflow in question C?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 if(((a*b)%LLONG_MAX)/b==a) then it doesn't overflow, else overflows...... check special cases a==0 && b==0 too so you don't get RTE for dividing a number by 0.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 If you don't mind this $log(t)$ time, you can calculate the max $sz$, which satisfy $a_{i}^{sz}<=t$ , by the code below:  while (t >= a[i]) { t /= a[i]; sz++; } When you reach $a_{i}^{sz}$, there is no need to get larger. So this will keep all your variables below t(or some other threshold).
•  » » » 4 months ago, # ^ |   +3 Thank you.
 » 4 months ago, # |   0 In problem D. I find number of connected components in complement graph and if this number is 3 then answer is yes and sets is this connected components. why is this solution wrong? I recieve wrong answer in test 11.
•  » » 4 months ago, # ^ |   +17 You also have to check that there is no edge between vertices in the same component
•  » » » 4 months ago, # ^ |   0 Yes. thanks. I got Accepted.
 » 4 months ago, # |   0 I am not getting my solution accepted[submission:61543290].As per test case 7,expected output is different from answer but I am getting correct output on my code using IDEYour text to link here...
 » 4 months ago, # |   +8 This round is way better than the last one.
 » 4 months ago, # |   0 Could you please update tasks' ratings?
•  » » 4 months ago, # ^ |   +8 Do you mean difficulty ratings for my problems? It will be updated by Codeforces team, not me.
 » 3 months ago, # |   0 Can anyone explain the question D easily? I didnt understand the question for a long time. TIA :)
•  » » 3 months ago, # ^ |   0 Make 3 vertices sets to make each pair of sets forms complete bipartite graph.