### gridnevvvit's blog

By gridnevvvit, 8 years ago, translation,

Soon (on March 16, 19:30 MSK) you are lucky to participate in Codeforces Round #236 for both divisions.

Problems have been prepared by me. It’s my first round for both divisions and I hope not last. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Ilya Los (IlyaLos) and Ignatyev Alexander (ai9128429340875) for testing of problems, Mary Belova(Delinur) for translating the problems, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD: Scoring system:

Div. 2: 500 — 1000 — 1500 — 2000 — 2500

Div. 1: 500 — 1000 — 1500 — 1500 — 2000

UPD:

Contest finished, congratulation for winners!

Div.2 :

Div. 1:

UPD:

UPD:

• +140

 » 8 years ago, # | ← Rev. 2 →   +225 Please don't click on "Rev" because I wrote something bad :(
•  » » 8 years ago, # ^ | ← Rev. 2 →   -57 BEG y'all for some mercy on not so many downvotes, OK?!
•  » » 8 years ago, # ^ | ← Rev. 4 →   -60 why you wrote something bad rather than writing something good like scoring system please don't click on "Rev" before the start of the contest I wrote Scoring System
•  » » 8 years ago, # ^ |   0 funny :p
 » 8 years ago, # |   0 Why this entry does not appear in the home page ?
•  » » 8 years ago, # ^ |   +13 Stop downvoting, it wasn't on the home page indeed at that point.
 » 8 years ago, # |   +7 wish all participants a very happy Holi :)
•  » » 8 years ago, # ^ |   0 Happy Holi bro..
 » 8 years ago, # |   +41 your first both divisions contest after many Div2 contests :)
 » 8 years ago, # | ← Rev. 4 →   -43 I wish it will be a good contest as always !!
•  » » 8 years ago, # ^ |   +37 :| Everything is funny for the first time!
 » 8 years ago, # |   +61 Since next Div.1 contest is on March 22, this contest is "Good Bye 1392" contest for Iranian Div.1 contestants. Nowruz 1393 is on March 20 so Div.2 contestants have one more contest in 1392 :) Happy Nowruz
 » 8 years ago, # |   -12 I wish it will be a great contest as always !!
 » 8 years ago, # |   +7 I guess, first time DIV2 contest takes a contest-id less than the corresponding DIV1.
•  » » 8 years ago, # ^ |   +6 true that. it maybe because of the statement of the last contest's problem B
 » 8 years ago, # |   +46 The overall feeling is that tasks are tend to be a bit artificial, especially B.And for E, I can't understand the statement.Thank you gridnevvvit! I believe your next round will be better. :)
•  » » 8 years ago, # ^ |   0 I feel that problem C just came out of nowhere...
 » 8 years ago, # |   +5 It was horrible Adiv2, but this is the first contest when I'm not sure in my B,C ideas at all) Smth new for me, thanks.
•  » » 8 years ago, # ^ |   0 So am I.
 » 8 years ago, # | ← Rev. 2 →   +6 What is the solution for C ?
 » 8 years ago, # |   +51 Is it just me or sometimes constraints on Codeforces are unnecessarily tight? For example today, I resubmitted B because I thought 5000 * sqrt(10 ^ 9) modulo operations won't pass in 1 second. Some time ago I got TLE for 5000 * 5000 in 2 seconds, although that was the expected complexity. Just because I also had 5000 * 5000 memory. Well today, after resubmitting I tried to hack such a solution and it fit into the limit, in something like 0.95. So why make n = 5000 when you want n ^ 2? Why make n = 5000 today? The only way in which 5000 instead of 1000 (for example) affects the contest is that some sloppy implementations may TLE and others may not, depending on some non-algorithmic issues (cache breaking, input/output speed, speed of used operations, etc). This was a good contest, congrats to the authors. They're not the target of this post, I'm just saying that generally we could avoid such issues if we just stick to reasonable limits, which don't cause doubts about TLE, be it for submitting or hacking.
•  » » 8 years ago, # ^ |   0 Actually there is a faster way then sqrt(10^9)...
•  » » » 8 years ago, # ^ |   0 What is the faster way?
•  » » » » 8 years ago, # ^ |   0 It's probably O(number of primes < sqrt(10^9))? (if we don't count Pollard's Rho algorithm here)
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +8 sqrt(10^9) — something finitenumber of primes — infinite=>(numbers of primes < sqrt(10^9)) = 0O(0) is pretty fast :P.Btw pi(n) = O(n / ln n), where pi(n) if of course number of primes numbers less than n.
•  » » » 8 years ago, # ^ |   0 Well I know there's a faster way, do you think I resubmitted the same thing? But the optimization brings 0 additional value to the problem. So why think about if it's necessary or not? Why guess if it's needed or not when hacking?
•  » » » » 8 years ago, # ^ |   0 You are using map which is red-black tree. Any number x has not got more then one prime divisor bigger then sqrt(x).
•  » » 8 years ago, # ^ |   +5 Agreed. 5000 * sqrt(10 ^ 9) failed. That makes me frustrated.
•  » » » 8 years ago, # ^ |   0 I think precalculate the prime that smaller than sqrt(1000000000) would be better. You can do it in O(n) time. That won't cause a Tle.
•  » » 8 years ago, # ^ |   +6 I've tried to hack a solution with 2 * 5000 * sqrt(10^9) operations and his solution took 0.998s... (I don't know how it is even possible to do more than 300,000,000 operations in less than 1s). As you say, I think it should have been n <= 1000 if this kind of solution was considered as OK or n <= 10000 if not. Nevermind, goodbye red :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 Totally depends on the operations. 3e8 array indices would probably be too slow, but if everything fits into the registers, you can get close to 2e9 cycles per second or so (= frequency of your processor).
 » 8 years ago, # |   +11 My accepted D1-A solution is as follows:For each step, create edge (u, v) with the smallest deg[u]^2 + deg[v]^2.It does not care about p, 2n + p, nor 2k + p. What is the intended solution, then?
•  » » 8 years ago, # ^ |   0 If you solve p = 0 then you can add any p edges and the solution will be ok. To solve p = 0 you can make a cycle out of N — 1 nodes, tie the N-th one to them and add 2 more edges somewhere. There are other ways, of course.
•  » » 8 years ago, # ^ |   +2 I didnt really understand the problem and just generate the pattern for C div2...and got AC :v
•  » » 8 years ago, # ^ |   +6 look at this solution for the same problem :P
•  » » » 8 years ago, # ^ |   -22 fuuuu, pascal
•  » » » » 8 years ago, # ^ |   0 tourist usually code in Pascal. That is not make any problem to him to be the first
•  » » » 8 years ago, # ^ |   0 And what?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 The condition is equivalent to saying that removing any vertex should delete at least two edges. So if for every vertex you can pick 2 edges touching it (each edge can be picked by at most 1 vertex), you're ok.I just connected i to (i+1)%n and (i+2)%n, and added p random additional edges.
•  » » 8 years ago, # ^ |   +6 I was creating edge for min(degree[i]+degree[j]).
•  » » 8 years ago, # ^ |   +3 I simply "distributed" 2*n+p edges in the manner hinted in sample solution 1-2,2-3,3-4,4-5 .....,1-3,2-4,3-5,4-6 ....,1-4,2-5,3-7 ...till the count becomes 2*n + p .. didnt care for the subgraph conditions
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I was reducing the code written in 3 minutes (deleting vectors,pairs), until it became my solution)  int cn; cin >> cn; for(int ci = 0; ci < cn; ci++) { int n,p; cin >> n >> p; int cnt = 0; for(int k = 2; k <= n; k++) for(int i = 1; i < k && ( cnt < (2*k + p) ) ; i++) cout << i << " " << k << "\n", ++cnt; } 
 » 8 years ago, # |   0 Another Tricky Contest but there could be a lot more hacking attemps!
 » 8 years ago, # |   0 Where can I check the editorial and the testcases?
 » 8 years ago, # | ← Rev. 2 →   +28
•  » » 8 years ago, # ^ | ← Rev. 3 →   +17 i dont know whats the funniest of the following: user thinks that adding comments makes it difficult for others to see that solutions are similar the two handles are FakeErdem2 and ErdemKirez (also very similar) they both submitted within 30 seconds of each other the "fake" account submitted before the "real" one
•  » » » 8 years ago, # ^ |   +3 The last point is just to not affect rating if the pretests failed .
•  » » » 8 years ago, # ^ |   0 Adding comments makes it difficult for system to skip the solution automatically.
•  » » » » 8 years ago, # ^ |   +8 oh. so ur saying that if two exactly identical solutions are submitted, system skips the second one automatically? i dont think this should happen. what if both codes are copied from some old blog post or any other public site?
•  » » » 8 years ago, # ^ |   +6 They actually have cheated in this way during the contests 225, 226, 227, 234 and 235, so this means that their strategy is not this bad...
 » 8 years ago, # |   +2 Sooo when will ratings be updated ???
•  » » 8 years ago, # ^ |   0 updated.
 » 8 years ago, # |   +31 Time limit in problem B is too strict. I've got TLE and got AC (after contest) by a small optimization. I think that either TL must be adjusted to 2s-3s or biggest test (test with biggest run time) should be in pretests.
•  » » 8 years ago, # ^ |   +1 same happened to my code..
 » 8 years ago, # | ← Rev. 3 →   +2 Time limit for D : Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Accepted..
 » 8 years ago, # | ← Rev. 2 →   0 What's wrong in my solution of Pro.B Div2? Anyone can help? Submission:6037256
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 So complicated way. Why dont you just find the first element of the corresponding element of array and count it? And the constraint is so small only about 1000 first element was able to counted.If there are some element had been in the right order in sequence for a first element most, so its the most probable sequence. Then find differences with corresponding element in array. Just itHere my solution : 6037944
•  » » » 8 years ago, # ^ |   0 Thanks.
 » 8 years ago, # |   0 Putting an advanced topic in a C problem even it's a direct one wasn't a smart idea i think !
 » 8 years ago, # | ← Rev. 2 →   0 Whats wrong with my idea, can anybody tell me? I have confusion with "//*******************" marked lines. http://pastebin.com/vi446T5fDiv2 D,div1 B
•  » » 8 years ago, # ^ |   0 Actually it is quite funny mistake :D In those two lines V[j]/=gcd(V[j],Div[i]); Div[j]/=gcd(Div[j],Div[i]); the iteration at which j==i (the first iteration of the loop) ... the value of Div[i] becomes 1 ... So it is not the correct value for the rest of iterations when j
 » 8 years ago, # |   +2 I seriously can't understand E. If the edge (x, y) is of different colour than (p, q), then x and y lie in a different tree than p and q, so condition 2 is impossible. No?
 » 8 years ago, # | ← Rev. 2 →   0 waiting eagerly for Round Statistics which DmitriyH usually posts!EDIT: its now available here, and i got my wish of my name being published! :)
 » 8 years ago, # |   0 I am stuck on 402D/403B. I tried several approached but I keep getting TLE. I think I am missing something here. Can someone please have a look : Using Sieve factorization (TLE at #18) : http://codeforces.com/contest/402/submission/6050051 Using Normal factorization (TLE at #42) : http://codeforces.com/contest/402/submission/6046374
•  » » 8 years ago, # ^ |   +4 Just add this line to your first solution and it becomes fast: for(int p : primes) { if (p*p > v) break; // <- add this line int cnt = 0; I tested it here: http://codeforces.com/contest/402/submission/6050585
•  » » » 8 years ago, # ^ |   0 Thanks a lot pllk !
 » 8 years ago, # |   0 DIV 2 problem B. I tried searching for the most common number in the array Ai-i*k(*Ai is the input, as long as the this number is positive) and the answer should be n-(the amount of times this number appears) but for some reason i cant pass test 8. is my idea wrong? Java submission: 6050363
 » 8 years ago, # |   0 I want to know the problem C why the tree can't have the height of 0
 » 8 years ago, # |   0 hi, someone can explain solution for problem E div2/C div1?
•  » » 8 years ago, # ^ |   0 Just for the strongly connected components A^k means The path length between two points for K
 » 8 years ago, # | ← Rev. 6 →   0 I was trying to find a twist in the logic of problem c (searching for graph) but the logic seems straight forward i.e removing edges from the smallest sub graph of i.e sizes 1 , 2, 3.... going up the subgraph until all the extra edges are removed seem to work. I am suspecting the logic cannot be that simple. Do you think this is really the logic?For example: for 12 nodes and 0 interestingnesstotal edges in complete graph = 66, total edges in the solution = 2*12 = 24total edges to remove = 42here is how i remove itnodes -> 12 11 10 9 8 7 6 5 4 3 2 1edges in subgraph-> 11+ 10 + 9 +8+ 7 +6+ 5 +4 +3 +2+ 1+ 0 (for eg. for graph of size 3 total edges 2 + 1 + 0)after removing the edgesedges in subgraph-> 11 + 10 + 3 + 0 + 0 + 0 + 0 +0 + 0 +0 + 0 + 0
 » 8 years ago, # | ← Rev. 2 →   +4 Nice One for Div 2. Thank you for arranging that. Hope You will arrange some more next time. Plz post the tutorial.
 » 8 years ago, # |   0 There were many chances to hack, but I couldn't do at all =(
 » 8 years ago, # |   0 Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together in codeforce!
 » 8 years ago, # |   0 Hii,in Editorial of Prblem C, Searching for Graph, Contest #236 they have talked about some 0-intersecting graphs... i dont have any idea and i am unable to find this on internet, so can anyone please give me some link, from where i can gather some information about this topic.thank you
•  » » 8 years ago, # ^ |   0 Laman graph is a -3-interesting graph.
 » 6 years ago, # |   0 My solution of Problem D is receiving Denial of judgement error. Could anyone please explain to me what is the problem?The Submissions Ids areSomeone please tell me what should be the countermeasure. Thanks in advance.