niyaznigmatul's blog

By niyaznigmatul, 9 months ago, translation, In English,
Tutorial is loading...

Prepared by gritukan

Tutorial is loading...

Prepared by GreenGrape

Tutorial is loading...

Prepared by dusja.ds

Tutorial is loading...

Prepared by pashka and YakutovDmitry

Tutorial is loading...

Prepared by dusja.ds and VArtem

Tutorial is loading...

Prepared by dusja.ds and burakov28

Tutorial is loading...

Prepared by BudAlNik

 
 
 
 
  • Vote: I like it  
  • +89
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Test this:

    4 3
    0
    1 3
    2 2 4
    0
    1

    Correct output: Lose

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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
        
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

how to calculate time complexity of B(div2)?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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))

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Prime gap multiplied by for factorization.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you..I forgot to think about the prime gap..thanks

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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!

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              He was talking about maximal prime gaps

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think there must be more interesting (maybe more effective?) ways to solve Div 1 Pro C.Could anybody share his or her solution?

  • »
    »
    9 months ago, # ^ |
    Rev. 6   Vote: I like it +34 Vote: I do not like it

    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)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I like it. It's fairly simple. Thanks for sharing!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    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://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.

»
9 months ago, # |
  Vote: I like it -13 Vote: I do not like it

DIV B , C problem solutions please.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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)

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

editorial of 937C??

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
936A — Div1
//.....
if (k%d==0){
  cout << t;
return 0;
}
else {
period = (k/d)*d+d;
}
//.....and other
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Div2 C / Div1 A Save Energy Problem Editorial ?? @Anyone

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

»
9 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why "x = d — k%d" and "work done in one time interval = k + x/2 "? ...Could u explain details,pls QAQ

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 :)

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve the problem Save Energy using Binary Search too?

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your approach?

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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".

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
        
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I see, thanks a lot for the help!

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why does this solution in "Sleepy Game" gives TLE in test 20?

Submission: 36210574

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think your solution prints infinite number of nodes which causes TLE. Be careful with your print() function.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to 936C is not clear from the editorial! Can anyone please explain a bit more in detail?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

niyaznigmatul can you show your code? (Div2 B);