### niyaznigmatul's blog

By niyaznigmatul, 11 months ago, translation, ,

Prepared by gritukan

Prepared by GreenGrape

Prepared by dusja.ds

Prepared by pashka and YakutovDmitry

Prepared by dusja.ds and VArtem

Prepared by dusja.ds and burakov28

Prepared by BudAlNik

•
• +89
•

 » 11 months ago, # |   0 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.
•  » » 11 months ago, # ^ |   +6 Test this:4 301 32 2 401Correct output: Lose
•  » » » 11 months ago, # ^ |   0 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
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 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 
 » 11 months ago, # |   +4 how to calculate time complexity of B(div2)?
•  » » 11 months ago, # ^ |   +4 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))
•  » » 11 months ago, # ^ |   +3 Prime gap multiplied by for factorization.
•  » » » 11 months ago, # ^ |   0 thank you..I forgot to think about the prime gap..thanks
•  » » » 11 months ago, # ^ |   0 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?
•  » » » » 11 months ago, # ^ |   +1 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.
•  » » » » » 11 months ago, # ^ |   0 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?
•  » » » » » » 11 months ago, # ^ |   0 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.
•  » » » » » » » 11 months ago, # ^ |   0 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!
•  » » » » » » » 11 months ago, # ^ |   +8 He was talking about maximal prime gaps
 » 11 months ago, # |   +5 I think there must be more interesting (maybe more effective?) ways to solve Div 1 Pro C.Could anybody share his or her solution?
•  » » 11 months ago, # ^ | ← Rev. 6 →   +34 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)
•  » » » 11 months ago, # ^ |   +3 I like it. It's fairly simple. Thanks for sharing!
•  » » 11 months ago, # ^ |   +59 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.
 » 11 months ago, # |   -13 DIV B , C problem solutions please.
 » 11 months ago, # | ← Rev. 3 →   0 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.
•  » » 11 months ago, # ^ |   +10 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)
 » 11 months ago, # |   +6 editorial of 937C??
 » 11 months ago, # |   0 936A — Div1 //..... if (k%d==0){ cout << t; return 0; } else { period = (k/d)*d+d; } //.....and other 
 » 11 months ago, # |   +3 Div2 C / Div1 A Save Energy Problem Editorial ?? @Anyone
•  » » 11 months ago, # ^ |   +2 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
 » 11 months ago, # | ← Rev. 2 →   +1 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
•  » » 11 months ago, # ^ |   0 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
•  » » » 11 months ago, # ^ |   0 Why "x = d — k%d" and "work done in one time interval = k + x/2 "? ...Could u explain details,pls QAQ
•  » » » » 11 months ago, # ^ |   0 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
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » 11 months ago, # ^ |   0 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
•  » » » » » 11 months ago, # ^ |   0 thanks for your help i get it now thanks a lot
 » 11 months ago, # | ← Rev. 2 →   0 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?
•  » » 11 months ago, # ^ |   0 I don't get your test case.
•  » » » 11 months ago, # ^ |   0 Sorry, I fixed the problem
•  » » 11 months ago, # ^ |   +5 "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"
•  » » » 11 months ago, # ^ |   0 Thank you, I understood
 » 11 months ago, # |   0 Can we solve the problem Save Energy using Binary Search too?
 » 11 months ago, # | ← Rev. 2 →   0 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
•  » » 11 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   0 You mean the situation when m = 0, or what? That's a single one, so. Or you ment something else?
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » » 10 months ago, # ^ |   +3 Thanks!
 » 10 months ago, # |   0 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
•  » » 10 months ago, # ^ |   0 can you explain your approach?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 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".
•  » » » » 10 months ago, # ^ |   0 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 
•  » » » » » 10 months ago, # ^ |   0 I see, thanks a lot for the help!
 » 10 months ago, # | ← Rev. 2 →   0 Why does this solution in "Sleepy Game" gives TLE in test 20?Submission: 36210574
•  » » 10 months ago, # ^ |   0 I think your solution prints infinite number of nodes which causes TLE. Be careful with your print() function.
 » 10 months ago, # |   0 Solution to 936C is not clear from the editorial! Can anyone please explain a bit more in detail?
 » 10 months ago, # |   0 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.
 » 10 months ago, # |   0 niyaznigmatul can you show your code? (Div2 B);