### niyaznigmatul's blog

By niyaznigmatul, 3 years ago, translation, Tutorial is loading...

Prepared by vintage_Vlad_Makeev

Tutorial is loading...

Prepared by GreenGrape

Tutorial is loading...

Prepared by dusja.ds

Tutorial is loading...

Prepared by pashka and YakutovDmitriy

Tutorial is loading...

Prepared by dusja.ds and VArtem

Tutorial is loading...

Prepared by dusja.ds and burakov28

Tutorial is loading...

Prepared by Nebuchadnezzar Tutorial of Codeforces Round #467 (Div. 1) Tutorial of Codeforces Round #467 (Div. 2)  Comments (58)
 » 936B — Sleepy Gameverdict — WA on test 31This is my code: 35744011. I think my code handles the Win case properly.But the strategy for Lose or Draw is somehow messed up. Help needed.
•  » » Test this:4 301 32 2 401Correct output: Lose
•  » » » hi there, i checked whether the source is disconnected, if so then Lose.but still WA on test 31. 35746464Can you suggest me when to output Draw considering reverse graph? thank u
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   You have to make sure that there is a cycle in the graph reachable from s: 5 5 1 2 1 3 0 2 3 5 1 4 1 
 » how to calculate time complexity of B(div2)?
•  » » Well, worst case, you need to check all numbers from y to p. Although, if there's a prime number between y and p, you will not go down to p. The max difference between 2 consecutive prime numbers under 10^9 is of 300 so you will at most check 300 numbers. Checking a number is done in O(min(sqrt(N), p)). Therefore, the complexity is of : O(300 * min(sqrt(N),p)) Wich is equivalent to O(min(sqrt(N), p))
•  » » Prime gap multiplied by for factorization.
•  » » » thank you..I forgot to think about the prime gap..thanks
•  » » » Hi, I can't see why consecutive primes' gap under 109 is less than 300. Is that inference of some theory? Would you pls explain a little more?
•  » » » » Here is a link about the distribution of prime numbers. Basically, what it says is that the nth prime number is roughly equal to .This implies that if you brute force to check all consecutive integers that are less than y, you will likely find one in roughly 300 checks. If you check here, you'll find that to be pretty accurate.It's unfortunate because prime gap, while well known, I don't think is well known enough to be considered standard Div2 B level. It really rested on you knowing this fact.
•  » » » » » Thanks! But I still have a question: how do we get the number 300 from the number 109? Or is that just a common sense? What if in this problem y is less than 1010, how do we estimate the upbound of check steps under this circumstance?
•  » » » » » » To be completely honest, I have no idea why it is as large as 300. From the link I shared, all you can deduce is that the average prime gap between prime p and the next prime is going to be roughly equal to , which would mean that on average, we only have to check numbers, but empirically it seems that 300 is what it turns out to be. It makes sense that the gaps tend to increase as the numbers increase, but I don't totally know how 300 was calculated.
•  » » » » » » » Well, I see, 300 is an exact number, but what matters in this problem is that according to prime distribution we know that search down from y is reasonable since there won't be too many numbers between two successive primes.Thanks a lot!
•  » » » » » » » He was talking about maximal prime gaps
•  » » » » » » » Suppose that y is 36 and p is 4, then our answer should be 35? Right? But 35 is not prime, then why are we searching for prime nos. plz explain someone. I'm sure that i am wrong somewhere
•  » » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   We are not searching for prime numbers. We are trying to analyze the complexity of this brute force algorithm of checking all the numbers below $y$ until we find one that works. So, we know the complexity of the algorithm will be the time it takes to factorize each number multiplied by the number of integers you must check. To get a bound on the number of integers we need to check, we notice that if we find a prime number between $y$ and $p$, that number MUST work. First, convince yourself that this is true. Then, we know from above that the largest gap between two primes below $10^9$ is $300$, so if we do $300$ checks then we MUST have found something that works (regardless of whether or not it is prime). This gives an upper bound on the number of integers we must check as $300$.
•  » » » » » » » » » ohkk..Now I understand. Thank you very much.
 » I think there must be more interesting (maybe more effective?) ways to solve Div 1 Pro C.Could anybody share his or her solution?
•  » » 3 years ago, # ^ | ← Rev. 6 →   Mine is less effective, but it's more simple (probably).We construct t by adding every character to the front of s in reverse order of appearance in t. so if t = t_1, t_2, ... , t_n, Then the steps are s = ... -> t_n .... -> t_(n-1), t_n ... -> t_(n-2), t_(n-1), t_n ... -> ... -> t_1, t_2, ..., t_n Say we currently have a string AzB, where A and B are substrings and z is the current character that we want to move to front. We also don't want to touch A in process. So we must get: AzB -> zA[some string]We can do that in 3 steps (here A' is the reverse of A, and B' is the reverse of B) AzB -> B'zA' (shift n) B'zA' -> AB'z (shift k := |A|) AB'z -> zAB' (shift 1) In total we need exactly 3*n operations (3*(n-1) if you want to skip the last step)
•  » » » I like it. It's fairly simple. Thanks for sharing!
•  » » There's a solution that uses 2 * n + O(1) operations....x...abc cba......xcba......x xcba......xcba..y... ...yxcba.....yxcba.. .....yxcbaSo you can append this sequence to one side and invert the string, now just construct the string from the middle outwards and it's fine1 2 3 4 5 6 7 8try constructing6 53 4 5 68 7 6 5 4 31 2 3 4 5 6 7 8http://codeforces.com/contest/936/submission/35713391 I actually used the idea of inside/out during the contest and when someone told me the easier way to solve it I merged both approaches and this is the result.
 » DIV B , C problem solutions please.
 » 3 years ago, # | ← Rev. 3 →   Thanks for the clear editorial. However, I found it difficult solving Div.1 Pro.D . Since the official editorial hasn't been published till now, can anyone give me a solution? Thanks a lot.
•  » » Greedy solution starting from the end of the line. For each row, keep track of the maximum first cell of the line in which a shot must occur to reach this cell.For each cell of the grid (you can aggregate all empty cells in only one, so this will reduce your grid to a maximum length of 2n), keep track of : - is there a change of line in the optimal path (there is one iff the other line contains no obstacle, and reaching the other past will only require you to shoot in the future) - Does going through this cell forces you to make a shot (and if so in which cell)When you're done, check if the first shoot needs to occur before or after t. If before, answer is No. If after, you can loop through the grid starting from the start and construct the list of moves and shots. Complexity and memory : O(m1+m2)
 » editorial of 937C??
 » 936A — Div1 //..... if (k%d==0){ cout << t; return 0; } else { period = (k/d)*d+d; } //.....and other 
 » Div2 C / Div1 A Save Energy Problem Editorial ?? @Anyone
•  » » Imagine a state block that contains the two periods 0 -> k & 0 -> x where x is the smallest multiplier of d that is greater than k, that is 0 < k < x meaning that the oven is turned on for the period 0 -> k and then becomes off for the period k -> x, then again turned on for x -> x + k then turned off for x + k -> 2*x and so on... now given a point in time say p can you calculate the number of these state blocks and the corresponding time spent in either the two modes of the oven?Drawing always helps!for reference: 35748765
 » 3 years ago, # | ← Rev. 2 →   in problem div 2 c i understand that 1/t (x)+ 1/2t (y)=1 after taken 1/t as common factor it will be 1/t (x+0.5y)=1 after dividing by 1/t it will be x+0.5y=t so how could i use k and d to find y or x and if this basic idea is not right so what's the right one thanks in advance
•  » » hmm , let me explain my approach . the process can be broken into many time intervals ( of the form (k+x) ) k — time stove is on (in one time interval ) . x — time stove is off (in one time interval )one_time_interval = k+x work done in one time interval = k + x/2 num — number of time intervals required num = t/(k + x/2) or 2*t / (2*k +x)rem — remaining work after num intervals . rem = t — num * (k + x/2)if rem less than equal to k then total_time = num * one_time_interval + rem else total_time = num*one_time_interval + k + 2*(rem — k)35813560
•  » » » Why "x = d — k%d" and "work done in one time interval = k + x/2 "? ...Could u explain details,pls QAQ
•  » » » » x is the time when the oven is off so it is half of the time when the oven is on it's in the problem statement and d is a period of time when it's on and k when we gonna turn it off take this example 2 and 3 first test case d is like a cycle every d minutes the oven is on and k is another cycle every k minutes it will be off that's what i understood until now and i don't get the part of x=d-k%d so i hope if he explained it
•  » » » 3 years ago, # ^ | ← Rev. 2 →   why x=d-k%d don't get it i understood your solution completely expect this part and thanks a lot for your explaining and sorry for taking from your time :)
•  » » » » lets see when for the first time we find stove to be off . lets say we checked at n*d (time t1) and stove was on , now we will check at (n+1)*d (time t2) and now stove is off , sok >= t1 and k < t2 ,also t2-t1 = d or t2= t1 + dnow for how much time after t1 stove will remain on ? it will remain on for time , t_on = k — t1 ,so it will remain off for time t_off = d — (k-t1) , also, k — t1 can be written as k%d (since t1 is a multiple of d and k is greater than t1 and less than t1 + d )so total time stove is of is t_off(or x) = d — (k%d)and total time stove was on is k,this cycle will repeat again until work is done
•  » » » » » thanks for your help i get it now thanks a lot
 » 3 years ago, # | ← Rev. 2 →   Let's look at test for task Iqea: ООО О_О ООО O it is shop, _ is empty space I think if we look in graph like in tutorial, we will find cycl, it won't be a tree. Could you explain it?
•  » » I don't get your test case.
•  » » » Sorry, I fixed the problem
•  » » "It's possible to get from any cell that doesn't belong to Gridland to any other cell that doesn't belong to Gridland by using only cells which don't belong to Gridland"
•  » » » Thank you, I understood
 » Can we solve the problem Save Energy using Binary Search too?
 » 3 years ago, # | ← Rev. 2 →   Excuse me for being dumb. But isn't that enough for Draw to not have at least one vertex without edges from it? P.S.About problem B. Sleepy Game
•  » » Yes, if there are no vertices without outgoing edges, it must be a draw. However, it may be a draw even when there are no vertices with outgoing edges.
•  » » » You mean the situation when m = 0, or what? That's a single one, so. Or you ment something else?
•  » » » » For example the graph here https://i.stack.imgur.com/pQxtv.png if you start at node A, the answer would be draw, even though there is a vertex without outgoing edges.
•  » » » » » Thanks!
 » Can someone help me notice whats wrong with my algorithm for DIV2D(Sleepy Game), its failing on testcase 28.http://codeforces.com/contest/937/submission/36052813
•  » » can you explain your approach?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   So basically, i just make a graph like you would usually do, then start dfs from the node where the coin is initially positioned. I keep int array 'bio' which tracks 3 things: 0 if the node haven't been discovered yet, 1 if its being discovered and 2 if its fully discovered — this is to detect cycles in a graph, if at any point i get to some node that has edges that connect to a node that is being discovered then a cycle is detected. Now, in dfs function i keep track if the current node has 0 parity and if it doesnt have any outgoing edges — "if(!graph[a].size() && !(path.size() % 2))" and also i have a vector that tracks the path, if a node that has 0 parity and no outgoing edges is found then print the path and exit, if not the check if theres a cycle and print "Draw" otherwise print "Lose". Judging by the test case 28 my code doesnt properly detect a node that has 0 parity and no outgoing edges i guess, since solution finds it and mine outputs "Draw".
•  » » » » Your code is failing for this input. keep one thing in mind that if you re-visit any node from a odd length cycle, your parity will change and thus possibly help you to win. 5 5 1 2 2 3 5 1 4 1 2 0 1 Expected : Win 1 2 3 4 2 5 
•  » » » » » I see, thanks a lot for the help!
 » 3 years ago, # | ← Rev. 2 →   Why does this solution in "Sleepy Game" gives TLE in test 20?Submission: 36210574
•  » » I think your solution prints infinite number of nodes which causes TLE. Be careful with your print() function.
 » Solution to 936C is not clear from the editorial! Can anyone please explain a bit more in detail?
 » In Div2 D/Div1 B, my submission got Wrong Answer on test 35, please, I need help in why it is WA.My logic is to start a DFS from vertex s, and allow each edge to be visited two times atmost, so I can test if any cycle will be useful for Petya to win. And any cycle will make the answer atleast Draw. If there isn't any cycle and all the leaves vertices don't make Petya the winner, then answer is Lose, beacause it is impossible to make 10^6 moves in 2*10^5 edges which atmost will be visited one time.
 » niyaznigmatul can you show your code? (Div2 B);
 » In problem can we just find a max prime in range k+1 to n and print it
 » Just a note: the main idea of using "states" in Div2 Problem D/ Div1 Problem B is that any vertex in the winning path is visited atmost twice in the original graph (each with different parity), as if it visits multiple times with the same parity, we can just use the first occurrence of that parity and continue.