Tutorial is loading...
Автор задачи: vintage_Vlad_Makeev
Tutorial is loading...
Автор задачи: GreenGrape
Tutorial is loading...
Автор задачи: dusja.ds
Tutorial is loading...
Авторы задачи: pashka и YakutovDmitriy
Tutorial is loading...
Авторы задачи: dusja.ds и VArtem
Tutorial is loading...
Авторы задачи: dusja.ds и burakov28
Tutorial is loading...
Автор задачи: budalnik
936B — Sleepy Game
verdict — WA on test 31
This 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 3
0
1 3
2 2 4
0
1
Correct output: Lose
hi there, i checked whether the source is disconnected, if so then Lose.but still WA on test 31. 35746464
Can you suggest me when to output Draw considering reverse graph? thank u
You have to make sure that there is a cycle in the graph reachable from s:
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.
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
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?
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......x
cba......x xcba......
xcba..y... ...yxcba..
...yxcba.. .....yxcba
So you can append this sequence to one side and invert the string, now just construct the string from the middle outwards and it's fine
1 2 3 4 5 6 7 8
try constructing
6 5
3 4 5 6
8 7 6 5 4 3
1 2 3 4 5 6 7 8
http://mirror.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.
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??
Div2 C / Div1 A Save Energy Problem Editorial ?? @Anyone
Imagine a state block that contains the two periods
0 -> k&0 -> xwherexis the smallest multiplier ofdthat is greater thank, that is0 < k < xmeaning that the oven is turned on for the period0 -> kand then becomes off for the periodk -> x, then again turned on forx -> x + kthen turned off forx + k -> 2*xand so on... now given a point in time saypcan 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
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 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 , so
k >= t1 and k < t2 ,also t2-t1 = d or t2= t1 + d
now 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
Dear niyaznigmatul,
Thanks for the informative tutorial. In 937B - Вредные кузнечики, it was sufficient to solve the problem by checking only the non-divisibility of some
oddhight less than or equal toydown top + 1by anyodd_primebetween3andq = min( N, p ), whereN = 31621is the largest odd number whose square is less than1e9. All the3400odd prime numbers between3andqwere initially computed usingsieve.35807290
Best wishes,
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?
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://mirror.codeforces.com/contest/937/submission/36052813
can you explain your approach?
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.
Expected :
I see, thanks a lot for the help!
Why does this solution in "Sleepy Game" gives TLE in test 20?
Submission: 36210574
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 atleastDraw. If there isn't any cycle and all the leaves vertices don't make Petya the winner, then answer isLose, 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.