niyaznigmatul's blog

By niyaznigmatul, 6 years ago, translation, In English
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 budalnik

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

| Write comment?
»
6 years 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.

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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

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

how to calculate time complexity of B(div2)?

  • »
    »
    6 years 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))

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

    Prime gap multiplied by for factorization.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years 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?

      • »
        »
        »
        »
        6 years 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.

        • »
          »
          »
          »
          »
          6 years 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?

          • »
            »
            »
            »
            »
            »
            6 years 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.

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

              He was talking about maximal prime gaps

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  ohkk..Now I understand. Thank you very much.

»
6 years 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?

  • »
    »
    6 years 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)

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

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

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

DIV B , C problem solutions please.

»
6 years 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.

  • »
    »
    6 years 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)

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

editorial of 937C??

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years 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

»
6 years 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

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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 :)

      • »
        »
        »
        »
        6 years 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

»
6 years 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?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years 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

  • »
    »
    6 years 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.

»
6 years 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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your approach?

    • »
      »
      »
      6 years 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".

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

          I see, thanks a lot for the help!

»
6 years 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

»
6 years 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?

»
6 years 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem can we just find a max prime in range k+1 to n and print it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.