### Retired_MiFaFaOvO's blog

By Retired_MiFaFaOvO, 6 years ago,

Hello everyone! Codeforces Round #268 is coming soon! We invite you to participate in this round. It will be held on September 20th at 17:00 MSK.

Problems have been prepared by me. Thanks xyz111 and dhh1995 for giving me the idea of some problems. Thanks vfleaking, foreseeable, MinakoKojima, Ruchiose and xllend3 for testing.

I also want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It is my first round on Codeforces. Hope you will enjoy this round.

You'll help a boy named Little X in this round. Good luck and have fun :)

UPD

Round has finished. Thanks for participating.

Congratulations to the winners.

Div. 1

Div. 2

Congratulations to ecnerwala, the only participant to solve the problem D!

Unfortunately, no one has solved the problem E in both divisions.

Editorial for the round will be added tomorrow.

UPD

Editorial is here.

• +256

 » 6 years ago, # | ← Rev. 2 →   +10 Looking at the level of the setters, I would say a Div 1 round would have been possible :( Edit: I thought today's round was their round, don't mind :P
•  » » 6 years ago, # ^ |   +6 So you got one xd.
•  » » » 6 years ago, # ^ |   0 OMG, I am blind, ignore that :D
•  » » 6 years ago, # ^ |   +28 Too much red users in one blog...
 » 6 years ago, # |   0 another china round! good luck everyone :)
 » 6 years ago, # |   +22 Why "Little X", but not simply "x"? :)
•  » » 6 years ago, # ^ |   +42 Maybe the oxymoron (little big x) is intended?
•  » » » 6 years ago, # ^ |   0 Звали?
•  » » 6 years ago, # ^ |   +1 x is usually name of the variables, it could create confusion too :P
 » 6 years ago, # |   +12 It's the first time to see contest announcement before the start of previous contest :D
 » 6 years ago, # |   +8 Why are there so many numbers in the handles of the problem setters ? =D
•  » » 6 years ago, # ^ |   0 No, many handles for testing not problem setting
•  » » » 6 years ago, # ^ |   +11 many Numbers in handlesnot many handles
•  » » » » 6 years ago, # ^ |   0 Thanks :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +44 Because 233 is a special number in Chinese... It means "LOL"(Laugh Out Loud) in English which shows a man bursts into laughter. And we use repeating "3" many times strengthen the funny meaning. 233 is a photo id in a famous forum of China. here is the photo.
•  » » » 6 years ago, # ^ |   +11 Link is broken.
•  » » » » 6 years ago, # ^ |   +35 poor link...
•  » » » » » 6 years ago, # ^ |   +12
•  » » » » » » 6 years ago, # ^ |   0 what is APEX KEK means
•  » » » » » » » 6 years ago, # ^ |   -8 Oh right, I should've included a see more on Know Your Meme and apex = top (it's made using rarely used words, like nay = no). I just found the "poor link" reaction seriously funny :D
•  » » » » » » » » 6 years ago, # ^ |   +8 Oh...I thought LOL is the short from Lots Of Laughter... After clicking your URL, I have just known LOL is short from Laugh Out Loud......
•  » » » » » » » » » 6 years ago, # ^ |   +16 It's hard to say what people want it to be (and it doesn't really matter), it could even be short from "Lots of LOL" :D
•  » » » » » 6 years ago, # ^ |   0 fix the photos.
 » 6 years ago, # |   -30 YessssssChinese round -> more math
•  » » 6 years ago, # ^ | ← Rev. 2 →   +20 There is actually going HackerRank contest "Ad Infinitum — Math Programming Contest September'14 ". It lasts 2 days :). Give it a try.
•  » » 6 years ago, # ^ |   -19 First of all, before this commented is downvoted, I would like to point out that codeforces is for developing your algorithmic knowledge. Depending on your definition of "algorithmic", math could be considered an algorithm; and this is a perfectly valid opinion. However, what is the point of competing in coding contests if all you want is math all the time. Every time you post, it's about math; nothing else. Coding contests are meant to introduce you to varied ways of thinking, not limited to math.
•  » » » 6 years ago, # ^ |   0 I'm agree with you and I don't know why many people downvoted you. Someone like math, someone not. But everyone love coding. I think we shouldn't care about kinds of problems.
 » 6 years ago, # |   +28 Oh, god, I think I can't participate any more Chinese round, because it is 6:00 am here.Btw, I guess more testers you have then more difficult this round will be.. let's see if it is correct.
•  » » 6 years ago, # ^ |   +6 early sleep and early wake~ After brushing teeth and washing face, you can participate the Chinese round relaxedly
•  » » 6 years ago, # ^ |   0 Have fun getting used to the U.S :)
 » 6 years ago, # |   -9 nice
•  » » 6 years ago, # ^ |   0 newSolar BigGod is here! You are a Yellow! But you say you are only div2.....
•  » » » 6 years ago, # ^ |   +3 When did I say that? I didn't use this Id for more than half a year.
 » 6 years ago, # |   +5 So, its going to be a typical chinese round . good luck everyone :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +15
•  » » » 6 years ago, # ^ |   +4 Сделано случайно.
 » 6 years ago, # |   +6 My last contest in summer! I'm going to school on Tuesday! Hope a good contest! Good Luck!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 I think it's everyone's last contest in summer in northern hemisphere :|
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes I think you're right!
•  » » » 6 years ago, # ^ |   +15 It's not your "last contest in summer" when you don't compete :| (Dabbe)
•  » » » » 6 years ago, # ^ |   +3 (nice) :D
•  » » 6 years ago, # ^ |   0 :|
•  » » 6 years ago, # ^ |   +10 It is already 20th of September. What kind of summer do you have?
•  » » 6 years ago, # ^ |   0 I had to think it's autumn already...
 » 6 years ago, # | ← Rev. 2 →   0 I have registered for the contest, but due to time constraints (I have to participate in a qualifying round of some other contest), I will not be able to participate for the entire 2 hours. Can I appear as a virtual participant (If I participate for the first hour of the contest)?
•  » » 6 years ago, # ^ |   0 No, if you submit during contest, it will be counted in your actual participation and rating changes will also apply. So it is better to take the entire contest as a virtual contest at some suitable later time.
 » 6 years ago, # |   +9 I will try to help Little X as much as possible but can Little X tell us score distribution ?
 » 6 years ago, # | ← Rev. 4 →   +16 Attention please,it's a Chinese round!There is reason to believe that it's impossible for the konjacs(its Chinese name ‘juruo’ means the people with low level like me)to improve rating.Good luck to every super cattle(you may be able to understand it)! TAT
 » 6 years ago, # |   +7 Many GranMaster & Master for prepare this round. My premonition told to me that "be careful with tricky test"
 » 6 years ago, # |   0 Ehm, score distribution?
 » 6 years ago, # |   +24 It seems that I will participate in the next contest (Div2) Officially :D
•  » » 6 years ago, # ^ |   +16 The hell is your graph?
•  » » 6 years ago, # ^ |   +3 I am sure , someday , your graph will be a great inspiration for many many coders !!!
•  » » » 6 years ago, # ^ |   0 Thanks :) hope that also
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 You were right. Welcome back to the hell, fella :D
•  » » » 6 years ago, # ^ |   0 yep I did it :D
 » 6 years ago, # |   +20 500 — 1000 — 2000 — 3000 — 3000 :(
 » 6 years ago, # |   0 B(div1) 4 7 9 2 4 5 7 If someone need.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 The answer is "YES 1 1 1 1", right?
•  » » 6 years ago, # ^ |   0 would it be correct if ans is YES 1 1 1 1 ?
•  » » » 6 years ago, # ^ |   0 Yes. ) But any people have answer : "NO".
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Or 3 5 8 2 3 5 (sometimes they remove numbers from first set without checking if first set stay valid) Edit: the answer is "NO", but some were giving for output "YES 0 1 1"
•  » » » 6 years ago, # ^ |   0 Also when a == b some codes enter inf.loop
 » 6 years ago, # |   +1 what was the hacking case in div-1 B...my solution got hacked :(
 » 6 years ago, # |   0 How to solve C ??
•  » » 6 years ago, # ^ | ← Rev. 10 →   0 I took the following greedy approach: for n <= 8, run recursion else 1 * 2 = 2 3 * 4 = 12 2 * 12 = 24 5 - 6 = -1 7 - 8 = -1 -1 - -1 = 0 for i > 8 && i <= n ( i * 0 = 0 ) 24 + 0 = 24 
•  » » 6 years ago, # ^ |   0 I used the following : for n<4 print NO for n=4/n=5 find solution by hand for n>=6 n - (n-1) = 1 1 - 1 = 0 for all i = 5 to i = n-2 i * 0 = 0 you are left with {0,2,3,4} - just do 2*3*4+0 
 » 6 years ago, # |   0 How do we solve Div2 Problem C?
•  » » 6 years ago, # ^ |   +2 There are several ways to solve it. You can see that with N < 4, there is no answer. With N = 4, you can easily take (1 + 2 + 3) * 4 = 24. N = 5, 2 * 4 = 8, 3 * 5 = 15, 8 + 15 + 1 = 24. From N = 6, 4 * 6 = 24, 3 — 5 = -2, -2 + 2 = 0, 0 * 1 = 0, then for i from 7 to N, 0 * i = 0, and finally, 24 + 0 = 24.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I took special cases for 4,5,6 and and for n>=6used pre-created sequence for 5 and 6 based on even or odd n,made every element n and n-1 as (n)-(n-1)=1 and multiplied all the ones in the end.
 » 6 years ago, # |   +1 Can anyone share his/her approach in Div2 C problem ?
•  » » 6 years ago, # ^ |   0 If n is even and >= 4: 1 * 2 * 3 * 4 = 24 n-(n-1) = 1, (n-2) — (n-3) = 1 and so on. So just multiply the 24 with the ones.If n is odd and >= 4: 5 * 4 + 2 + 3 — 1 = 24 n-(n-1) = 1, (n-2)-(n-3) = 1 and so on. Same.There is no answer if n < 4.
•  » » » 6 years ago, # ^ |   0 Great. Got it thanks :)
•  » » 6 years ago, # ^ |   0 for n >= 6 erase all numbers except 2,3,4 using: (5 — 6 + 1) * z for n = 4 and n = 5 — hardcoded answer
•  » » » 6 years ago, # ^ |   0 Yes got the idea now couldn't think about it in contest :(Thanks :)
 » 6 years ago, # |   0 How to solve Problem D of Div. 2 ?
•  » » 6 years ago, # ^ |   0 My solution was, to just use pair(value,pos) in a set, and modify the set comparing function to consider only the first value. Then just keep checking if each element has its match in either A or B. hope it passes final tests :)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 I pretty much did the same. Got hacked. :-(Edit 1:- I got what is wrong with my solution. Edit 2:- I never considered that empty sets are allowable.
•  » » 6 years ago, # ^ |   +1 Your graph is inspirational !!!
•  » » 6 years ago, # ^ |   0 It's a bipartite matching problem ;)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Hm, i had two maps, one where i stored if there exists some number, and one where do i keep position of that number in initial array. Then, for every number, check map1[a-array[i]], map1[b-array[i]], if there is both do sth, if there is only one put it into the set, if there is none return -1. See my code for details UPD: It failed on systest, so this approach may be wrong
•  » » 6 years ago, # ^ |   +1 Pick a number in the list, say x. Then we are interested in whether a-x and b-x are also in the list. If1) Neither are in the list, then partitioning is not possible.2) If only a-x is in the list, then both x and a-x go into set A3) If only b-x is in the list, then both x and b-x go into set B4) If both are in the list, then this is inconclusive. We need to further check b-(a-x) and a-(b-x) according to the same rules (for example, if only b-(a-x) is in the list then all of a, a-x, b-x, and b-(a-x) go into set B). The implementation of this is pretty straightforward, though in contest I mishandled the a=b case (which requires special handling as a-x=b-x=b-(a-x)=a-(b-x)=...). See 7882478.
•  » » » 6 years ago, # ^ |   0 Why do we need to check further ??? Can you give test ??
•  » » » 6 years ago, # ^ |   0 i got it on contest , but i missed when cout no
•  » » 6 years ago, # ^ |   -10 hopcroft-karp bipartite matching
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +8 Hii, palmerstone, I like your approach using Hopcroft karp, but I am having trouble understanding the case when both a-x and b-x (along with x) are present in given array. Here's a part of your code if (!c && !d){ flag = false; break; } /*...*/ if(!flag) puts("NO"); how did u came to such conclusion that when both a-x and b-x are not present, there can't be any possible matching?
•  » » » » 6 years ago, # ^ |   0 What do you mean? x is an element of the given set. If both a-x and b-x are not present then it is certainly not possible to include x in any of the sets, is it? Hence not possible.
•  » » » » » 6 years ago, # ^ |   0 Oh yes. Thanks, I get it now... By the way can you please tell what does array L and R store in your implementation of hopcroft-karp ??
•  » » 6 years ago, # ^ | ← Rev. 4 →   +16 My solution for div2 D/div1 B:Assume that b>a because we can switch them anyway and b=a is trivial case. Let x be the smallest value which hasn't been assigned yet to either of the sets. If there exist a value b-x, then we have to pair values x and b-x into set B because value b-x can't be paired into set A because a
•  » » » 6 years ago, # ^ |   0 Can anyone tell me the greedy approach to solve div1 B?
•  » » » » 6 years ago, # ^ |   +2 Have you really requested a greedy approach to this problem in reply to comment where greedy approach was explained?
•  » » » » » 6 years ago, # ^ |   0 Actually , I have seen a few greedy accepted solutions . But could not understand their proofs.
•  » » » » » » 6 years ago, # ^ |   +13 OK, so here you got greedy solution with full explanation and proof: http://codeforces.com/blog/entry/13836#comment-188500 ...
 » 6 years ago, # |   +2 What's the solution for problem C? Is it some kind of greedy/constructive algorithm based on number theory, or is it dynamic programming? The numbers are from 1 to N, so I assumed it was a number theory problem but couldn't come up with a solution.
•  » » 6 years ago, # ^ | ← Rev. 4 →   +2 For numbers up to 3 answer is 'NO'. Solution for 4: 1 * 2 = 2 2 * 3 = 6 6 * 4 = 24  Solution for 5: 5 - 3 = 2 2 + 1 = 3 2 * 3 = 6 6 * 4 = 24  Other solutions: N - (N - 1) = 1 (N - 2) - (N - 3) = 1 ... 1 * 1 = 1 ... <- solution for 4 if N is even or 5 if N is odd 
•  » » 6 years ago, # ^ |   0 Just notice this if(n<4) no soln if(n==4) 1*2*3*4=24 if(n==5) 4*5+3+2-1=24 and for all other numbers, if n is even then you do the 4 thingy and keep doing i+1-i=1 for all the numbers, and at last do 24*1=24 as many times is you need same thing for odd n, just you would use 5 thing
•  » » 6 years ago, # ^ |   0 You can get the 24 by using 2, 3, 4 or 1, 2, 3, 4. For the neighbor number, say, i and i + 1, we can get 1 by using - operator, and 1 can be eliminated by * with other number. Then I think you get the answer:-)
•  » » 6 years ago, # ^ |   0 if n is less than 4, obviously no solution. Then 2 cases, if n is even, we can reduce the sequence to 1,2,3,4 (after which we just multiply each element one at a time). By subtracting n and n — 1, multiplying 1 and 1, then n — 2 and n — 3 and so on.. if n is odd, you can similarly bring it to 1,2,3,4,5, we can reduce to 2,3,4 by doing the following: 1 + 5 = 6, 6 — 3 = 3. After this we just multiply each one again. Hope its clear :)
•  » » 6 years ago, # ^ |   0 A much easier solution is to get 1 by doing n-(n-1) and then 1-1=0. Now do i*0=0 for all i from 5 to n-2. And then do 2*3*4 = 24. For n<=6 pre calculate the ans. I hope you get it.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 mine is same as rishul_nsit Sol Link
 » 6 years ago, # |   0 This contest reminds me of the Codeforces Round #146 (Div. 1) which was prepared by WJMZBMR... Codeforces Round #146 (Div. 1)
 » 6 years ago, # |   +5 To those who have problems with div. 2 C here is my approach:First print out the answer for cases n <= 5. Then for n > 6 you realize that you can make 24 by multiplying 6 and 4. Then you are left with the burden of creating n — 2 more operations, thus, you subtract adjacent numbers so you get a long chain of 1's, be careful that you cannot use 6 and 4 again. Then you simply keep alternating between: 1 — 1 = 0 1 — 0 = 1until you are left with 1 or 0 then you can just do either 24 + 0 = 24 or 24 * 1 = 24I did this approach during this contest and it seems to work. I was a bit dumb for the first hour because I forgot to print out "YES" at the beginning >.<
•  » » 6 years ago, # ^ |   0 Haha I forgot to print "YES too :PMy solution was as follows: the n = 4 is easy, because we can just multiply 1 * 2 * 3 * 4 = 24. The n = 5 is a tiny bit trickier, but we have 4 * 5 = 20, then 20 + 2 + 3 — 1 = 24. Now, if n > 5, we can take the two largest numbers, n and n-1, and subtract n-1 from n to get 1. Now, our list is 1, 2, 3, ..., n-3, n-2, 1. If we multiply the two 1s, we are left with 1, 2, 3, ..., n-3, n-2, which is the list for n-2, a smaller case! This means that n = 6 will work, since we can reduce it to the n = 4 case, n = 7 will work, since we can reduce it to the n = 5 case, and so on.
•  » » 6 years ago, # ^ |   +13 my answer is 1*2*3*4*(6-5)*(8-7)*...*(n-(n-1))=24 for n is even 5*4+3+2-1*(7-6)*(9-8)*...*(n-(n-1))=24 for n is odd
 » 6 years ago, # |   +18
•  » » 6 years ago, # ^ |   0 Our Little X is in upper case. Too big!!
 » 6 years ago, # |   0 Fuck math with no programming!
•  » » 6 years ago, # ^ |   +88
•  » » » 6 years ago, # ^ |   +18 Thanks, that's what I was asking for!
•  » » 6 years ago, # ^ |   0 Got butthurt? Go away.
•  » » » 6 years ago, # ^ |   0 Why so serious?
•  » » » » 6 years ago, # ^ |   +5 Because he was rude, used swear word and continues math-hate here which I'm completely fed up with.
•  » » 6 years ago, # ^ |   +13 I am not sure, but only the last problem seems to be mathematical one.
•  » » » 6 years ago, # ^ |   0 First one was also mathematical more than programming I'd say. But, a major chunk of programming is maths and logic, so it is only expected.
•  » » » » 6 years ago, # ^ |   +8 Of course all the problems are about math here(discrete math mostly), but here, I believe people mean complicated math by saying "fu**ing math again", but noticing that 6*4=24, a*0=0 and a*1=a.
 » 6 years ago, # |   +8 That was one fast system test!
 » 6 years ago, # |   0 Why so weak pretests??? I guess lots of Bs will fail. Also there was too many WA2 in problem A... For constructive problems, first sample should be more difficult. :|
•  » » 6 years ago, # ^ |   +1 IMHO, pretests complexity is completely up to the Problem Setter.
 » 6 years ago, # |   +19 I spent all 2 hours on problem D but still cannot finish coding it...Calculating "lexicographically smallest" one is very confusing, and I couldn't make solution without very complex iteration. Doesn't there exist any simpler solution?
•  » » 6 years ago, # ^ |   +8 Indeed. If it weren't for this "lexicographically smallest" than it would be doable with centroids and that kind of stuff, but it is a significant obstacle :/.
•  » » » 6 years ago, # ^ |   +8 Yes. Thinking about centroid is fun, but I think main part of this problem is more complex part, because only 1 people solved it despite thinking about centroid is not so hard...
 » 6 years ago, # |   +1 Like 90% of 469D - Два множества has failed tests. Lol!
 » 6 years ago, # |   +1 Wow, system test over in 10 minutes this time!
 » 6 years ago, # |   +7 thanks for the fast system test~ I think I could back to blue.
•  » » 6 years ago, # ^ |   +16 I think just like you :/
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Me too :\Edit: Hey, we both stayed in div1! :D
 » 6 years ago, # | ← Rev. 5 →   +9 problem A:for n=1,2,3: nofor n=4 : 1*2*3*4for n=5 : (3*1+5-2)*4for n>=6 : 2*3*4+(6-5-1)*7*8*...*n
 » 6 years ago, # |   0 for div 2 B And D what is the bug in my solutions ??Code_B
•  » » 6 years ago, # ^ |   +3 For D: 1 2 2 1 
•  » » » 6 years ago, # ^ |   0 as i understand from this casea-x can be equal to x ,, is this right ??
•  » » » » 6 years ago, # ^ |   0 Yes.
•  » » » » » 6 years ago, # ^ |   0 still WA on the same case ?? Code_DIm I using the right approach ??
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Try this test:3 5 62 3 4Your solution is totally wrong
•  » » 6 years ago, # ^ |   0 about D: |cpp| if (n % 2) { puts("NO"); return 0; } <|| it will fall on the case 3 2 6 1 2 4because 2-1=1.
•  » » » 6 years ago, # ^ |   0 as i understand from this casea-x can be equal to x ,, is this right ??
•  » » » » 6 years ago, # ^ |   0 right.
•  » » 6 years ago, # ^ |   0 about B: Your check for intersection doesn't look right. See if you can find your error here: if ((x >= a[j].first && x <= a[j].second) || (y >= a[j].first && y <= a[j].second))
•  » » » 6 years ago, # ^ |   0 can you please explain why this is wrong?
•  » » » 5 years ago, # ^ |   0 Same question, please explain what's wrong here?
•  » » » » 5 years ago, # ^ |   0 Seriously... 17 months agoAnyway, look at the conditions inside the if statement. What is it doing? Is it checking that the two segments overlap, or if one segment is completely within the other segment? What we want is for the two segments to intersect, one segment does not necessarily have to completely contain the other.
 » 6 years ago, # | ← Rev. 5 →   0 Isn't this code wrong 7871552 ?? Test: 2 1 0 01 52 47 7UPD:The inputis illegal sorry.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I think it is wrong. The answer should be 0, but it is giving 1. oh! Inputs are not valid.
 » 6 years ago, # |   +14 Ehh..if (n % 4 == 1) { ... cout<<"3+1 = 4\n"; ... }There wasn't any pretest for n % 4 == 1? It's really disappointing :\
 » 6 years ago, # | ← Rev. 2 →   0 My solution for div-1 B using dinic's algorithm for maxflow TLEd :(I thought it would run in O(E * sqrt(V)) time as all edges are of unit length. Can anyone please let me know why dinic would be suboptimal? Isn't it the same as Hopcroft-Karp for unit graph?My Submission
•  » » 6 years ago, # ^ |   0 The nodes in the subgraphs can have at most 2 degrees. I think you didnt need such a complicated algorithm
•  » » 6 years ago, # ^ |   +3 My implementation of hopcroft-karp got Accepted in 514 msSolution
 » 6 years ago, # |   0 By the way, somebody solved problem E in Division 1...
 » 6 years ago, # |   +101 printf("24 * 1 = 1\n"); and Failed A...What a sad story :((
•  » » 6 years ago, # ^ |   0 printf("24 + 0 = 24\n"); :((Same story
•  » » » 6 years ago, # ^ |   0 Err, what's wrong with 24 + 0 = 24 ?
•  » » » » 6 years ago, # ^ |   +3 My code for n=4 prints in the end 24 + 0 = 24
•  » » 6 years ago, # ^ |   0 same story got 1 wa because of that
 » 6 years ago, # |   +8 Great test for problem D Div 2. Lots of Failed System Test
 » 6 years ago, # |   0 Can you give me an example on which my code doesn't work ? ( Sorry for my poor English) http://codeforces.com/contest/468/submission/7883022
•  » » 6 years ago, # ^ |   +3 Why would everybody use tonns of #define? It puts my bum on fire.
•  » » » 6 years ago, # ^ |   0 Because it's easier to write MP than make_pair or something else... You write faster
•  » » » » 6 years ago, # ^ |   -20 It makes code harder to read in my opinion. Especially when I see that 50% of code are definitions for "for" and other shit.If you use snippets you can write fast enough. As for me is more important to think fast, not write.
•  » » » » » 6 years ago, # ^ |   0 FOR0(x[i],8) vs. for(x[i]=0;x[i]<8;x[i]++) not only saves keystrokes, but also reduces probability of typing errors.
•  » » » » » » 6 years ago, # ^ |   -6 Ok-ok. I understand, I am bad programmer if I don't use #define.
•  » » » » » » » 6 years ago, # ^ |   +5
•  » » 6 years ago, # ^ |   0 2 8 10 4 6 
•  » » » 6 years ago, # ^ |   0 It's well... output : YES 1 1
•  » » » » 6 years ago, # ^ |   +11 Sorry. Try this. 3 12 14 5 7 9 
•  » » » » » 6 years ago, # ^ |   +8 Thank you very much for this example :). Now, I understood why my code doesn't work
 » 6 years ago, # | ← Rev. 2 →   +1 I can not understand the reason why many of the chinese authors make hard and mathy problem set. In my opinion, contest's easy problem should be easy. Otherwise it is not motivating enough for people to participate.
 » 6 years ago, # |   +3 I've entered for the next div2 contest.The konjac(its Chinese name ‘juruo’ means the people with low level like me) has no human rights.
 » 6 years ago, # | ← Rev. 5 →   +5 winter is coming
 » 6 years ago, # |   +13 when will the ratings be updated?
 » 6 years ago, # | ← Rev. 3 →   0 About Div1 B. Does anybody have a case with an odd n and positive answer? Or could explain why this is possible? I assumed this wasn't possible during the contest, but apparently it is. Maybe I misunderstood the problem.
•  » » 6 years ago, # ^ |   0 1 10 20 5
•  » » » 6 years ago, # ^ |   +3 5 is in the group A and 10-5 is also in the group A
•  » » » » 6 years ago, # ^ |   0 Oh i see, thank you.
•  » » » » » 6 years ago, # ^ |   0 No problem. :D
 » 6 years ago, # | ← Rev. 2 →   0 can someone explain why this solution is incorrect? http://codeforces.com/contest/469/submission/7867443
•  » » 6 years ago, # ^ |   0 you should use resize not reserve
•  » » » 6 years ago, # ^ |   0 reserve only reserves space but the size of your vector stays the same. it is only useful for example you read numbers and push them back of a vector. the vector resizes itself when you push back sometimes. if u know how many numbers u are going to push back then u reserve some memory and when u push a number back of the vector it doesnt allocate new memory
•  » » » » 6 years ago, # ^ |   0 I understand. Thank you !
 » 6 years ago, # |   0 How to solve Div 2D/ DIV 1B ?
•  » » 6 years ago, # ^ |   0 the numbers create a group of chains. just have a look at my code: http://codeforces.com/contest/469/submission/7880049
•  » » » 6 years ago, # ^ |   0 Can you please tell me what is wrong with my solution : http://codeforces.com/contest/468/submission/7883509
 » 6 years ago, # |   0 Task D div 2 (Two Sets) Test Case 9: How could the correct answer be YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?when it is stated in the text: If there is a way to divide the numbers into two sets, then print "YES" in the first line.
•  » » 6 years ago, # ^ |   +6 You should know that {} is a set. it is an empty set.
•  » » » 6 years ago, # ^ |   0 It is like sharing 5 apples between you and me. You take all of the apples and I get none of them. But what we just did was sharing :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 NoteIt's OK if all the numbers are in the same set, and the other one is empty.
•  » » 6 years ago, # ^ |   0 You Didn't read this Note:"Note It's OK if all the numbers are in the same set, and the other one is empty."By the way, I got WA too in this case :(
 » 6 years ago, # |   0 Can any one please point out the mistake in my code. I am a newbie and am unable to find the glitch in CODE 469D. Thanks in advance
•  » » 6 years ago, # ^ |   0 In your solution you can use a number in 2 sets at the same time. check this: 3 20 18 5 15 3
•  » » » 6 years ago, # ^ |   0 Its answer should be NO
 » 6 years ago, # |   +17 When will they update ratings?
 » 6 years ago, # |   +11 Chinese Round again, so difficult problems again...
 » 6 years ago, # |   +3 Can anyone tell me what's wrong with my code for problem D, please?7882442Thank you!
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Check this test:10 12 143 2 10 9 4 9 3 2 5 10 Answer is:YES 0 0 1 1 1 0 0 0 1 0Edit: Sorry. Test is incorrect.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Explanation: Some numbers may occur several times and you should put some of them in set A, and some other in set B.Edit: It's not true. My mistake.
•  » » » » 6 years ago, # ^ |   +9 That's not true, the problem statement specifies that the numbers are distinct.
 » 6 years ago, # |   +8 very interesting and enjoyable problem indeed..i enjoyed this very much :D
 » 6 years ago, # |   +4 I have a question regarding this submission 7868179 Div.2 problem A .. I unsuccessfully tried to hack the solution using a testcase where the algorithm will try to access h[100] while the size of the array is actually 100! so the last element i can access is h[99], but the hack was unsuccessful .. any explanation ??
•  » » 6 years ago, # ^ |   +3 When you access beyond the range of an array in C/C++, it gives an undefined behavior. This undefined behavior may or may not throw an exception.
 » 6 years ago, # |   +3 My first time doing the first three problems . Best wishes.
 » 6 years ago, # |   0 So much math, it's awesome round!
 » 6 years ago, # |   0 Retired_MiFaFaOvO Thanks! It was a great Round!Could anyone clarify on grading policy? I've successfully submitted solutions for 2 tasks without penalties or resubmissions but my final round score is negative why it could be so?Thanks!
•  » » 6 years ago, # ^ |   0 Cuz you have 1497th (-520) place whereas you had 977th place at previous round.
 » 6 years ago, # |   +16
 » 6 years ago, # | ← Rev. 4 →   +34 I just wanted to leave this here: 7878473In case you're too lazy to open, here is the whole accepted code to C in Python (authored by ZhouYuChen) m = int(input()) x,t=10**100-1,m-100*45*10**99%m print(t,t+x) I have to say that I'm impressed :P
•  » » 6 years ago, # ^ |   0 A really neat/impressive solution!!What is the logic behind the solution?
•  » » » 6 years ago, # ^ |   +9 Let S(l, r) be the sum of digits of numbers form interval [l, r]. Take big k and see that S(1, 10k) = S(2, 10k + 1) - 1 = S(3, 10k + 2) - 2 = ...
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 Here we have with x=10^100 — 1 and t=m-(450*10^100)%m = m-r , where r
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +9 You are taking a hard way to understand this problem. I used the same idea and I think I can explain more clearly.There are 4 things to observe:1) S(1,10^k) = 45 * k * 10^(k-1) + 1You can try to convince yourself doing some mathematical proof or just run a script that calculates in a brute force fashion when k is small.2) S(1,10^k) = S(2,10^k)-1 = S(n+1,10^k+n)-nThis is the trickiest part! In the first case, l = 1 and r = 10^k. What happens if we increase them both? l = 2 and r = 10^k+1. In this case, we "removed" one element whose function value equals to 1 and "added" another one whose value is 2 (10^k+1 has two 1's and a lot of 0). You can observe (by induction) that the same holds for any value we add to both l and r. Therefore, this formula I wrote here is correct3) S(1,10^k) % M = x if and only if S(M-x+1,10^k+M-x) % M = 0Well, if you add M-x to both boundaries of S(1,10^k), you will have S(1,10^k) = S(M-x+1,M-x10^k) + x — M, according to property (2). Then you take modulo M and you will have S(M-x+1,M-x10^k) % M = [ S(1,10^k) + M — x ] % M = [ x + M — x ] % M.4) S(1,10^17) > 7 * 10^18Finally, as a is at most 10^18, you have to find a power of 10 that guarantees a sum that is greater than that value. I wrote a simple script in Python that calculated S(1,10^k), according to formula (1), for some k and I found that k = 17 was enough.If you have any further questions, you can take a look at my last submission for this code or write a message.Regards
 » 6 years ago, # |   0 Can someone explain the greedy approach to Div.2 D / Div. 1 B Two Sets?
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +12 This round taught me a lesson and warned me about my deficiency in coding details. Besides I eventually understood that you may never think about getting more rating in Chinese Round. But actually it may not be the reason for not participating the contest, for the main purpose that we compete in CF isn't the for the rating. Even so, there will be a long time for me to regain my confident and to participate another round especially the Chinese Round.
 » 6 years ago, # |   0 Can anybody explain what is the flaw in my approach Solution ?
•  » » 6 years ago, # ^ |   0 5 14 12 5 6 7 3 9 
 » 6 years ago, # |   0 Thank you for the tasks, I really enjoy the round.C Div 2 is very simple and beautiful. I wish I could find the "odd part" of solution during the round :)
 » 13 months ago, # | ← Rev. 2 →   0 Why this test case#27: 3 1 2 2 2 3 Returns: Oh, my keyboard!Not "I become the guy." ??
 » 10 months ago, # |   0 Can any one tell how to approach problems in competition so that it takes less time complexity and how to approach math problem fastly.And what's the time complexity of program if i write n^2 solution to the problem in test case loop.
•  » » 10 months ago, # ^ |   0 There are no shortcut, you know what to do.
•  » » » 10 months ago, # ^ |   0 What do u think about bold line .And what's the time complexity of program if i write n^2 solution to the problem in test case loop.
•  » » » » 10 months ago, # ^ |   0 O(t * n ^ 2)
•  » » » » » 10 months ago, # ^ |   0 But i think loop for inputing data complexity doesn't count?Is this correct.
•  » » » » » » 10 months ago, # ^ |   0 It does. Your Input/Output should be as fast as possible.