niyaznigmatul's blog

By niyaznigmatul, 2 years ago, translation, ,

Editorial

Hello!

Codeforces Round #467 (Div. 1) and Codeforces Round #467 (Div. 2) will take place on February, 25 at 14:35 UTC. Most of the problems are Innopolis Open Olympiad in Informatics problemset. We ask olympiad participants not to take part in Codeforces rounds and not to discuss the problems till the end of the rounds.

Problems were prepared by: niyaznigmatul, pashka, gritukan, VArtem, burakov28, BudAlNik, YakutovDmitriy, dusja.ds, GreenGrape, tourist. We thank testers: demon1999, senek_k, the_art_of_war, Qrort, ayoyia, izban и julsa.

Good luck!

UPD: The round is rescheduled to +1.5 hours to avoid collisions with other events.

• +335

 » 2 years ago, # |   +17 Hope the problem statements are as short as the announcement!! :D
 » 2 years ago, # |   +7 There are some users who regestered in div.2 round before the rating change of round 466 and now they are div.1
•  » » 2 years ago, # ^ |   -9 did they ever fix the one where the educational round let div1 participate in div2
•  » » » 2 years ago, # ^ |   0 It wasn't a bug to be fixed. It was totally intentional.
•  » » » » 2 years ago, # ^ |   0 So it's intentional that a purple user can farm rating in contest strictly for < 1900? Where did they ever say that's intentional?
•  » » » » » 2 years ago, # ^ |   0 The results of educational round was announced after div 2 contest so it was made rated for everyone who were div 2 before the educational round. Participants want to know whether it's rated or not before they participate in contest. The only fair way to ensure this was to make it rated for everyone who were div 2 before educational round. As you say you can't simply "farm" rating. I actually dropped from div 1 back to div 2 after that contest. Whoever had rating increase totally deserved it.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 official comment (http://codeforces.com/blog/entry/57819?#comment-414872)
•  » » » » » » 2 years ago, # ^ |   0 looks like I was wrong, my bad
•  » » 2 years ago, # ^ |   0 Anyone in particular you have in mind? I only see a handful of >1900 people in the div2 results and it doesn't look like the competition counted towards their rating.
 » 2 years ago, # | ← Rev. 7 →   -66 This round will be held in usual time. It's good for someone.
 » 2 years ago, # |   -68
 » 2 years ago, # |   +28 It's the first time ever I've seen a contest with 10 distinct writers :OLet's hope for a quality contest with no interference from DDoS and server issues ;)
 » 2 years ago, # |   -30 Round# 467 is a prime number while contest(div. 2) 937 is a prime number, too!
•  » » 2 years ago, # ^ |   -38 Problem A: 467 and 937 are lucky numbers, given a string count.. 
•  » » » 2 years ago, # ^ |   -48 What's happened to you people :|
 » 2 years ago, # |   -60 I have found the name tourist in the problem setter section :D
 » 2 years ago, # |   -27 10 problem setters , sir tourist is also here , i think this contest problems are too much perfect and malleable , too much excited :)
 » 2 years ago, # |   -29 Hopefully the number of problems is less than 10 considering there are 10 problem setters xD
 » 2 years ago, # |   -21 My brain singing "I want something just like this" :p
 » 2 years ago, # |   -24 How many problems are expected? There are many setters
 » 2 years ago, # | ← Rev. 2 →   +39 So is contest starting at 16:05 UTC now?Edit: I realised later I can see the time in Contests tab.
 » 2 years ago, # |   +24 Hope a round whose time is good for East Asia users!!!
 » 2 years ago, # |   +3 Please make this round visible in a "Pay attention" section (can't see it in RU version) and include it into the list of upcoming events! I found this round only accidentally.
 » 2 years ago, # |   -11 tourist as setter in Contest #2 of 2018 (Contest #1 — Hello 2018).
 » 2 years ago, # |   +106 It is not good to change the timings at the last moment as all my plans are getting disturbed.
 » 2 years ago, # |   +30 So sad it delayed.It is 12:05 UTC+8 now :( I know I'm not that good at programing,but I just want to join in the contest for fun... (Unhappy Chinese pupil)BTW,will my comment be hidden because too negative feedback?
•  » » 2 years ago, # ^ |   0 I'm sad, too. ;( And about your comment, it won't.
 » 2 years ago, # |   -99 The comment is hidden because of too negative feedback, click here to view it
 » 2 years ago, # |   +1 Why the delay...? I want to know what those "other events" are?
 » 2 years ago, # |   +5 so what about score distribution?
 » 2 years ago, # |   +118 Got up early on a Sunday morning for a contest and found it delayed like.
 » 2 years ago, # | ← Rev. 2 →   0 I can't participate in this contest because it delayed. But I have registered. So the question is: will my rating be influenced if I don't participate. If yes, what should I do?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 No. If you do not submit any code, your rating will not change. And you can also unregister your registeration.
•  » » 2 years ago, # ^ |   +18 Unregister.find yourself in the (http://codeforces.com/contestRegistrants/937),and press the "X" after it.
•  » » 2 years ago, # ^ |   0 I know how to do now. Thanks!
•  » » » 2 years ago, # ^ |   +8 An Chtholly lover! WOW!
 » 2 years ago, # |   0 Can you delay it another 10-30 minutes?
 » 2 years ago, # |   0 I know the event today.it's VK Cup 2018,not tourist's marriage.:-)
•  » » 2 years ago, # ^ |   -9 But in the Contests page, it shows that VK Cup 2018 is on Mar 10th?
•  » » » 2 years ago, # ^ |   0 switch to russian version dude
•  » » » » 2 years ago, # ^ |   -6 thanks, I get it now.
 » 2 years ago, # |   +21 Although I was very busy at work but came home earlier for the round, and see that the scheduled time is changed. For next rounds, I suggest to change date or time at least a day before the round.
 » 2 years ago, # |   +43 Events like Chelsea VS Manchester United :)
•  » » 2 years ago, # ^ |   -12 +1
•  » » 2 years ago, # ^ |   +21 original time would have been better, I would have been able to watch Man City vs Arsenal! much better than chelsea vs united
•  » » » 2 years ago, # ^ |   +7 Mike is a Chelsea or ManU fan :V
•  » » » » 2 years ago, # ^ |   0 Haha!!
 » 2 years ago, # |   0 I'm too worried about codeforces server errors during the contest. Let's that it'll not happen again.
 » 2 years ago, # |   +5 please post the new score distribution.
 » 2 years ago, # |   +4 Hate the time delaying. The new time conflict with my sleeping time
 » 2 years ago, # |   0 I hope this contest will make me green !.. I just need +75 rating to become a green coder...
•  » » 2 years ago, # ^ |   +2 yeah, Against all odds, finally you got your prize ! :)
•  » » » 2 years ago, # ^ |   0 Yess...I became a green coder now...!!!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Yes..
 » 2 years ago, # | ← Rev. 3 →   0 Hopefully it will be a cool contest.
 » 2 years ago, # | ← Rev. 5 →   +66 I hope, systesting of VK cup will be turn off during the round.UPD: So you haven't done this...
 » 2 years ago, # |   +2 I think all of you guys should stop arguing. Codeforces is a programming website, not a quarrelling website!
•  » » 2 years ago, # ^ |   +8 finally we got rid of ppppppppppppppp
 » 2 years ago, # |   +2 Came here to read funny comments but man wtf?!
 » 2 years ago, # |   -14 Is it rated?
 » 2 years ago, # |   -18 is it rated for div 2?
 » 2 years ago, # |   0 to CF Server : DON'T FREEZE.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 @I never freeze@froze
 » 2 years ago, # | ← Rev. 2 →   -50 From my school years I remember this olympiad as a trash. Seems like not much have changed. No offence.
•  » » 2 years ago, # ^ |   +23 No offence But it was offensiveBtw why?
•  » » » 2 years ago, # ^ | ← Rev. 3 →   -41 Cause it's just my opinion, and I don't wanna be rude or something. Just really don't like it.Low problems quality. When I participated, it was 4 very-very easy (like div2 A) problem with a lot of stupid coding, and one hard geometry problem. So the places were distributed by points in only one problem (on olympiad there are problems with subproblems, you get points for solving subproblems, no time/resubmit penalty). This time they are harder, but still boring/stupid.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   -26 i agree codeforce needs some subproblems for better categorizing (according to individual coding proficiances)
•  » » » » 2 years ago, # ^ |   0 Yesterday's difficulty distribution was good though :)
•  » » » » 2 years ago, # ^ |   +30 I don’t know which problemset you are talking about. Any link would be helpful.You are welcome to become one of the problemsetters, if you have "not stupid/not boring" problem ideas in your mind.
•  » » » » 2 years ago, # ^ |   +15 Don't be angry because you can't solve them
 » 2 years ago, # |   -6 Unrated Round cy >(
 » 2 years ago, # |   -14 fucking long queue!
 » 2 years ago, # | ← Rev. 2 →   0 What is this? There is 10 pages long queue. (~700 submissions only in div2)Make this round unrated >.>
 » 2 years ago, # |   0 Today's day is so good : I am performing wonderful in the contest and queue is helping me in it :)
•  » » 2 years ago, # ^ |   0 Hope it doesn't get unrated.
 » 2 years ago, # |   0 what is this? This much Queue
 » 2 years ago, # |   0 goodness me there is a 10 page+ long queue. Please fix it asap!
 » 2 years ago, # |   -6 13 page long queue ! what is this !
 » 2 years ago, # |   -6 this long queue, will it make this round unrated?
 » 2 years ago, # |   0 You know the queue is so long when you're in Div.1 and the "In queue" verdicts' region is wider than a 50-line page...
•  » » 2 years ago, # ^ |   0 70-lines to be exact.
 » 2 years ago, # |   0 Shit man! I really hope the round won't be unrated because of the long queue.
 » 2 years ago, # |   0 It's taking a very long time to process submissions...
•  » » 2 years ago, # ^ |   +2 Seems to be fixed now.
 » 2 years ago, # |   0 The judge is running too slow . so frustrating at times .. look into it
 » 2 years ago, # |   0 Tomorrow is my Exam but still i'm giving the contest to get away from the stress situation but these long queues of codeforces are giving me more headache than my syllabus did.
 » 2 years ago, # |   +2 Are DIV 2 Contests getting harder or I'm the one who is getting dumber ??
•  » » 2 years ago, # ^ |   +11 Both
•  » » 2 years ago, # ^ |   0 you are not true Rick :D
•  » » » 2 years ago, # ^ |   0 yeah, I'm just another Morty :-(
 » 2 years ago, # |   +2 What the hell is pretest 10 in C?
 » 2 years ago, # |   0 how to solve DIV2 : B?
•  » » 2 years ago, # ^ |   +9 Check if there is number from y to y-300 that is not divisible by any number from 2 to p. 300, because prime gap is at most 300 in this number range
•  » » » 2 years ago, # ^ |   0 prime gap is 300?
•  » » » » 2 years ago, # ^ |   0 Yes, maximum distance between two primes is a bit less than 300 in range from 1 to 10^9
•  » » » 2 years ago, # ^ |   0 "because prime gap is at most 300 in this number range" can you please elaborate it a little?
•  » » » » 2 years ago, # ^ |   0 You can find it on wikipedia, just search for prime gap
•  » » » » » 2 years ago, # ^ |   0 thanks mate! I have wasted my 20 mins on this:(
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 since p can also be of order 109 checking in [2, p1 / 2] [2, min(n1 / 2, p)] is enough.
•  » » » » 2 years ago, # ^ |   0 Please explain a little why we check only till sqrt(p)
•  » » » » » 2 years ago, # ^ |   0 If P has any divisors, it can be written as a*b. Now, if a is less than sqrt(P), then b must be greater than sqrt(P). Therefore, either a or b is greater than sqrt(P). So, if divisors exist, we only need to check up to sqrt(P).
•  » » » » » » 2 years ago, # ^ |   0 Thank you
•  » » » » 2 years ago, # ^ |   0 can u help me to figure out why this is wrong my submission
•  » » » » » 2 years ago, # ^ |   0 You are only checking divisibility up to mn = min(1000LL, p); but should be sqrt(y), since y could be 1E9, whereas 1000*1000 = 1E6.
•  » » » » » 2 years ago, # ^ |   0 mn = min(1000LL, p); why 1000?
•  » » » » » » 2 years ago, # ^ |   0 my bad :( got it!! thanks
•  » » » 2 years ago, # ^ |   +1 prime gap: https://en.wikipedia.org/wiki/Prime_gap
•  » » » 2 years ago, # ^ |   0 what if p is 10^8 or greater. wont it get TLE
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 You check for prime divisors of i where y-300<=i
•  » » » » » 2 years ago, # ^ |   0 i checked for all divisors of i (sqrt(n)) upto i — 500 and if yes print
•  » » 2 years ago, # ^ |   0 Then why is this solution wrong ?https://ideone.com/3YAlQZ
•  » » » 2 years ago, # ^ |   +1 case 2, 9 answer is 9
•  » » » » 2 years ago, # ^ |   0 Oooooops,
•  » » » 2 years ago, # ^ |   0 check 2 9 output should be 9
•  » » » 2 years ago, # ^ |   +1 the solution need not be prime everytime. The only condition it must satisfy is that in the range [2, p] it doesn't have any factors!
•  » » » 2 years ago, # ^ |   +1 Thanks guys. Silly bugs everywhere :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 You don't need to do calculate any prime gaps, just work backwards from y. Because you know that there won't be a huge prime gap, you are sure to find something pretty quickly. http://codeforces.com/contest/937/submission/35691076 Just be sure to leave the loop once you find it and to only check up to sqrt(y) when searching for divisors
•  » » » 2 years ago, # ^ |   0 How to calculate the time complexity of your code Intrincantation
•  » » » » 2 years ago, # ^ |   0 In the worst case, outer loop runs until we find a prime number, so when calculating the complexity you need to use prime gaps, but you don't need to actually know the exact value to implement it, just know it is relatively small. Let P(n) be the largest prime gap. Complexity will be O(P(y) * sqrt(y)). Because you are checking up to sqrt(y) to find divisors, and you are doing this at most P(y) times.
 » 2 years ago, # |   +10 How to solve Div-1 C?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +16 First turn the string into a permutation, that we want to transform into 1,2,...,n. Then, starting from n/2, start constructing the string. In a single step, do: 6789...5... --> ...6789...5 --> 5......6789 --> 98765...... This reverses the string we've built, and adds the number we wanted to add to the end of the reversed string. Use this to append small and large numbers alternatingly. It takes 3*n = 6000 operations.
•  » » 2 years ago, # ^ |   0 I had similar idea to other one.But I wanted to share my way of thinking.I could easily come up with 4*n steps for building from one corner to another. But the 4*n was coming because each time the string was coming reversed so that wasted n steps to straighten in it. So doing from middle and adding a letter on each side we can get rid of straightening here.4*n approach: assume u have come to this form S.... S is suffix of required string . Now I will describe a method to convert it to Y.... where Y is bigger suffix by 1 than S. So now we find character before S in t and flip it there so now ....Y... we have.Now we have to bring Y to start for that we reverse whole string(...rev(Y)...) and bring rev(Y) to end (....rev(Y)) and now flip from just before Y giving Y..... . So main idea is getting rid of reverse whole string by doing operations from both sides.
•  » » » 2 years ago, # ^ |   +8 I extend the prefix like you do in your 4N approach, but each time I add a letter from a different end considering that s[0] and s[n-1] are adjacents. At the end the string may need to be reversed and/or rotated. Reversing it is simple: op(n). Then if it needs to be rotated X times, you can do that with 3 operations: op(x), op(n-x), op(n).
 » 2 years ago, # |   +17 Problem E is fucking awesome (no sarcasm)
 » 2 years ago, # |   0
 » 2 years ago, # | ← Rev. 2 →   0 Why is this solution is wrong?! Div2Dhttps://ideone.com/kZvFal Line: 50 :'(
 » 2 years ago, # |   0 Again a good problemset... Thanks codeforces.
 » 2 years ago, # |   0 What is hack test for Div.2 D???
•  » » 2 years ago, # ^ | ← Rev. 3 →   +17 Something like4 41 22 3 401 21You can't win, but you can draw by cycle 2->4->2
•  » » » 2 years ago, # ^ |   0 My code gives the right answer, thanks :D I was fearing something harder
•  » » » » 2 years ago, # ^ |   0 You can check also odd length cycle, then you must win.
•  » » » » » 2 years ago, # ^ |   +1 too many bugs in my solution, yet it passes pretests.seems like bad pretests
•  » » 2 years ago, # ^ |   +6 Suppose, it was against invalid back path construction. It is not enough to build back path until start vertex is found, the additional condition of stop must be the first player in start vertex. Otherwise for the path like (1)->(2)->(3)->(1)->(4)->(5) the first player can win in case of complete path walking, but back path construction, with mistake mentioned above, brings to only (1)->(4)->(5) which is not the win of the first player.
 » 2 years ago, # |   +10 What were the hacks for B?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -7 What was the solution for DIV2.B?? was there primality check involved?
•  » » » 2 years ago, # ^ |   0 You don't have to do a full-blown primality check. Just iterate in descending order through every x for which p < x <= y, and check if it has any divisor d for which 2 <= d <= min(p, sqrt(x)).
•  » » 2 years ago, # ^ |   -10
 » 2 years ago, # |   0 May anyone tell me the core issue to raise a TLE in pretest 4 of Div1B/Div2D? ;)Here is my last solution, sorry for the code being so messy...
•  » » 2 years ago, # ^ |   0 Maybe you didn't judge the condition when there is at least one circle in the graph,but there don't exist anyway to get to a point with a 0 outdegree,then in this case he could at least draw?I didn't pass all the pretests until the end of the contest(it may be something wrong with the output of the path),but I failed on pretest 4 previously,and after I found this condition and judged it I passed pretest 4...Hope it can help you,and sorry for my bad English
•  » » » 2 years ago, # ^ |   0 Well, seemed like I got the issues. I did check for such, but I was totally careless when handling my condition-checker in return commaands.Not sure if it could save me from TLE-ing, but at least it was wrong.Thanks ;)
 » 2 years ago, # |   -51 MATH, MATH, everywhere MATH.
 » 2 years ago, # | ← Rev. 2 →   +15 Hack for D div 2: 5 5 1 2 2 3 5 1 4 1 2 0 1 Expected : Win 1 2 3 4 2 5 
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 What is the answer? Edit: You already edited your comment. Thanks !
•  » » » 2 years ago, # ^ |   +6 Sorry I forget to write the answer ... I edited it
•  » » 2 years ago, # ^ |   0 Thanks, i hope my solution is right.
•  » » 2 years ago, # ^ |   0 how the answer can be win ? when petya moves from 1 to 2 vasya will move from 2 to 5, as both will play optimally. so how can petya win?
•  » » » 2 years ago, # ^ |   0 They don't play optimally, Petya plays for both of them.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +3 ohh ! I wrote the condition for optimally well. As i thought that petya checks whether he will win the game no matter what vasya will move after sleep, or make it draw. And how did it pass the pretests ? As the checking condition itself is entirely wrong
•  » » » » » 2 years ago, # ^ |   -8 And how did it pass the pretests ? pretests are weak in this one, probably intentionally. which is a good idea for div1-B but not good for div2-D.. but i guess thats a disadvantage of mixed round.
•  » » » » » » 2 years ago, # ^ |   +1 pretests are weak. But the checking condition itself is entirely wrong.
•  » » » » » » » 2 years ago, # ^ |   0 coincidence
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Your solution fails for this:3 31 22 1 301Answer is Draw.Idk how you passed pretests, I guess they are weak
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 It fails for all cases as my checking condition itself is entirely wrong, as i misunderstood it.
 » 2 years ago, # |   +12 https://postimg.org/image/ts93ksg85/ still waiting :)
 » 2 years ago, # |   0 Can someone please explain the logic for solving Div2.D/Div1.B ?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 You need to reach a childless node in an odd number of steps to Win. You can track the parents of all nodes that can be visited starting from s in an odd and even number of steps and their in a 2*n array.If one childless node can be visited in an odd number of steps, you win. Else, you draw if there is a cycle attainable from s. Otherwise, you lose.Edit : my condition for cycle detection was wrong. You have to check explicitely for cycles starting from s to differentiate draw from loss
•  » » » 2 years ago, # ^ |   0 Nice. Thanks !
•  » » » 2 years ago, # ^ |   0 Not really. If a cycle has a way in and a way out, which lead to a childless node by an odd number of steps, you can still win.Also, if a cycle has an odd number of sides, any path from it to an arbitrary childless node can lead to victory as well.
•  » » » » 2 years ago, # ^ |   +8 how to check if there is an odd cycle?
•  » » » » » 2 years ago, # ^ |   +2 (Actually, I wasn't able to solve it probably — it got TLE verdicts).Since I can't handle cycles properly, I used Kosaraju's algorithm and divided vertices into SCCs.Then, the condition to call each DFS function is to check if there has been a path from s to that vertex with odd/even number of edges (based on the oddity of the currently working-on-vertex).
•  » » » » » » 2 years ago, # ^ |   0 can u tell me why my code is wronghttp://codeforces.com/contest/937/submission/35735167
•  » » » » » 2 years ago, # ^ |   +5 can u tell me why my code is wrong http://codeforces.com/contest/937/submission/35735167
•  » » » » » » 2 years ago, # ^ |   0 For the failed case, Someone else marked vis[node] = 2; for node = 45. So, when you tried to end game by visiting 45, it was already visited in some path so it was never even tested. Basically, you aren't trying certain paths once that node is visited in some other path.
•  » » » » 2 years ago, # ^ |   +11 If you (implicitly) create a bipartite graph G', with twice the number of the original graph, one vertex for each (vertex, parity) setting, and the same relative neighborhoods and perform a DFS on that graph, this case will be treated without having to explicitly detect odd cycles.
•  » » » » » 2 years ago, # ^ |   -8 Hi, Can you suggest some readings/problems based on the similar idea? A lot of programmers have used this technique, is it well known?
•  » » » » 2 years ago, # ^ |   +3 My algorithm will go at most twice through every edge : once when you reach him with an odd number of steps, and once when you reach him with an even number of steps.I believe this takes care of these two cases
•  » » » 2 years ago, # ^ |   0 How do u calculate if a childless node can be reached in odd number of step(I mean there could be cycles)?Thanx in advance!!
•  » » » » 2 years ago, # ^ |   0 Is this solution correct?We have to reach the start node from childless node in odd number of steps.So lets say we color the nodes starting from the childless node.lets say i color the childless node with black.So i'll color its adjacent white.So the question comes that whether the source vertex can coloured white.So just do a sort of bfs with two visited array ,vis1 to denote if it has been coloured black,vis2 to denote if it has been colored white.push all childless node and start the normal bfs,i mean if i am black and my adjacent are not white then push them,else dont.
•  » » » » 2 years ago, # ^ |   0 each time you visit a node, mark all his children to be visited with the opposite parity, if they have not been visited with this parity. You'll find out in O(n+m) if each node can be reached in an odd or even number of steps, then you can check the childless nodes one by one
•  » » » » » 2 years ago, # ^ |   0 will this handle the cases where there is an odd cycle in the path from s to any vertex?
 » 2 years ago, # |   +1 Could anyone give any hint to solve div2 D?? Thanx in advance!!
•  » » 2 years ago, # ^ |   +4 Just replace any vertex v to vertex (v, 0), (v, 1) and any edge u -> v to two edges: (u, 0) -> (v, 1) and (u, 1) -> (v, 0). Now you can do simple Dijkstra from (start, 0).
 » 2 years ago, # |   0 If you pass pretests on a submission and then get compilation error on the next, does the accepted solution go through system testing or does cf take the last submission even if it gives WA/compilation error?
•  » » 2 years ago, # ^ |   0 the last accepted submission
 » 2 years ago, # | ← Rev. 4 →   +5 In div-2 D, when I tried to hack and got unsuccessful attempt, I realize I misunderstood...I thought the real Vasya starts after some point, So for have a draw, in every possibility they cannot get out of the loop . 3 31 22 1 301my answer is Lose for it although the real answer is Draw :(
 » 2 years ago, # |   0 Another hack for B. Although i din solve D, as i found the test case in which it will fail 35 min before the end and i could not find the solution, this is it. 8 8 1 2 1 3 2 4 6 1 5 1 1 1 7 1 8 0 4 ans is win and 4 5 1 2 3 6 7 8
 » 2 years ago, # | ← Rev. 2 →   0 For div2d .. if: find any path to a leaf and it's vasya's turn --> winelse if: cycle --> drawelse: --> loseWhat's wrong ?Edit: never mind. My code contained a bug
•  » » 2 years ago, # ^ |   +3 else if: cycle --> draw You must also check if you can reach that cycle.
•  » » » 2 years ago, # ^ |   0 When you start from S, any cycle you reach is certainly reachable
•  » » 2 years ago, # ^ |   0 if: find any path to a leaf and it's vasya's turn --> win also, any path can contain itself contain a cycle (might not be required to traverse same cycle more than once though, not sure)
•  » » 2 years ago, # ^ |   0 The fact is that while traversing if you en-counter a odd length cycle, it can be used to change the parity and reach the same state with the other parity of the solution.
 » 2 years ago, # | ← Rev. 2 →   0 How people could solve problem C in 1 minute? Like LodThe.
•  » » 2 years ago, # ^ |   0 idkits fking impossible
•  » » » 2 years ago, # ^ |   0 Possible because questions were from some innopolis olympiad.
 » 2 years ago, # |   0 in D div 2, assuming both petya and vasya play optimally well right?
•  » » 2 years ago, # ^ |   +21 Vasya doesn't even play how he can play optimally lol.
•  » » 2 years ago, # ^ |   +3 No we have to favour petya (check test case 1) vasya can move 1 -> 2 -> 5 but we favour petya thats why 1 -> 2 -> 4 -> 5
•  » » » 2 years ago, # ^ |   0 since petya plays first, how will he wants to lose. And what i thought is petya is checking whether he will win, if tomorrow vasya gets up from sleep and play optimally. AND by the way how did it pass the pretests ?
•  » » » » 2 years ago, # ^ |   0 you are checking petya can win or not irrespective of how vasya will play, if vasya will play optimally there is no way petya can win in first test case.
•  » » » » » 2 years ago, # ^ |   0 He can. if petya goes to 3, instead of 2, He will definitely win, As petya moves first.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 yes if petya will play 1->3 than vasya can't, but both the moves were made by patya, so petya is playing optimally, and vasya's moves always favouring petya
 » 2 years ago, # | ← Rev. 2 →   0 In problem D : my codes second one is correct :( :( https://www.diffchecker.com/FXKB7hnMUPD : second one also wrong ! :))
 » 2 years ago, # |   0 long queue but nice round, hope rated!
 » 2 years ago, # |   +6 4 4 2 2 3 1 4 1 4 0 1 hack for div2 D: ans is lose
•  » » 2 years ago, # ^ |   +3 Doing the hard work but getting WA due to wrongly implementing cycle detection as in a non directed graph = priceless
•  » » » 2 years ago, # ^ |   +16 pretests were too weak.. i was using 0 indexed vertices instead of 1 indexed vertices in dfs and still it passed the pretests
 » 2 years ago, # |   0 Can anybody tell me what is the time complexity of this code for DIV2 B.
•  » » 2 years ago, # ^ |   0 around 300 * sqrt(10^9)
 » 2 years ago, # |   +17 Late hack announcement! Little too late!!!I submitted Div1B in 01:22:38 and it was hacked in 01:31:59. RoomBut I didn't get any hack announcement notification during the contest time. I checked my submission couple of times in Room standings and Common standings but didn't see that it had been hacked. Even, I refreshed the main Problems page and standings page after the contest had ended, till then it was in "pretests passed" state instead of "hacked". I only got a hacked notification during the system testing. I didn't take any screenshots for proof as now I think I should have (sorry). Now I am thinking, how much a late hack announcement/update can affect a contestant? Also had anyone else experienced this?
•  » » 2 years ago, # ^ |   +5 My Div1B was also hacked without giving me a pop-up notification whereas it should be given immediately right after a submission is hacked in normal practice. Luckily, in my case the verdict showed correctly with "hacked" in "My submission" page. As a result, I was not affected by the missing of the pop-up notification after all.
 » 2 years ago, # |   +38 Poland stronk!
•  » » 2 years ago, # ^ |   +32 Tanks in advance!
 » 2 years ago, # |   0 Ooops! Something has broken down in Codeforces :<
 » 2 years ago, # |   +8 In Div2 problem C: what is the correct output for this test case: 999999999999999999 999999999999999998 1000000000000000000
•  » » 2 years ago, # ^ |   0 1000000000000000000.93750000000
•  » » » 2 years ago, # ^ |   0 i got 1000000000000000000.93750000000 and 1000000000000000000.00000000000 and 1000000000000000001.00000000000 from different accepted codes
•  » » » » 2 years ago, # ^ |   0 hmm.. I think its something about the precision. Mine returns the .9375 one
•  » » » » 2 years ago, # ^ |   +6 Thats because mod(x-y)/max(1,y) should be less than pow(10,-9) which is true for all accepted codex,y are expected and actual output
•  » » 2 years ago, # ^ |   0 I am getting 999999999999999998
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 1000000000000000001 here (on AC code).
•  » » 2 years ago, # ^ |   +3 1000000000000000001 to be exact, but just 1.0E18 works
 » 2 years ago, # |   +70 How did LoDThe solved div2A at 00:02:12 and div2C at 00:03:38 in div2?No one in the top20 positions in div1 solved div2C in under 4 minutes, and he even solved A before!
•  » » 2 years ago, # ^ | ← Rev. 6 →   +26 He took part in offline part. Just cheats and no more. P.S. His name is Igor Balyuk
•  » » » 2 years ago, # ^ |   +24 Shouldn't this be taken care of? Because it'd affect the rating change. I mean if he took part in the actual contest before, then it's not fair.
•  » » » » 2 years ago, # ^ |   +4 hope :p
•  » » » » 2 years ago, # ^ |   +20 Of course it wasn't fair. I believe somebody should fix it.
•  » » » » » 2 years ago, # ^ |   0 And the rating has been updated, they won't fix it :( And I'm only 2 short from being a Candidate Master :( It's not fair. I would have been Candidate Master if he didn't participate :( I'm so frustrated now...Can't anything be done?
•  » » » » » 2 years ago, # ^ |   +84 I write to niyaznigmatul and KAN about this problem and don't get any feedback. Lets think it's legal to cheat on rounds.
 » 2 years ago, # |   +3 D went from ~400 ACs to ~70. E F F C Y C L E S
 » 2 years ago, # | ← Rev. 3 →   +5 I got WA for problem DIV2 D on test 28 which was: Participant's output Win 233 971 277 477 871 502 673 37 219 Jury's answer Win 233 864 714 151 370 604 141 233 971 277 477 871 502 673 37 219what was wrong ?
•  » » 2 years ago, # ^ |   +3 Your answer is an odd length, the correct answer must be even length...
•  » » 2 years ago, # ^ |   0 To win you have to have a path of even length
•  » » » 2 years ago, # ^ |   +5 I made a terrible mistake while printing path :(
•  » » » » 2 years ago, # ^ |   +1 If it makes you feel any better, I made the exact same mistake. :(
•  » » 2 years ago, # ^ |   0 Well, to win you need go from 233(turn First Player) to 233(turn Second Player).
 » 2 years ago, # | ← Rev. 2 →   0 Why am I getting the wrong answer for div2B. I used the segmented sieve and I am getting the correct answer when I run it on my pc.Here is the code..
•  » » 2 years ago, # ^ |   0 You mean to say you're getting the correct answer for the case that is failing?
•  » » » 2 years ago, # ^ |   0 Yes.
 » 2 years ago, # |   +23 Testcases for E are too many..
 » 2 years ago, # | ← Rev. 2 →   +75 Currently, Div.1 contest doesn't have a final result yet, because of this.If cki86201's solution for Div1E is correct, he/she will make it to the 3rd place. Cheers! ;)UPD: Accepted. Congrats!
•  » » 2 years ago, # ^ |   +134 Thanks!!
 » 2 years ago, # |   -10 i got wrong answer in C-Div2 because the output number was in double format like that 7.67538e+017 insted of 767537647587662141 , so is that my fault or the judge fault
•  » » 2 years ago, # ^ |   +18 If you are using cout use cout<
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 How to solve problem C ?UPD: Thanks for not replying to this poor. I got it.
•  » » 2 years ago, # ^ |   0 same thing happend with me also..
 » 2 years ago, # | ← Rev. 2 →   -11 Running the same code on the computer gives different results from that when it's run from the judge! Link
•  » » 2 years ago, # ^ |   +17 In this function: int divs(int x) { for(int i=2;i
•  » » » 2 years ago, # ^ |   +9 totally agree with u, in my computer I get -1; So I change this code a little bit, 35711545 , It passes test 1.Hope it is helpful @ LouaiZahran
•  » » » » 2 years ago, # ^ |   +11 Thanks a lot! Akikaze Wavator
 » 2 years ago, # |   +3 Rating changes take forever when you want them to be quick.
•  » » 2 years ago, # ^ |   +3 You may use this site to get an approximation https://cf-predictor-frontend.herokuapp.com According to it you'll become purple with an increase of 150 points Congratulations :)
 » 2 years ago, # |   0 Yes.
•  » » 2 years ago, # ^ |   0 Never purple again! Congrats!
 » 2 years ago, # |   +64 Hmm.. Feels like someone was writing div1 and div2 contest in the same time http://codeforces.com/contest/937/submission/35707300 http://codeforces.com/contest/936/submission/35706280
•  » » 2 years ago, # ^ |   +10 It doesn't make sense. Why did he do that? I could understand testing div1 solutions on div2 pretests, but he submited div1 earlier than div2...
 » 2 years ago, # | ← Rev. 2 →   0 Can somebody please tell me why my code for D gets a TLE at pretest 4? Link- http://codeforces.com/contest/937/submission/35711753For some reason, the DFS function is running into an infinite loop- but according to me that shouldn't be, as I am using the recur[u] to act like visited[u] in a way. I used the fact that, the only way when recur[u] will be 0 again after becoming 1 is when the DFS of the subtree of u ends- else its a cycle which we detect and exit such visited nodes.Any test case or help is appreciated. Thank you :)(I know this can Time out for larger cases, like, vertex s leading to n/2 nodes, and all those n/2 nodes leading down to same chain of length n/2. Like a long-tailed kite. But why is it getting TLE at pretest 4 with n=50 is bugging me :( )
•  » » 2 years ago, # ^ |   +3 After done With current node you are allowing others to come back to the same node later on. Many node can come back which points to this node causing infinite’s loop.
 » 2 years ago, # | ← Rev. 6 →   +23 Hi guys, while you are waiting for editorial, I'll try to help you to solve problem D.So, our task is to find a uneven route to a leaf-vertex (a vertex that has no edges coming from it)The answer is Draw, if the graph doesn't contain leaves at all.If the graph has a leaf (leaves). But a route to each is only even, we need to check whether the graph has a cycle. If it does — the answer is Draw else the answer is Lose.If the graph has a leaf with an odd route to it the answer is Win.Now our task is to output the way to our leaf. We should be careful with it and not break a while(probably :P) cycle if our route at the moment is even! How can we code the written above? I think, that one of the easiest way is to write a bfs and check the following:"If we can reach a V-vertex with an uneven route then we can reach TO-vertex with an even route. And vice a verse"My solution is here. Feel free to ask me some questions. GLHF
•  » » 2 years ago, # ^ |   0 dfs on 2-layers graph looks simpler)We can save sequence at once we found that answer is "Win".
 » 2 years ago, # |   0 Too eager to know solution for Div2 E/ Div1 C.. help required
•  » » 2 years ago, # ^ |   +3 The cleanest solution I've seen is if you perform the operation on x = n, then on x = i, then on x = 1, you move the ith character to the front, e.g. if we want to move the c to the front: front|c|back (ignore the |'s)-> kacb|c|tnorf (x = n) -> frontkacb|c| (x = i) -> |c|backfront (x = 1)Using this operation, you can repeatedly build the string in reverse order, using at most 3*N < 6100 steps.
•  » » » 2 years ago, # ^ |   +3 Oops formatting:front|c|back-> kacb|c|tnorf (x = n)-> frontkacb|c| (x = i)-> |c|backfront (x = 1)
•  » » » » 2 years ago, # ^ | ← Rev. 4 →   0 Thanks. Got it . xD
•  » » » » » 2 years ago, # ^ |   +8 I think it would be x=i since after the first operation the character is in the n-i'th position.
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +23 Got it man. Thanks. by the way your last ans is wrong. it should be |c|frontkacb
 » 2 years ago, # |   +6 I am seeing some pretty complicated submissions for problem B — Vile Grasshoppers. The main idea is that the distance between consecutive primes upto 10^9 is never more than 300 or so. This allows us to start from y and keep decrementing, till we get a number who's smallest factor is greater than P. Worst case, we will not have to do more than 300 root(n) factorisations. Explanation and code.
 » 2 years ago, # |   +1 Lost ~1300 points because I didn't use std::fixed in the output of Div2/C...
•  » » 2 years ago, # ^ |   0 me too :( now my rating change is -35 instead of predicted +35.
 » 2 years ago, # |   0 Can anyone tell me why my solution is failing at test 28? http://codeforces.com/contest/936/submission/35722758
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Cause in your solution you do not consider paths like 1->2->3->1->4->5 when you can return to previously passed vertex and still win, I guess so.Check this out: 5 52 2 41 31 11 50 1If it returns "Draw", your solution is wrong.
 » 2 years ago, # |   +2 When can we expect editorials ?
 » 2 years ago, # |   0 Hey in the C problem of div. 2 one of my friend's code got accepted and as I was going through the test cases I found this(refer link). How is this possible? https://drive.google.com/open?id=1scjEnYJuRpkfcu2gPGvJRpBm94NcH1sH
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Everyone who solved C has this problem, but the answers are definetely right
 » 2 years ago, # |   0 How to solve Div2 C?
•  » » 2 years ago, # ^ | ← Rev. 5 →   +14 Our goal is to find how long will be a chicken in a fast mode and in slow :D.So, in first k minutes chicken will be prepared for ((k/t)*100)%.fastMode=((k/t)*100)Now we need to find a moment of time when Julia will again switch chicken to fast mode. This moment will be f:f=ceil(k/d)*d => (f-k) minutes chicken will be in a slow mode and will be prepared for ((f-k)/(2*t)*100) %.slowMode=((f-k)/(2*t)*100);So total time of that cycle is k+(f-k). After each cycle our chicken will be ready for fastMode+slowMode%.Now let's find out how many full cycles we will be able to "put" in our 100%. That is floor(100/(fastMode+slowMode))At that moment our answer=floor(100/(fastMode+slowMode))*fFinally we need to check how many percent of chicken preparation left left=100-floor(100/(fastMode+slowMode))*(fastMode+slowMode). If it is equal less than (k/t)*100 then we just add to our answer (left/(fastMode))*k, else ans+=k, left-=fastMode and then ans+=(left/(slowMode))*(f-k)Yeah, I see it looks quite complicated , but you are free to ask questions. Maybe my solution could also help.** P.S. When I was using % (multiplying by 100) i received a WA on test case #32. On codeforces compiler answer was "nan" while on mine it was OK :( **UPD Corrected a formula
•  » » » 2 years ago, # ^ |   +3 If d > k then your algorithm will give f = 1 => f-k = 1-k(negative for k > 1) minutes chicken will be in slow mode. Isn't it undesirable? BTW thanx for great explanation.
•  » » » » 2 years ago, # ^ |   +5 Yeah, I did a mistake Correct is: f=ceil(k/d)*dThank you for your answer.
•  » » » 2 years ago, # ^ |   0 This solution is correct but the formulas can be simpler:Indeed, the chicken is cooked in fast mode for k minutes then, for d — k mod d minutes. Indeed, after k + (d — k mod d) minutes, you will be on a multiple of d. So the lenght of a cycle is of k + d — k % d. The formula for the number of cycles : cycles = t / (k + (d — k%d)/2)
•  » » » 2 years ago, # ^ |   0 When I ran your code for k = 2, d = 5 and t = 10 it outputs 14 whereas the answer should be 12, shouldn't it? or am I missing something?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 The correct answer is 14.After first cycle: chicken is prepared for 4/20+3/20=7/20; TimeTaken=5;Second cycle: chicken is prepared for 14/20. TimeTaken=10;Third cycle onlyFastMode: chicken is prepared for 18/20. TimeTaken=12;We need to prepared chicken for 2/20, while using fullSlowMode we will prepare it for 21/20. That's why we need to use only 2/3 of our SlowMode. So the time of this part of SlowMode will be 2/3*3=2.TimeTaken=12+2=14
•  » » » » » 2 years ago, # ^ | ← Rev. 4 →   0 As d = 5 when Julia goes to kitchen at t = 5 she will find the stove to be on. So she will not do anything and return. So The time period of one cycle comes out to be = 10. I guess you have taken time period of your cycle = d(= 5) which I think is be wrong in this case... How I visualized it is as follows When the clock is high it means gas is on and when it is low it means gas is off.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 You misunderstood the problem. The stove turns off by itself, but only Julia can turn it on. When t=4, who turned it on on your graphic?
•  » » » » » » » 2 years ago, # ^ |   0 Yeah my bad I misunderstood the problem. Anyway thanx for helping me.
 » 2 years ago, # |   +15 Editorial?
 » 2 years ago, # |   0 can someone tell me why my code is wrong and how can i rectify it thanx in advance..http://codeforces.com/contest/937/submission/35735167
 » 2 years ago, # | ← Rev. 2 →   +6 17 people contributed to this contest and there is no editorial after one day!!UPD1 : a semi editorial is posted,hope to see the complete one!
•  » » 2 years ago, # ^ |   +26 Perhaps Brooks's law applies to writing editorials, too?
•  » » » 2 years ago, # ^ |   0 although i had to use wikipedia to understand your comment's meaning, but i'm agree with you :D
•  » » » 2 years ago, # ^ |   +10 I think it's more of bystander effect.
•  » » » » 2 years ago, # ^ |   +15 I wouldn't call this round an accident. I quite liked problem C.
 » 2 years ago, # |   0 Why 35710602 WA ? Div2D
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Your problem is that you overlooked the case when you have a cycle with odd number of vertices where you should transverse the cycle to change the turn from Petya to Vasya and vice versa.Consider the following testcase: 5 4 2 2 4 1 3 1 1 1 5 0 1 This corresponds to a graph that has a cycle 1->2->3->1 but it still had an answer 1->2->3->1->4->5 Your Code gives a wrong answer in that case as it prints "Draw" instead, you just didn't handle the cycles with odd number of vertices case.
 » 2 years ago, # |   0 When will we get tutorials for the problems ?
 » 2 years ago, # | ← Rev. 2 →   0 i was waiting for editorial but after a day now i decide to ask my question here...how to solve Div2.D(Div1.B)?
•  » » 2 years ago, # ^ |   +34
•  » » » 2 years ago, # ^ |   0 thanks... better than nothing!!
 » 2 years ago, # |   +1 where's the tutorial to the problems ?
 » 2 years ago, # | ← Rev. 2 →   +2 pls, upload the editorials...
 » 11 months ago, # |   0 niyaznigmatul Div. 1 E doesn't appear to be viewable.
•  » » 4 months ago, # ^ |   0 I'm having the same trouble.niyaznigmatul Could you fix it?