### M.Mahdi's blog

By M.Mahdi, 6 years ago,

Hi!

We're glad to invite you all to participate in Codeforces Round #360(Div. 1 and Div. 2) which will take place on Wednesday, 29 June, 20:05 Moscow time. Check it in your timezone!

The problems are designed by Man (Parsa Abdollahi) and me. It's our first Codeforces round and we hope you enjoy competing it as much as we enjoyed preparing it! (^◡^)

Our special thank goes to JeBeK (Peyman Jabbarzade) who helped us a lot in preparing and testing the round. Many thanks to GlebsHP (Gleb Evstropov) for his help in preparing the contest, and MikeMirzayanov (Mike Mirzayanov) for great platforms Polygon and Codeforces. We also want to thank Zlobober (Max Akhmedov) for testing our round.

We wish (and expect!) you all many Accepted solutions! ( ﾟ▽ﾟ)/

UPD: Problems are going to be about Pari and Arya.

UPD2 Congratulations to the winners!

Div. 1:

Div. 2:

Editorial + some challenges will be published soon.

• +658

 » 6 years ago, # |   +70 Very good time ! Thanks Mr.Shokri
•  » » 6 years ago, # ^ |   +26 Yeah , same for us. :)
•  » » 6 years ago, # ^ |   +130 Very terrible time! It is 01:05 in china.If my mom find the light in my room at that time, she must kill me! Awfully!
•  » » » 6 years ago, # ^ |   +62 Then try to win the round and you'll have an excuse! :)
•  » » » 6 years ago, # ^ |   0 Same in China T_T
•  » » » » 6 years ago, # ^ |   +12 Actually, that was China too. :|
•  » » » » » 6 years ago, # ^ |   +16 I think he might have meant, "It's the same for me, I'm in China as well."
 » 6 years ago, # |   +114 I hope both tourist and Petr will participate. And let the battle begin!
•  » » 6 years ago, # ^ |   +23 You should also hope both JIBANCANYANG and MiracleFaFa will participate.
•  » » » 6 years ago, # ^ |   +81 But you can't compete in the same division right?
•  » » » » » 6 years ago, # ^ |   0 u just got completely off the hook!
•  » » » » 6 years ago, # ^ |   +14 R E K T
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +26 Lucky MiracleFaFa... #:-s
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +26 be glad. MiracleFaFa will participate
•  » » 6 years ago, # ^ |   +14 Petr didn't participate but tourist is currently 2nd and last time he was second he had a -48 rating change. Petr still has a chance :)
•  » » 6 years ago, # ^ |   +8 Come on, now it becomes even more thrilling!
 » 6 years ago, # |   +7 That is a good time Good luck guys
•  » » 6 years ago, # ^ |   -36 That is a good time Good luck gays
•  » » » 6 years ago, # ^ |   0 Good luck guys That is good time
•  » » 6 years ago, # ^ |   +13 i hope to get into the same room to take my revenge and hack you as you hack me last contest
•  » » » 6 years ago, # ^ |   +8 It's a good thing to hacked :3
•  » » » » 6 years ago, # ^ |   +5 Unlucky me , didn't get in the same room maybe i'll take my Great Revenge later ,,,, time pass and revenge grow up
•  » » » 6 years ago, # ^ |   +6 Better to get hacked than to get system test failed.
•  » » » » 6 years ago, # ^ |   +3 In case you have not locked. Otherwise, you feel bad due to locking in case of hack.
•  » » » 6 years ago, # ^ |   +4 You should thanks hacker because your solution is Wrong and you can fix before contest end :)) :))
 » 6 years ago, # |   +56 Whoa, it starts at 2:00 AM and ends at 4:00 AM... I'll have to go to bed early in the evening and wake up then.And I couldn't but add some emojis. (๑>ᴗ<๑)
•  » » 6 years ago, # ^ |   -29 It is really sorry, and I guess you are Indian from your time.
•  » » » 6 years ago, # ^ |   +5 No, she is a Korean I believe.
•  » » » » 6 years ago, # ^ |   +2 Is there any reason to believe this person is a 'she'?
•  » » » » » 6 years ago, # ^ |   +3 It just doesn't feel right if she is a boy based on her profile picture and her typing style.
•  » » » » » » 6 years ago, # ^ |   0 Hmm... well I wouldn't hold such prejudice. Cause well...I'm pretty sure your wrong on the gender thing.
•  » » » » » » » 6 years ago, # ^ |   0 As a matter of fact I am a girl. Why do you think I am not a girl?
•  » » » » » » » » 6 years ago, # ^ |   0 I don't believe you're not a girl. Nor have I expressed that belief. I myself am gender fluid, I literally can't make gender distinctions.Okay, I was being vague on purpose. I happen to know that person. You may observe we go to the same school...
•  » » » » » » » » » 6 years ago, # ^ |   0 I see. I misunderstood your words because I am still learning English...
•  » » » » » » » » 6 years ago, # ^ |   +5 Why do you not participate in contests?
•  » » » » » » » » » 6 years ago, # ^ |   0 Because I sleep early and codeforces round are always so late in the midnight.
•  » » » » » » 6 years ago, # ^ |   +28 Wait how can you tell someone gender by typing style.
•  » » » » » » » 6 years ago, # ^ |   0 Because he used cute emojis and boys I met never use emojis... Maybe I should meet more people.
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 No offence, but you just said " he used cute emojis" are you sure that person is a girl.Arguing with a girl makes me sad:(.Between, you don't need to meet more people I need to meet more girls :P
•  » » » 6 years ago, # ^ |   +23 The time difference between this round and the previous one is only half hour, I don't think half an hour is a big deal!!!
 » 6 years ago, # |   +3 But it is really quite too late for me..
 » 6 years ago, # |   -12 excited for the round
•  » » 6 years ago, # ^ |   +184 What a bold statement
•  » » » 6 years ago, # ^ |   +86 What a bald guy
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 His Handle name written in Arabic and mean "The Lengend" in English
•  » » » 6 years ago, # ^ |   -33 What a faggot
•  » » 6 years ago, # ^ |   +98
 » 6 years ago, # |   +79 So it's 2π in radians :) :D :v
 » 6 years ago, # |   +15 11:05 pm to 01:05 am(Bangladesh) then wait for system testing.... then wait for rating.......DAMN!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 After That Bangladeshi people have "sehri" and Sleep :)
•  » » » 6 years ago, # ^ |   +25 I think the time is perfect for Bangladesh people this time..."tarabi" > diner > contest > wait for system testing > ("sehri" + wait for rating ) > go to sleep :)
 » 6 years ago, # |   +5 whoa, I can sleep longer =))If CF contest starts at usual time, I just have 2 hours to sleep; but today I can sleep in ~3 hours (maybe)Although the contest starts a half an hour later, I feel very comfortable and excited =))Hope the contest goes well =))*p/s: sorry for bad English =))
 » 6 years ago, # |   +18 I have Linux embedded system final tomorrow, but nothing stops me from participating this round :>
 » 6 years ago, # |   +14 pari?!
•  » » 6 years ago, # ^ |   +19 napari ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +52 Pari is a Hindi word for 'fairy'/'angel' in English.
•  » » » 6 years ago, # ^ |   +2 I think it means an angel and not a fairy .
•  » » » » 6 years ago, # ^ |   +12 angel is called farishta
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +46 It's a Persian word! More details (Press Ctrl+F and search Pari) / More Details 2
•  » » » » 6 years ago, # ^ |   +24 Exactly, India was once part of Persian Empire and thus origin of a lot of Indian words is Iran, not India.
•  » » » » » 6 years ago, # ^ |   +8 india became india after 1947, earlier it was(at the time of mughals and before) just indus valley civilization!
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 India has many different language derived from many different language branches. Using the term "Indian words" is like using the term "European words". It doesn't make sense. Most of the Indian languages were developed before the Muslim conquest of India so has very little to do with Muslim/Mughal empires.The only language influenced by Muslim/Mughal rulers of India is Urdu which is spoken by Muslims across India. Some of the Indian languages like Sanskrit and Hindi might have similarities with Persian language because they were derived from a single source. Refer: https://en.wikipedia.org/wiki/Proto-Indo-European_language.Though I am not going to debate on exact origin of word Pari, I would definitely disagree with your sweeping statement that "origin of lot of Indian words is Iran". It's complete BS.
 » 6 years ago, # |   -16 plz tell me the name of the BOOK or link of VIDEO tutorials from which i can learn PYTHON from very BASICS.I know C .
•  » » 6 years ago, # ^ | ← Rev. 2 →   +19 I started to learn from this link. I really recommend this. This link is the best resource that you'll ever get.
•  » » » 6 years ago, # ^ |   0 thanks
 » 6 years ago, # |   -68 I have a serious mission to deliver sacrifice to the One and the Only Almighty Chin-Chin(Peace be upon Him) which is chromosomes. If I can't please the One and the Only Almighty Chin-Chin(Peace be upon Him) with these sacrifices, He'll wipe out the entire realms. So please, I need help from all of you to generate as much of chromosomes as you can! Each time there's submitted solution which passed system test, a small amount of chromosomes will be generated.
 » 6 years ago, # | ← Rev. 2 →   +3 Hello, I am a new user here. I was wondering whether editorials are released for every contest and where do I find them?
•  » » 6 years ago, # ^ |   +9 Go to contest page(problemlist), after that find "Tutorial" in the bottom of the right panel, next to "Announcement".
•  » » » 6 years ago, # ^ |   +3 Thank You
 » 6 years ago, # |   +208
•  » » 6 years ago, # ^ |   +71 A girl is Arya Stark of Winterfell and is going home.
•  » » 6 years ago, # ^ |   +3 Pari, she calls herself.
•  » » 6 years ago, # ^ |   -22 : |||||| People never want to stop spoiling ...
•  » » » 6 years ago, # ^ |   +14 People never want to stop not watching GoT on time and complain about the spoilers.
•  » » 6 years ago, # ^ |   +20 Actually Arya meant in this statements is a Persian boy, not Arya Stark (But it'd be great, right?).
 » 6 years ago, # |   0 SUPER COINCIDENCE: We have national team trainings currently going on and at every break we play tank trouble game just like Arya :D
 » 6 years ago, # |   +82 Pari must be a fake account of Arya.
 » 6 years ago, # |   0 Plus for Pari and Arya!)
 » 6 years ago, # |   -16 Huh there is an important exam day after tomorrow can't participate :'(.
 » 6 years ago, # |   -17 In fine :)
 » 6 years ago, # |   +38 Actually, trying to get AC with suboptimal solutions is a good strategy quite often — for example vs .
•  » » 6 years ago, # ^ | ← Rev. 2 →   +34 I'm pretty sure by unoptimal solutions he means "tofs" (thats what we call it in farsi) it means spits, things that aren't supposed to work but take advantage of the tests, like Submitting a solution which is n ^ 2 but has a lot of breaks or a wrong solution which passes because there were no tests against it
 » 6 years ago, # |   0 if the girl has a name a man can bring back her eyes - the girl has no name.
•  » » 6 years ago, # ^ |   +21 it looks like someone banged your head on keyboard while registration ,no offence intended :)
 » 6 years ago, # |   0 Im looks like a cow.
 » 6 years ago, # |   +56 Ac is an Ac, no matter if it's optimal or not
•  » » 6 years ago, # ^ |   +16 of course but trying to get AC with non-optimal solutions isn't so smart
•  » » » 6 years ago, # ^ |   +18 I thought so, but then I saw people getting ac with brute force solution in this gym problem Polycarp and Palindromes in a contest where I couldn't come up with an optimal solution...
•  » » » » 6 years ago, # ^ |   +9 you're right , that's weird
•  » » 6 years ago, # ^ |   +33 hacks are coming and they will be here soon
•  » » » 6 years ago, # ^ |   +11 So it's gonna be your day today :D
•  » » » » 6 years ago, # ^ |   +19 in div2 rounds I hack others , but in div1 I'm the one who will be hacked hahaha
•  » » » » » 6 years ago, # ^ |   +32 loool the hunter becomes the prey :3 Good luck up there :D
•  » » » » » » 6 years ago, # ^ |   +14 thank you Good luck down there :D
•  » » » » » » 6 years ago, # ^ |   0 down there , here I come
 » 6 years ago, # |   0 It's holiday here \o/!!..hope weird problems haha
 » 6 years ago, # | ← Rev. 2 →   +19 tourist has been already registered , waiting to see Petr too in the contest.
•  » » 6 years ago, # ^ |   +17 when I was div2 few days ago , I was just like you waiting for them to register and see what they can solve , but now I'm not waiting for them at all . just wishing to stay pink as long as I can hahaha
•  » » » 6 years ago, # ^ |   +8 I think you're purple not pink :D
•  » » » » 6 years ago, # ^ |   0 maybe :p
•  » » » 6 years ago, # ^ |   +3 Blue is my favorite , nothing else
•  » » 6 years ago, # ^ |   +9 tourist 1st on CodeForces , peter 1st on TopCoder
 » 6 years ago, # |   +8 How many problems and score distributions?
 » 6 years ago, # |   -46 Arya be like...Today she will slay us with the statements!
 » 6 years ago, # |   -9 The name of the problme E in div 2 should be "SUCH THAT". :p :p
 » 6 years ago, # | ← Rev. 2 →   -16 [Temporary Deleted]
•  » » 6 years ago, # ^ |   +2 But Brock Lesnar (MiracleFaFa) came from nowhere
 » 6 years ago, # |   +32 Good Fight Between tourist & MiracleFaFa :)
 » 6 years ago, # |   +8 How to solve D?
•  » » 6 years ago, # ^ |   0 If you know value of , then you can know value of . Infact, it will be same.Proof is very simple. . You know value of t. Write x = k * (a * b * c) + t, where k is some integer. Now, you can see that$x \, \% \, a = t$x \, \% \, b = t\$x \, \% \, c = t
•  » » » 6 years ago, # ^ | ← Rev. 5 →   0 You said that if x = k * (a * b * c) + t then . This is not true.However, it is true that
•  » » » » 6 years ago, # ^ |   0 will be to be accurate.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 I have used this approach: (c1*c2*c3___*cn + 1) and 1 will give same modulo (equal to 1)on dividing with c1,c2,c3___cn. Now check whether (c1*c2*c3___*cn + 1) and 1 give same remainder on diving with k. If yes ,print yes else print No. EDIT:It will fail system test as it is WA on: 2 4 2 8
•  » » 6 years ago, # ^ |   +21 You need to compute LCM of all numbers and check that it is divisible by K. To avoid overflow after each LCM operation you can do GCD with K. Then the final number should be equal to K.
•  » » » 6 years ago, # ^ |   0 How to prove such solution?
•  » » » » 6 years ago, # ^ |   +4 Two numbers x and y have the same remainder modulo c[i]'s if and only if abs(x-y) = lcm(c[1], c[2], ... c[n])Now if x mod k and y mod k are not the same, then there will always be ambiguity for Arya. x mod k and y mod k will be the same iff lcm(c[1], c[2], ... c[n]) % k is 0 since the differ by this amount (or a multiple of this amount)
•  » » » » » 6 years ago, # ^ |   0 from where i can learn those type of theory?
•  » » » » » » 6 years ago, # ^ |   +3 From the CF comments section after a failed attempt to solve a problem :P
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 If LCM of c1,c2..cn is not divisible by K, then (x+ m*LCM) (m= any +ve integer), would give different remainder for K, but same for c1,c2..cn as m is increased. Hence, not possible to uniquely determine remainder with K
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +18 Here is another view on the problem and explanation.Any set of distinct numbers C (e.g. c = {3, 4, 6} as below) "generates" unique remainder sets for increasing positive numbers X with Period = LCM(c1, c2, .. cn). Those unique remainder-sets allow to uniquely distinguish remainders x mod k. E.g. remainders row "2 1 5" always correspond to (x mod k) == 5, or "1 2 4" to (x mod k) == 10. So to have things unique CycleLength = LCM(C) needs to be "syncronized" with K, more presicely it needed CycleLength % K == 0.Out of that two solutions come: Find LCM and check if it is divisible by K. If true "Yes", otherwise "No". Solution #1 Factorize K to prime powers. E.g. factorize K=108 to 4 * 27, or K=12 to 3 * 4. If EACH of that prime powers divides any number from C-set — the answer is "Yes", otherwise "No". In fact it has the same meaning as in "1": if each prime power from K can be found in some subset of C numbers then => (c1*c2*c3*..cn) % K == 0, which leads to LCM(c1,c2,c3..cn) % K == 0. Solution #2 k = 12, c : {3, 4, 6} x = 01, rems: 1 1 1 , i mod k = 1 x = 02, rems: 2 2 2 , i mod k = 2 x = 03, rems: 0 3 3 , i mod k = 3 x = 04, rems: 1 0 4 , i mod k = 4 x = 05, rems: 2 1 5 , i mod k = 5 x = 06, rems: 0 2 0 , i mod k = 6 x = 07, rems: 1 3 1 , i mod k = 7 x = 08, rems: 2 0 2 , i mod k = 8 x = 09, rems: 0 1 3 , i mod k = 9 x = 10, rems: 1 2 4 , i mod k = 10 x = 11, rems: 2 3 5 , i mod k = 11 !!! Cycle end. x = 12, rems: 0 0 0 , i mod k = 0 !!! New cycle iteration. x = 13, rems: 1 1 1 , i mod k = 1 ... x = 22, rems: 1 2 4 , i mod k = 10 x = 23, rems: 2 3 5 , i mod k = 11 x = 24, rems: 0 0 0 , i mod k = 0 
•  » » » » » 6 years ago, # ^ |   0 Only this explanation made sense to me. Nice one!
•  » » » 6 years ago, # ^ |   0 LOL. I have checked if K is divisible by LCM(a, a + n) ._.
•  » » » 6 years ago, # ^ |   0 "To avoid overflow after each LCM operation you can do GCD with K" How can we prove that after taking GCD with k answer will not be affected.
•  » » » » 6 years ago, # ^ |   0 We are interested only in divizors of K. Other numbers give no information about X mod K (by Chinese Remainder Theorem). Therefore with GCD we will not interesting divizors.
•  » » 6 years ago, # ^ |   0 Check if k is divisible by (LCM of all c[i]).
•  » » » 6 years ago, # ^ |   +10 I think you mean't the other way around.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 lem1: if you have reminder of x to two numbers p&q that gcd(p,q)=1 you can understand reminder of x to pq.lem2: if you know reminder of x to ba so you know reminder of x to a.so if k = p1^a1 * p2^a2 * ... you have to check that all p1^a1 & p2^a2 & .. are in all c's or not.i forgot to check ai s & i get wrong answer :'(
• »
»
6 years ago, # ^ |
Rev. 5   +16

Let's say we have input:
n = 6 k = 7
c1 = 1 c2 = 2 c3 = 3 c4 = 4 c5 = 5 c6 = 6

Now we can create the table of remainders R[ci][xj]. Each cell contains the value x mod c:

ci \ xj 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 1 0 1 0 1 0 1 0 1 0 1 0
3 1 2 0 1 2 0 1 2 0 1 2 0 1 2
4 1 2 3 0 1 2 3 0 1 2 3 0 1 2
5 1 2 3 4 0 1 2 3 4 0 1 2 3 4
6 1 2 3 4 5 0 1 2 3 4 5 0 1 2
7 1 2 3 4 5 6 0 1 2 3 4 5 6 0

Now let's look at the 1'st column (from top to bottom):

ci 1 2 3 4 5 6 7
0 1 1 1 1 1 1

We can think that the vector  = (0, 1, 1, 1, 1, 1) corresponds to 1 mod 7 = 1.

Now let's look at the 2'nd column (again, from top to bottom):

ci 1 2 3 4 5 6 7
0 0 2 2 2 2 2

This column can also be represented as a vector  = (0, 0, 2, 2, 2, 2) corresponding to 2 mod 7 = 2.

Each column is a vector representation of the corresponding value x.

Depending on the value of x, we get different columns of remainders. If it is possible to form a function , then the answer is "Yes" (we can determine the value x mod 7 by using only remainders x mod ci). If you cannot form a function (i.e. the same input vector can lead to different values:  =  and f( )  ≠  f( ) ), then we cannot properly encode a single remainder x mod 7 with a vector of remainders of ci. In that case, remainder x mod 7 has more capacity to store information about x, then the capacity of the whole set of ci values.

•  » » » 6 years ago, # ^ |   0 Cool table
 » 6 years ago, # |   0 Who else got Div2 C: Wrong answer on case 15?
•  » » 6 years ago, # ^ |   +21 Me, because I forgot that the graph may have more than 1 connected component.
•  » » » 6 years ago, # ^ |   +1 I did take care of that. Or may be I thought I did. Let's see.
•  » » » 6 years ago, # ^ |   0 I took care of more than one connected components but my solution gave WA for pretest 11 18806227 . I have no idea why?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I got too many TLE on testcase 15 and it turned out to be I was using global "i" in bfs function. ;((
•  » » » 6 years ago, # ^ |   0 Can you explain in detail how did you get a TLE and not WA?
•  » » 6 years ago, # ^ |   0 connected components!
•  » » » 6 years ago, # ^ |   +3 Also, even if it was given that there is only one connected components formed by the edges, another issue might have been using 1 as a root for BFS. It might be the case that 1 is actually disconnected.
•  » » » » 6 years ago, # ^ |   0 Absolutely right.
•  » » » » 6 years ago, # ^ |   0 Actually, if vertex 1 is disconnected, then it is also a connected component with only one vertex.
•  » » » » » 6 years ago, # ^ |   0 "one connected components formed by the edges,"
 » 6 years ago, # |   0 dat feeling when u finished div2C solution with 40 seconds on the clock, submit, but forgot you used zero-based indexing... :(
 » 6 years ago, # |   0 Where's the editorial??
 » 6 years ago, # |   +225 After solving ABC I checked whether I didn't register for Div2 contest ._.
•  » » 6 years ago, # ^ |   +5 How to solve C easily?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +24 Note that picking a good subset (k; x) is like picking two subsets — one with sum x, the other with k-x. That leads to an obvious O(N * K^2) dp solution.
•  » » » 6 years ago, # ^ |   +22 I hope this will be descriptive enough (dp are bitsets): dp[0][0][0] = 1; RE (i, n) { int a; cin>>a; FOR (prv, 0, k) { dp[i][prv] |= dp[i - 1][prv]; if (prv + a <= k) { dp[i][prv + a] |= dp[i - 1][prv]; dp[i][prv + a] |= (dp[i - 1][prv] << a); } } } 
•  » » » » 6 years ago, # ^ |   0 Will solution with bool array get TLE?
•  » » » » » 6 years ago, # ^ |   +11 No. 500^3 is still pretty fast (my code took 15ms xd). I chose bitsets, because they were pretty handy here.
•  » » » » » » 6 years ago, # ^ |   0 I recieved TLE on test 19 using a O(N*K^2) solution. :-(
•  » » » » 6 years ago, # ^ |   -21 is it sprase table?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Maintain an array of sets S[i][j] = numbers you can make if you get a subset of c[1..i] which has sum j (bitset recommended). Consider the cases:i) Your subset doesn't contain c[i]ii) Your subset contains c[i], but you don't use it (to make sum j)iii) Your subset contains c[i], and you use itBitset can help you union these sets quickly. It is obvious that you just have to maintain last 2 rows of array S, so the space complexity is O(K^2)
 » 6 years ago, # |   0 It's a very good contest! Thank you! My favorite task is c! And can anybody explain d?
 » 6 years ago, # |   +23 User fakee clearly got some sweet revenge against Barichek: On another note: Thanks to the authors for a nice contest I enjoyed solving the problems a lot. I hope you will make more contests!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 And yashkumar18 took revenge from i_need_job for just trying to hack his solution :P(link)Edit : I still don't know how to upload pictures in comments :/
 » 6 years ago, # |   0 I got TLE in TC 19, div2E...
 » 6 years ago, # | ← Rev. 2 →   +14 A lot of solutions will fail in Div2D including mine. I hacked all the solutions (there were only 2 :p ) in my room with this case. 2 8 2 4 Output should be: No 
•  » » 6 years ago, # ^ |   +3 I'm sorry, but why?
•  » » » 6 years ago, # ^ |   +8 X=1 and X=5 give the same remainder when divided by 2 or 4 but they give different remainders when divided by 8.
•  » » » » 6 years ago, # ^ |   0 Thanks!
•  » » » 6 years ago, # ^ |   0 For example, you can't tell if its 5 mod 8 or 1 mod 8
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 For X = 1, 1%2 = 1, 1%4 = 1For X = 5, 5%2 = 1, 5%4 = 1So, you can't really uniquely identify X % 8.
•  » » » 6 years ago, # ^ |   0 Check 1 and 5, they have same reminders mod 2 and mod 4.
 » 6 years ago, # |   +18 I don't think div1 C should be div1 C.
•  » » 6 years ago, # ^ |   +8 Yes, you are right.
 » 6 years ago, # |   +16 It took me whole contest to solve Div2 C,D,E. It took tourist and TooSimpIe just 12 minutes to do that!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +15 There is a reason why they are Red.
 » 6 years ago, # |   +49 Is O(qm) intended complexity for div1-D?
•  » » 6 years ago, # ^ |   +10 If it was, then the task was all about optimization and luck. I got TLE in pretest 15 with O(qm) but kllp passed pretests in 2600ms with the same idea and time complexity.
•  » » 6 years ago, # ^ |   0 my (NlogN + M * (DSU)) per query passes in 2 seconds.
•  » » 6 years ago, # ^ |   0 Our solution is .
•  » » 6 years ago, # ^ |   0 I got O(q·(m + n·logn)) in 967ms: 18804248
•  » » 6 years ago, # ^ |   +10 I've got O(mq3 / 4α(n))
 » 6 years ago, # |   0 Can anyone please check my solution for Div2C 18806227 ? Thank you.
•  » » 6 years ago, # ^ |   -8 Which testcase did you fail?
•  » » » 6 years ago, # ^ |   0 11th. I took care of connected components as well :(
•  » » 6 years ago, # ^ |   +5 Try to add g[v].push_back( u ); your code.
•  » » » 6 years ago, # ^ |   0 Shit! That was easy . Thank you
 » 6 years ago, # |   +58 I'm curious if the O(qmα (m)) is intended solution in div1D. If so — why limitations are so strange (n, m ≤ 105 will be ok). If no — seriously?!And Oscar goes to foreach .. break in div1E. Spend about 20 minutes trying to solve problem without break. With break problem becames... div1C.
•  » » 6 years ago, # ^ |   +3 FYI, I have in D.How to solve it with that break? At the end, I came up with the following solution but don't know if it's correct. Find SCC's and for each SCC from which there is no edges find the smallest cycle. The answer is .
•  » » » 6 years ago, # ^ |   0 I think it is correct (I hope so :) )
•  » » » » 6 years ago, # ^ |   0 It's funny that for much time I tried to solve a version without break too. Still, it's our fault, not organizers. And I'd say it's at least div1D difficulty, not div1C.
•  » » » » » 6 years ago, # ^ |   +8 Yeah, but they could write much more readable code. It looks like it was intended :)
•  » » » » » 6 years ago, # ^ |   +7 I wouldn't say it's like D, I don't solve D in 20mins like it solved E)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 I think using segment tree to store the useful edges in its range can solve div1 pD in , which is asymptotically faster but...:P
•  » » 6 years ago, # ^ |   +23 OMG, that break is not within if --___--?? Where is the hidden camera??
•  » » 6 years ago, # ^ |   0 n, m ≤ 10^5 still holds when n, m ≤ 10^3.
•  » » » 6 years ago, # ^ |   0 There was no m ≤ 1000 condition.
•  » » » 6 years ago, # ^ |   0 but m is up to 5·105
•  » » » 6 years ago, # ^ |   +13 = = I meant the pretests are probably weak that it looks like n, m <= 10^3.
 » 6 years ago, # |   +10 Hints for Div1 D?
•  » » 6 years ago, # ^ |   -80 suppose k = 2^3*3^7*5^3, then you just need modulo wrt to 2^3,3^7,5^3 to find modulo wrt k. Note that if you have modulo 2^2 and not 2^3, we will failTo find modulo wrt to 2^3, just check if on of the numbers is divisible by 2^3.
•  » » 6 years ago, # ^ |   +5 sort edges in descending order . You need to find the first index such that edges taken till that index form a non bipartite graph .
 » 6 years ago, # |   +3 Terrible grammar. Someone send the statements to jacksfilm for YGS
 » 6 years ago, # | ← Rev. 2 →   0 After reading Problem Div2D -> Do i know english at all?
 » 6 years ago, # |   0 This is what I tried for Div 2 C. Can someone tell me the fault in my algorithm. So I maintain two hash maps for the two Vertex Covers. Initially I pick up the first edge, and put each of the vertices in this edge in each hash map. So if edge is (u, v), then A hash map will contain u and B hash map will contain v. I then have 2 copies of the edges of the graph, namely s1 and s2. For s1, I remove all the edges incident on u. For s2, I remove all the edges incident on v.Now I call a function that processes my logic. So basically I check all the edges from s1, Let the current edge at any time be (u1, v1). So if u1 is present in hashmap B, and v1 is also present in hashmap B, then its not possible to split and I print -1. However if one of them is present in hashmap B, for example say u1 is present in hashmap B, I add v1 to hashmap A, and remove all the edges incident on v1 from s1, and continue the same procedure for other edges in the set. I am unsure of the case where neither of them is present in hashmap B. In that case I do not know which vertex I should add in hashmap A.Finally, after removing all the edges from s1, and no problem was encountered. I proceed to call the same function for s2, but now interchange the roles of hashmap A and hashmap B. If after doing the same process, if s2 set becomes empty, and there was no problem. I print out the keys of the hashmap in sorted order. So my question relates to that step when neither of the vertices in a given edge are present in the other hashmap. In that case which, edge should I consider adding. I thought of a solution to add the vertex with higher degree, but I guess it won't be correct. Any help would be appreciated. Thanks!
•  » » 6 years ago, # ^ |   +8 Consider a square-shaped graph, and pick any edge as the first edge. If when processing s1, the edge opposite to this edge is checked, since this edge is also in s2, the function fails. However a square shaped graph has an answer in the form of opposite vertexes (A: (1, 3), B: (2, 4)). Is this what you meant?
 » 6 years ago, # | ← Rev. 2 →   +2 Last time tourist got on second place at CROC he got -48 in rating. Toady he is on second place again and 30 minus points is enough for getting petr #1 at codeforces. (let's just wait for the rating changes :D)
 » 6 years ago, # | ← Rev. 2 →   0 In Div1-C Problem. What i and j are here ? Are they 2 subset sum ? Errichto Solution 18788820
•  » » 6 years ago, # ^ |   0 Yes, two subset sums. Consider dividing elements into three parts with sums i, j and s - i - j where s denotes the sum of elements so far.
•  » » » 6 years ago, # ^ |   0 Thanks.
 » 6 years ago, # |   0 What a round. It felt like i was giving an English Language exam -_- Wasted 90+ minutes to understand the problem D (Div 2) and still i didn't get what it actually asked -_-
 » 6 years ago, # |   0 How funny!!! What were the system tests for Div2 B? My wrong code got AC! :pHere
•  » » 6 years ago, # ^ |   +8 Why? Seems alright to me.
•  » » » 6 years ago, # ^ |   0 How can it seem alright? Just check with some inputs. For example 20
•  » » » » 6 years ago, # ^ |   0
•  » » » » » 6 years ago, # ^ |   0 Oh great! The line s[0]=s[0]-- reduces s[0] in my compiler but here it doesn't :/ Why is that?
•  » » » » » » 6 years ago, # ^ |   0 Just you use postincrement."s[0]=s[0]--;" is equal: char t = s[0]; --s[0]; s[0] = t;
 » 6 years ago, # |   -77 I am quite surprised by JoeyWheeler's performance.
•  » » 6 years ago, # ^ |   +219 Thanks mate >_>
•  » » 6 years ago, # ^ |   +73 What is so surprising? He solved 3 easy problems with a little mistake in one and got stuck on harder problems (D's acceptance rate is inflated because of passing bruteforces). Happens to me all the time and remember about tourist's 168th place once.
 » 6 years ago, # |   +1 It seems that Div2D simple solutions are getting AC just taking lcm. I believe that it wouldn't be difficult to construct a counterexample using large primes and the product will overflow. Can someone tell me if I'm right or it can be proved that it will fit in unsigned long long?
•  » » 6 years ago, # ^ |   +5 Even if you calculate lcm as a*b/gcd(a,b), the a*b part cannot exceed 1000000*1000000, which fits under long long int range.
•  » » » 6 years ago, # ^ |   0 It is just in the first operation, but after it should overflow. Anyway, in the submission I saw, the guy used some smarter approach to make it pass.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   -10 I used gcd instead of lcm so that it would never overflow. (Failed in systests because of a bug but this one works.)SubmissionEdit: sorry, just realized I had previously put the wrong submission
•  » » 6 years ago, # ^ |   +11 I tried to hack such submission, but finally noticed that the guy made a[i] = gcd(a[i], K) before. Then LCM will not overflow K.
 » 6 years ago, # |   -15 fuck cin/cout.... (problem D div 2)
 » 6 years ago, # |   +21 Today I managed to be solving three (!) problems which were not tasks prepared by organizers :). In Div1D I considered intervals of cities not intervals of roads and wasted more than hour on that. In Div1E firstly I didn't notice break. Then I noted break, but I considered version with that break within if :P. I didn't solve any of them ;).
 » 6 years ago, # |   +1 Waiting for Editorial ...............
 » 6 years ago, # | ← Rev. 2 →   0 The first idea for solving div2B was to generate first one hundred even palindroms ( yes, i know that it would get TLE ) , but when checking results i saw that the n-th palindrom is equal to n+reverse n , and solution which displays n+reversen is accepted , but i dont understand why .. why ?
•  » » 6 years ago, # ^ |   0 Start by noticing that palindromes with even number of digits are made of two equal parts. That is, if you cut them in half, both parts will be equal, but reversed.
 » 6 years ago, # |   0 For Div2, Problem C (NP Hard) — I was not able to represent the graph as an adjacency matrix (boolean) due to memory constraints (Since 1 <= V, E <= 100,000). However, I see that the accepted solutions have used an array of vectors of the same size. I am confused if the test case uses a complete graph with V equal to max-limit, won't this exceed the 256M memory limit, even if a vector is used?
•  » » 6 years ago, # ^ |   0 m<= 10^5
•  » » 6 years ago, # ^ |   0 """two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively."""
•  » » » 6 years ago, # ^ |   0 Damn it, thanks.
•  » » 6 years ago, # ^ |   0 There can't be such testcases because number of edges is also constrained.(It can't be V(V-1)/2)
 » 6 years ago, # |   +26 Div2 ==> FinishedDiv1 ==> Pending system testing:/
 » 6 years ago, # |   +164 There is no systest because you are trying to construct test aganist O(qmα (m)) in D ?)
•  » » 6 years ago, # ^ |   +44 Seems like they've failed to construct such test
•  » » 6 years ago, # ^ | ← Rev. 3 →   +70 The time complexity is at most O(q(m + n2)) instead of O(qmα(m)). Because the distance of each vertex to the root of the disjoint-union set is at most O(n).
•  » » » 6 years ago, # ^ |   0 Isn't O(q*n^2) with given constraints is ~ 10^9 instructions. I was under the impression that this will get TLE. Looks like that is not the case. How to predict whether a solution design will get TLE or not?
•  » » » » 6 years ago, # ^ |   +6 You are right, and the constant factor is not 1 (more like 3 or 4). But TL is 6 seconds.
 » 6 years ago, # | ← Rev. 2 →   -18 Before the system test: finally i will be a div1 user :DAfter the system test: good bye div1 for ever ;_;
 » 6 years ago, # |   +3 Before systests : ~600. After systest : 296.
 » 6 years ago, # |   0 get rekt but i can get much of experience，thanks authors for nice problems TT
 » 6 years ago, # | ← Rev. 3 →   -64 )
•  » » 6 years ago, # ^ |   +81 Do you even meme bro?
•  » » » 6 years ago, # ^ |   +14 No, I am doing this first time :/ All I want to have editorials to learn something new.
•  » » » » 6 years ago, # ^ |   +27 Keep trying, eventually you will find the correct meme (or realize that it doesn't exist at all).
•  » » » » 6 years ago, # ^ |   0 Meme editorials (bro)?
 » 6 years ago, # | ← Rev. 8 →   +26 TLE on 1B with cin and ios :: sync_with_stdio(false) :( Why can't authors add a proper max-test in the pretests! :/
•  » » 6 years ago, # ^ |   +11 I got TLE due to cin too -> 18790984. Got AC with scanf in 342 ms -> 18809097It sucks to get tle just due to slower I/O :(
 » 6 years ago, # | ← Rev. 2 →   0 My Code for Problem A of Div #2 today. It gives right answer when in PC (Windows, Codeblock 16.01) but problem when in CF for Input 2 2 10 00. Please help me guys.
 » 6 years ago, # |   +121 "Pari never tries to get ac with non-optimal solutions" — aren't constraints in D explicit invitation to code bruteforce ._.? Even tourist and MiracleFaFa coded bruteforces -_-. Stupid problem. Try doing some statistics on how many AC to that problem are brutes (I guess >=80%).
•  » » 6 years ago, # ^ |   +26 I'm curious why so many red guys are confident with bruteforce.They probably realized it is a Div 2 contest.
•  » » » 6 years ago, # ^ |   +31 There was two reasons why I complain:1. It is too easy for div1D2. Why n ≤ 1000, I don't use it.But the constraints are small enough for this solution to pass.
•  » » » » 6 years ago, # ^ |   -13 These may happen for everyone who is preparing a contest for the first time.
•  » » 6 years ago, # ^ |   +29 So that explains it... I found the actual solution (or something that has the same complexity at least) and it was some ugly Frankenstein union of a bunch of different algos, when I looked at the standings and thought "no way 70 people coded that :o"
 » 6 years ago, # |   +19 Fun facts:using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in Busing a O(qm alpha n) approach gets AC in DAs Swistakk says, I thought I registered for Div 2 after solving ABC.Well, I should have gone back to office and let my mother participate this round for me.
•  » » 6 years ago, # ^ |   +37 More fun facts, random_shuffle AC in div1C. 18807562
•  » » » 6 years ago, # ^ |   +24 random_shuffle has become quite an efficient problem solving tool recently!
•  » » 6 years ago, # ^ |   0 Another fun(?) fact: Around 70 div1 participants got TLE in B because of input speed.TFW you set a need-to-optimize problem's TL to 6s and a ****ing huge input one to 1s.If you ask me, yes I'm butthurt))
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 qm log(n) works in D too I now understand that my solution is qm + qnlogn. Sorry for being misleading
•  » » 6 years ago, # ^ |   +21 using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in Bn = 10^9 an O(n) solution passes and everybody loses their mindsn = 10^6 an O(n sqrt n) solution doesn't pass and everybody loses their mindsSTFU people :3no offences, just kidding, i'm a noob
 » 6 years ago, # |   0 Got wa on 25th test case for div2B.i just increased size of string to 200005 from 100005 and it got accepted.can anyone explain why?
•  » » 6 years ago, # ^ |   0 the answer can be as long as 200000 as given n will have 100000 digits... hope that helps.. :)
•  » » » 6 years ago, # ^ |   0 But i didnot put the answer in a string
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 maybe because your string b didn't have a proper '\0' null terminator in the right place. why still it gives correct output for increased array size I don't really know.
 » 6 years ago, # |   +11 Lol, so stupid idea in Div1D really passed... I wonder, what did authors expect to see when they set 6 (!!!) seconds TL.
 » 6 years ago, # |   0 can anyone tell me the problem with this submission(DIV 2C) http://codeforces.com/contest/688/submission/18808464 when i am running this code it is outputting correct answer but in submission it is giving -1 for 1st test-case itself...
 » 6 years ago, # |   -21 When you see MiracleFaFa solved Div2 E in a period of 4 mins
 » 6 years ago, # |   +22 The advanced algorithmic technique to get AC in div1D1880846618810544
•  » » 6 years ago, # ^ |   0 Any idea as to why this works/doesn't?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 The second submission has better memory locality so cache works better.
•  » » 6 years ago, # ^ |   +18 Mine are also fun:1881039218810587
 » 6 years ago, # | ← Rev. 2 →   +42 tourist is't the first !
 » 6 years ago, # |   -9 I am really surprised, my solution in B div1 is nlognTLE using cin even with ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)Used scanf and printf it got ACI never saw this happen on a site like Codeforces, I really can't believe it happened and why time limit is too strict?!!!I wish i see good explanation to what i saw today and why the author made the time limit so small !!If he made time limit 1.5 seconds as an example only intended solutions will pass too.
•  » » 6 years ago, # ^ |   0 Your solution is slower than the intended one. Cin/cout is slower than printf/scanf.
•  » » » 6 years ago, # ^ |   -11 I think gcd is log or moreso total is nlogn, only my constant factor is bigger, i know, but the same complexity, if time limit is too tight it means other languages will not get AC
•  » » 6 years ago, # ^ |   0 sieve() takes a lot of time. My method just takes gcd() and does not take sieve() method, with " ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)", and faster than your AC solution more than 100ms.
•  » » 6 years ago, # ^ |   0 My Python solution was judged TLE on pretests, then submitted a C++ version and got AC =) I tought there were multiplicative factors on execution time to equalize results...
•  » » » 6 years ago, # ^ |   0 I think that if they make some updates like special Time Limit for each lang that's will be better
•  » » » » 6 years ago, # ^ |   0 Yeah, but it's a huge amount of work =P
•  » » » » » 6 years ago, # ^ |   0 that's right
 » 6 years ago, # |   0 Still tourist is first
 » 6 years ago, # |   +20 tourist — Petr = 1 ! The game is still on :)
 » 6 years ago, # |   +14 Some time limits were definitely problematic :/ Enough people mentioned Div1B (input), but my problem was with Div1C — my O(N*K^2) solution got TLE, which I fixed easily with some microoptimizations but I didn't expect them to be needed... Was there some good reason for this time limit (e.g. a worse solution that might've passed otherwise)? If not, it's frustrating that constant factor optimizations made such a big difference in this contest (also in Div1D apparently).
•  » » 6 years ago, # ^ | ← Rev. 3 →   +10 Well after enough optimizations my O(n^4) for Div2E/Div1C got AC'd18812616Maybe they are justified about their strict time limits after all...
 » 6 years ago, # | ← Rev. 8 →   0 On Div2D/Div1B, many C++ codes which get TLE31 get AC by just adding one line of code at the beginning of main:ios_base::sync_with_stdio(false);example:Time limit should not have been only 1 second.
•  » » 6 years ago, # ^ |   +1 Luckily I read this. http://codeforces.com/blog/entry/10
 » 6 years ago, # |   0 My solutions are showinh the verdict skipped what do i do are my submissions wrong or what??
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 If more than one submission for a problem pass the pretests, the most recent one will be considered and the rest will be skipped
 » 6 years ago, # |   +50 I think it is intetesting that tourist-Petr is 1. But I don't deem it interesting that my rating is now 2899!:(
•  » » 6 years ago, # ^ |   +62 Matches your username ... I think that's pretty interesting
•  » » » 6 years ago, # ^ |   0 lol
•  » » » » 6 years ago, # ^ |   +13 The last chance to be a lgm before retiring？ lol.
•  » » » » » 6 years ago, # ^ |   +3 Possibly. It should be informed that retiring means the end of OI contests(for high school students) in China. If I fail in the contest in july(NOI 2016), I will retire and this is my last chance. And I should mention that programming contests in China are easy to fail. But whatever it is I narrowly missed this chance. :(
•  » » » » » » 6 years ago, # ^ |   +47 matthew99 is Illuminati Confirmed
•  » » » » » » » 6 years ago, # ^ |   +11 lol... really magic
•  » » » » » » 6 years ago, # ^ |   +32 Congratulations to matthew99 on winning China NOI 2016!
 » 6 years ago, # |   0 Can any body tell why this submission 18804553 is WA ? I saw some AC solutions and its the same idea .
•  » » 6 years ago, # ^ |   0 I think you are not handling multiple connected components correctly. For example, on the case "4 2 1 2 3 4" your code does not put vertices 3 or 4 in either group.
•  » » » 6 years ago, # ^ |   0 Thanks, but as it said in the statement we can keep vertex for ourself , so i can keep vertex 3 and 4 , and give vertex 1 to Pari and give vertex 2 to Arya , right ?
•  » » » » 6 years ago, # ^ |   0 You can keep a vertex to yourself . Not an entire component -_- . See the sample input , there are 4 nodes but node 4 isn't in the output !
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Thanks , I didn't read the statement well , I got AC with some little changes .
 » 6 years ago, # |   0 I am thankful that my solution got hacked. Or else would have gone back to Div 2 today :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   -16
 » 6 years ago, # |   +13 Uh ... So there is UPD3 but no UPD2 ...I think that's why we didn't see the score distributions, they skipped it (?) ... ._.
•  » » 6 years ago, # ^ |   0 Now it's fixed, editorial is out guys! :D