Please read the new rule regarding the restriction on the use of AI tools. ×

mainyutin's blog

By mainyutin, history, 6 months ago, translation, In English

1955A - Yogurt Sale

Idea: mainyutin, prepared: mainyutin

Tutorial
Solution

1955B - Progressive Square

Idea: ssor96, mainyutin, prepared: Vladosiya

Tutorial
Solution

1955C - Inhabitant of the Deep Sea

Idea: ssor96, Vladosiya, prepared: mainyutin

Tutorial
Solution

1955D - Inaccurate Subsequence Search

Idea: mainyutin, Vladosiya, prepared: mainyutin

Tutorial
Solution

1955E - Long Inversions

Idea: ssor96, prepared: Vladosiya

Tutorial
Solution

1955F - Unfair Game

Idea: mainyutin, prepared: mainyutin

Tutorial
Solution

1955G - GCD on a grid

Idea: ZergTricky, prepared: mainyutin

Tutorial
Solution

1955H - The Most Reckless Defense

Idea: vmanosin7, prepared: mainyutin

Tutorial
Solution
  • Vote: I like it
  • +92
  • Vote: I do not like it

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

Thanks for the editorial.

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

Too dumb to understand H

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

Enjoyedd it as always ;)

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

Hacks in problem G were especially too much in this contest Right?

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

    Sorry but I'm a newbie here. How it can be hacked? I do not see any using of hashing

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

      Newbie? Anyways, hacking is when someone finds a counter-example/test which the code fails to answer correctly, on time or exceeds memory limit. Basically, when someone hacks someone's solution/code which passed all tests with "Accepted", they find a testcase following the constraints, however returns wrong verdict when processed by the "solution".

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

Can anyone explain this swap preparation

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

    It often is a good idea to let someone else prepare the problem so that in case mistakes happen in terms of the correctness of the solutions, more people are aware of what is going on.

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

      What does preparation mean in this context?

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

        Create strong test data, alternative solutions and checkers/validators. In this contest, one validator was messed up but it was fixed later on.

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

Thank you for the editorial!

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

Can somebody please tell me why my submission for B 255683892 got TLE in system testing?

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

    Unordered map's worst case time complexity is $$$O(N^2)$$$ due to collisions. Use ordered map for the same.

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

      Thank you.

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

      So should we always use ordered map?

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

        A rule of thumb is to avoid using unordered map whenever you can.

        1. Verify if you can avoid the unordered map by using an array/matrix as a table to index the elements directly. If you can't use directly, sometimes you can normalize the values to make it possible. If the problem has multiple test cases, remember to analyze the complexity to clean up the table between the cases.

        2. If you can't use an array by any reason (memory, hard to code, complexity to clean/reuse...), analyze the worst case complexity with ordered map. If it's clearly enough to pass within the time, then use it. The complexity is more predictable and stable. There is no reason to exchange the "not so fast ordered map, but guaranteed AC" by a "MAYBE faster unordered map, but also MAYBE TLE" during the contest.

        3. If you really need/want to use the unordered map, keep in mind that the test cases can blow up the average unordered map solution, getting TLE sometimes. Hopefully, you can try to avoid this by making some changes in the hash function. You can read more about here: Blowing up unordered_map, and how to stop getting hacked on it

        EDIT: Changed the order and added some explanations.

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

    Just for TLE issue, there are two things you can do to make it run faster:

    1. cin / cout for large amount of data is slow, check here https://mirror.codeforces.com/blog/entry/6251 and use std::ios::sync_with_stdio(false); in your code. You can check samples of other user's submissions to see how they use this to speed up input efficiency.

    2. Don't dynamically allocate arrays in runtime as in int a[n*n], allocate a static array in advance, something like int a[510 * 510] at the beginning.

    I don't believe unordered_map is the issue.

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

      Thank you. But it seems like unordered_map was the issue because I submitted the same solution but with a map instead of an unordered_map and it got accepted.

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

Thank you for fast editorial

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

Is it rated?

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

Can anyone help me with this ? 255764657 getting TLE.. thanks a lot

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

Has anyone solved the problem G with bfs?

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

For C there’s an easier way to think of it: instead of one Kraken, we have two krakens attacking from both left and right, with the left one dealing $$$ceil(\frac{k}{2})$$$ damage and the right one dealing $$$floor(\frac{k}{2})$$$ damage. We can then simulate their attacks independently and count number of ships sunken afterwards.

Code: my solution

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

    yeah I did it with prefix and suffix and then binary search from both sides

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

    I did with same approach

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

Problem F has a simple $$$O(1)$$$ mathematical solution: 255716134.

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

    can u elaborate how u come up with this formula

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

      It can be simplified to $$$\sum_{i=1}^{4}\lfloor\frac{p_i}{2}\rfloor + (p_1,\ p_2\ and\ p_3\ are\ all\ odd)$$$. You just have to count states that have zero xor sum, which can be expressed as $$$\vec p = (p_1, p_2, p_3, p_4) = (2n_1, 2n_2, 2n_3, 2n_4) + (n_5, n_5, n_5, 0)$$$ where $$$n_i$$$ 's are arbitary integers

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

      Greedy, first consider $$$n_4$$$, the number of $$$(100)_2$$$, $$$n_4$$$ should be even to make xor = 0, after erasing all number expect $$$(100)_2$$$, the last $$$\lfloor n_4 / 2 \rfloor$$$ sequences have 0 xor.

      Then consider $$$n_1, n_2, n_3$$$, it is evident that $$$n_1, n_3$$$ and $$$n_2, n_3$$$ should have the same parity to make xor = 0. Then you need to try to achieve that by erasing some numbers as shown in the code.

      The optimal solution is: first make $$$n_4$$$ even, then make $$$n_1, n_3$$$ and $$$n_2, n_3$$$ have the same parity, thus one zero-xor is obtained for every two erasing.

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

        Furthermore, ans=\sum_{i=0}^{4}\left\lfloor\frac{p_i}{2}\right\rfloor+\sum_{i=0}^{3}\left(p_i&1\right) 255945388

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

      I come up with similar formula base on the fact that: 1. The result of two XOR elements is 0 if and only if the two elements are equal; 2. The result of three XOR elements is 0 if and only if they are exactly (1, 2, 3); 3. The result of more than three XOR elements is 0 if and only if it can be divided into the sum of the several pairs and triple above. Finally, add a little greedy thought)

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

Could someone explain why BFS TLEs with same logic for G?

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

For problem E, I wonder if there exists some other method to choose&reverse which is better? Or, why always choosing&reversing the first zero from left to right(or right to left) can examine whether a 01-string can be converted to all-1-string. Is there any provements? Thanks a lot.

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

    yaa same doubt

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

      i though something just now, lets take 110.... for example. so now since leftmost one is part of just 1 segment we cant do any operation on this, come to next 1, so due to previous segment there is no change on this 1 and segment starting from this 1 itself is the last one involving this 1 so cant do any operation again, now next 0, so previous segments have no effect. Segment starting from this element is the last one involving it so we have to do operation, no choice and then so on, we will have to take into consideration the operation applied on this zero for next k-1 elements.

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

F — Greedy Approach 255903652

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

What is the rate of problem E could it be below 1400 ?

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

    $$$clist$$$ gives an approximate rate around $$$1600$$$

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

This contest really was not made for python users, most of the solutions were giving tle for python answers and not for the exact same cpp solution

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

    Agreed, I don't know why even simple C problem givign me TLE :-(

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

why is BFS getting TLE for problem G ?

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

    nvm i got it to work

    Declaring all variables as static seems to be a solution . Especially visited and the input 2Darray

    code : 255917745

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

Why I am getting TLE in E? Please help Submission link: 255910548

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

what is the time complexity of this code?? I am. confused about how many factors will be there in a particular state dp[i][j] ?? 255662591

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

    In state dp[i][j] there are only factors which is not divisible by any other factor. The number is hard to calculate

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

Hi, I try to use the logic of dijktra algorithm on porblem G. GCD on a grid.

But, I get wrong answer 2136th numbers differ - expected: '8', found: '4'

I can't figure out the bug: 255917561

Please, help

Thanks

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

    if (-gcds[next_row][next_col]>-next_gcd){ gcds[next_row][next_col]=next_gcd; q.push({gcds[next_row][next_col],{next_row,next_col}}); }

    --> this line is problem like you are ignoring a possible gcd value which cal help you to have transition

    given--> a[i][j] = 6, a[i][j + 1] = 12 but you can do a[i][j] = 10 if you ignore 6 you will get wrong answer

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

    Try this:

    2 5
    6 3 6 3 6
    2 6 6 6 2
    
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      2 5
      6 3 6 3 6
      2 6 6 6 2
      

      max path

      My code output is 2, too.

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

        Okay, so you are doing anti-Dijkstra.

        Then this:

        1
        2 5
        1120 14 14 8 3
        16 08 28 8 8
        

        prints 2, while there is path with 4

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

          Thanks vstiff, I really appreciate

          I think the anti-Dijkstra works, the push into the queue should be outside the if statement, but I get MLE.

          if (-gcds[next_row][next_col]>-next_gcd){
              gcds[next_row][next_col]=next_gcd;
          }
          q.push({next_gcd,{next_row,next_col}});
          

          256041649

          Is there a way to fix it?

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

    Creating vectors of size $$$10^6$$$ in $$$10^4$$$ test cases.

    $$$10^6 * 10^4 = 10^{10}$$$

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

Why O(N) solution of problem D is giving TLE in python? 255903393

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

    i don't know the full reason but somehow storing strings instead of integers in a dict reduces time ( may be something related to hashing inside a default dict ig) same happened to me i tried just changing int to str dtype in lists of a and b it got accepted. your code's modified submission

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

I dont understand why A* and DFS (with early stopping) give TLE for G. Surely the number of nodes visited is similar to that in the tutorial (effectively doing a search from start to end for each divisor of g)

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

Can someone explain to me how the third example of question F works? I think the answer is 4.

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

    Why do you think the answer is 4? The best case scenario is having the same ones adjacent: 1 1 2 2 3 3

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

how to prove the num of divisor of N is N^(1/3)

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

    Not exactly what the tutorial said, but you can have a look at the function's growth rate.

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

    I don't think so they are trying to say that the number of divisors is N^(1/3), but they are trying to say that the number of divisors is not greater than that. Although for the past 15 mins I was also wondering how is the possible and where is the proof. If someone can explain me in simple terms I would be very thankful.

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

    There were problems about finding the numbers with maximal number of divisors till N, they solved through the backtracking typo generate p_{1}^q_{1}*p_{2}^q_{2}*...*p_{k}*q_{k}, where p_{i} is the i-th smallest number, and the number of divisors is a product of q_{i}+1

    So in generation the most non-trivial thing is to find out that q_{i-1} >= q_{i} because if several numbers with equal number of divisors we are interested in smallest ones, by it you can find that number with maximal number of divisors till 10^9 has 1344 divisors, and till 10^18 has ~1.03e5 divisors, but estimation is clearly rough because 1344 > 1e3

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

Can the twoer located in the enemie's path in the problem H? If it is posiible, why the solution of dp is right?(just one tower has the range of 0?)

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

    By default, all towers have a zero range, but the player can set a tower's range to an integer r (r>0), in which case the health of all enemies will increase by 3r. However, each r can only be used for at most one tower.

    it is mentioned r>0

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

      I know that, but when I use dp, in the final answer, no more than one tower will have the radius of 0. However, when some towers located in the enemy's path, as the promblem says(0 is default), those towers will damage the enemy with zero radius. It seems that the dp can not count this part of damage. Because my dp is weak, I want to konw that whether I misunderstand the problem or the dp can count all zero part in fact.

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

    Towers are located on empty cells

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

Hi guys currently stuck on problem H can't find the problem for this code(wa on test 4). Can anyone help me take a look? Thanks in advance!

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

    Great News guys,got accepted already.

    What was wrong:
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    which topic to study for solving this problem

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

      If we're only talking about "TOPICS" then this is a pretty standard bitmask DP problem. However, There's an important observation that the maximum radius of a tower doesn't exceed 12, which LEADS to the method of bitmaskDP.

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

I think in the tutorial of problem F the transition should be dp[i][j][k] =max(dp[i−1][j][k],dp[i][j−1][k],dp[i][j][k−1])+x(i,j,k)

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

For G, why is the number of divisor the cube root of A

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

Problem G can be solved using brute force: store the list of gcds at each element and choose the maximum element at point (m,n) https://mirror.codeforces.com/contest/1955/submission/255975752

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

Hey anyone have solved Problem E using Segment Tree??

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

256004789

can someone please explain why am I getting time limit exceeding on test 3? in question C. Inhabitant of the Deep Sea and also tell where I went wrong please ;-;

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

    vector erase is O(n)

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

      could please you tell what I can do instead of erase? and also how I can avoid mistakes like these so that I won't make them during the contests

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

        Because you're only erasing the first and last element, a deque is a perfect ds for that, replace erase with pop_front().

        BTW your solution is also not working, k is 1e15 so obv it will get TLE

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

          ooh my bad silly mistake

          and I did not use deque cause I have not familiarized myself with deques. Thanks I will look into it :> 256015838

          it's still not working is my logic wrong? sorry for so many questions

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

very easy code for F 256008944

if both cnt[1] and cnt[2] are odds, just think them as one for cnt[3]

(01 XOR 10 = 11)

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

Can someone explain to me why my code for G, in which I use DP having a complexity of O(m.n.n) is not working. What I am doing is, I stored dp[i][j] as max gcd from (i,j) to (n,m).

For this, I update the dp as follows:

dp[i][j] = max(dp[i][j], gcd("gcd from (i,j) to (k,j)",dp[k][j+1]))

dp[i][j] = max(dp[i][j], gcd("gcd from (i,j) to (k,j)",dp[k+1][j]))

here is the code https://mirror.codeforces.com/contest/1955/submission/256013095

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

    It's my first approach in the problem but found an easy counterexample for it

    2 3 
    6 2 1
    3 6 4
    

    here ,by maximum $$$GCD$$$ logic, it will outputs $$$1$$$.

    (Since dp[2][2] = max(dp[1][2] = 2, dp[2][1] = 3) = 3 and dp[2][3] = max(1,1) = 1 )

    However, the correct answer here is $$$2$$$ by considering the $$$path$$$

    $$$(1,1)=>(1,2)=>(2,2)=>(2,3)$$$

    P.S:

    The above example is correct in you code, since you start from end

    consider the inverted version of the same example

    2 3
    4 6 3
    1 2 6
    

    your code outputs $$$1$$$, but answer is $$$2$$$ by the same $$$path$$$ described above

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

      Ohhh ok got it. Thanks. How do I know if a DP approach won't work in a program like any tips?

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

        Well, make sure the solution checks all the possibilities. It's convenient to try on small cases first and try to validate your solution on them.

        When you validate your logic, write the slow solution for transition and try to optimize until it fits the time limit.

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

Can anyone help me figure out why my solution to C got TLE? Seems O(n) to me.

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

    your code is O(k), dont subtract a[i] by 1 at a time, you can subtract it by batch

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

https://mirror.codeforces.com/contest/1955/submission/256034339 can anyone give test case which will fail my code

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

why vector on E solution??

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

In question G we don't have to iterate through all divisors of g
We can maintain a list of factors
In each loop:
- Choose a search candidate in the list
- If exists a path, discard all values smaller than the candidate
- If not exists a path, discard all values which is multiplier of the candidate
https://mirror.codeforces.com/contest/1955/submission/256059578

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

For problem H, isnt that the enemy only visit certain cells in path, but cover() considers all cells in the range of radius R, right ???

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

    I forgot the fact that enemies will pass thorugh all # cells, i wias thinking in direction where enemies only pass through some # cells, and compilcated my problem..

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

    Thus, the maximum radius for the tower can be found from the inequality $$$500⋅π⋅r^2−3^r>0$$$, assuming that the tower has a damage of pi=500. This estimate gives R=12

    Could you explain how come the Maximum radius is just 12?

    Inequality should be $$$500\times$$$(# of cells)$$$-3^r>0$$$ => $$$500\times (50\times 50-1)-3^r > 0$$$ which gives $$$r=107$$$ right?

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

Can anyone tell why recursion is giving TLE for G? Even if I put this condition that dp[i][j]==true and visited[i][j]==true, return true it still gives tle This

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

Can someone help for the line below:

cout << ans + (dq.size() && dq.front() <= k) << '\n';

What does the (dq.size() && dq.front() <= k) do? What value does it add to ans?

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

    It’s for handling the last remaining element in the deque.

    Dry run the following test case for better clarity:
    5 9
    1 2 3 2 1

    If we didn’t had that line, answer computed by us would be 4 whereas the actual answer is 5.

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

Problem D

My submission 256118405 is getting TLE. Need help.

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

why in the problem G the dp[i][j] = max(__gcd(dp[i][j+1] , curr_num) , __gcd(dp[i+1][j],curr_num))

doesnt work any test case

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

    It seems like you are moving from bottom rightmost cell to top leftmost cell. So your answer would be dp[0][0]

    This is a greedy strategy which will fail for the following test case:
    2 4 11
    2 14 7
    3 2 14

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

I couldn't solve it in contest, but I have queue implementation for problem E in $$$O(nk)$$$ if anyone want an example. https://mirror.codeforces.com/contest/1955/submission/256137527

Same idea, bruteforce for $$$k = n..1$$$ then simulate the flipping. Idea is to maintain the last k indices in $$$[i-k... i-1]$$$ which need to be flipped. The size of this list is same as how many times $$$bit[i]$$$ will be flipped before it. So we'll push $$$i$$$ to queue whenever $$$(bit[i] + size \,\,of \,\, queue) \,\, \% \,\, 2$$$ is $$$0$$$. If there is nothing need to be flipped at the end (queue is empty), then it means $$$k$$$ is possible.

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

Does there exist any solution to problem G using some modification to dijkstra?

I tried submitting a similar approach to dijkstra but it got TLE (on test case 31) because unlike dijkstra, we can't greedily choose the best path with largest gcd for a given vertex and ignore other bad paths with less gcd for that vertex because those bad paths with less gcd further might become good paths. Here's the submission.

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

Millions of people around the world are waiting so kindly stop your personal discussions and focus on others

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

EMJB with kindness offered help and you keep them waiting? Focus on others now!

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

Anyone used binary search for E?

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

Can someone explain me why this submission255752599 is giving WA for TEST-CASE 4 in C

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

In problem G, why does code with 2d arrays for dp work (256666729) and with 2d vectors (256170691) doesn't?

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

A simple mathematical O(1) solution of F: 256693662

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

Damn, prob G we can check divisor of gcd(a11, anm) and check by dfs O(n * m * sqrt(MaxAij)). Enough to AC

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

I want to share an alternative solution for H, which can be solved nicely with a "by-the-book" MCMF implementation:

The key observation is indeed that there are not that many ranges feasible (at most 12). But the fact that two towers can't use the same range may point out the need for a matching kind of approach.

Further, as some choices bring cost (powers of 3) and some are reducing costs (more tiles being covered), then the problem can be modelled as flow graph with:

  • one source
  • K nodes representing the towers (linked to the source, with capacity 1 and no cost)
  • 12 nodes representing the powers of 3 (linked to the towers accordingly, with capacity 1 and the negative cost based on the power of the tower multiplied with the covered tiles using a specific radius)
  • one special node representing that we don't use a power of 3 (i.e. radius 0, linked to each tower, with capacity 1 and no cost)
  • a sink node connected to the powers of 3 (with the cost being the power of 3 and capacity 1) and to the special node (with no cost and an arbitrary large capacity)

Apply MCMF (min-cost, max-flow) algorithm and the answer is the cost straight-away.

https://mirror.codeforces.com/contest/1955/submission/257223979

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

i don't understand the solution of Question F

mine look so simple and faster

any explain for editorial solution of Question F ?

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

import java.util.*; import java.lang.*; import java.io.*;

public class Main { public static void main (String[] args) throws java.lang.Exception { // your code goes here Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0){ int n = sc.nextInt(); int m = sc.nextInt(); int x = sc.nextInt(); int[] a = new int[n]; Map<Integer,Integer> b = new HashMap<>(); for(int i=0;i<n;i++){ a[i] = sc.nextInt(); }

for(int i=0;i<m;i++){
            int k = sc.nextInt();
            b.put(k,b.getOrDefault(k,0)+1);
        }

        int i = 0;
        Map<Integer,Integer> window = new HashMap<>();
        int res = 0,c = 0;
        while(i<m){
            int k = a[i];
            window.put(k,window.getOrDefault(k,0)+1);
            if(b.containsKey(k) && window.get(k)>=0 && window.get(k)<=b.get(k)){
                c++;
            }
            i++;
        }
        if(c>=x)res++;
        while(i<n){
            int f = a[i];
            int l = a[i-m];
            window.put(l,window.getOrDefault(l,0)-1);
            if(b.containsKey(l) && window.get(l)>=0 && window.get(l)<b.get(l)){
                c--;
            }
            window.put(f,window.getOrDefault(f,0)+1);
            if(b.containsKey(f) && window.get(f)>=0 && window.get(f)<=b.get(f)){
                c++;
            }
            if(c>=x)res++;
            i++;
        }
        System.out.println(res);
    }
}

}

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

Can someone elaborate why G has a time complexity of O(n*m*cubic_root(A))? I think it's O(n*m*sqrt(A)).

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

    Number of divisors for any $$$n$$$ are $$$O(n^{1/3})$$$.

    You can check here.

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

B

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

Can anyone tell why the following code for the problem G ~~~~~ Your code here... ~~~~~

1955G - GCD on a grid gives wrong answer 259895161

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

    The solution and the idea is wrong, you don't take gcd with dp values you take gcd of path (i.e the values given in the grid). Here you are taking $$$dp[i][j]$$$ = $$$max(dp[i][j], gcd(dp[i-1][j]/dp[i][j-1], a[i][j]))$$$ in this $$$dp[i-1][j]/dp[i][j-1]$$$ is storing max values instead of $$$(a[i-1][j] / a[i][j-1])$$$ you are taking gcd of max value and current value instead of $$$gcd(a[i-1][j]/a[i][j-1], a[i][j])$$$ which is wrong.

    Hint for correct solution:

    Hint-1

    Hint-2

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

D have a little strange

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

Thanks for the editorial.

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

Hey, can anyone please help me understand why this submission 262094929 got TLE at tc35?

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

    hey did you understand the reason of TLE , I had same doubt

    263251053

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

      Vector initialization takes more time than creating a constant size array, so either create an array everytime. Or create a dp vector once, and then inside the for loop, reset it each time. This had solved the tle for me in my code.

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

        Solved for me as well for the same reason ,Thankyou!

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

I wonder why my O( n log n) solution got TLE in the 'D' problem. Submission: 264661140

In the editorial, it's also written that the O( n log n) solution will work.

Can anyone tell me why it's happening? What's wrong in my code?

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

FOR F .why its name is unfair game

ll ans=0; vll p(4); forl(i,0,4)cin>>p[i]; ans+=p[3]/2; if(p[0]%2&&p[1]%2&&p[2]%2){ans++;} ans+=p[0]/2; ans+=p[1]/2; ans+=p[2]/2; cout<<ans<<endl;

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

can someone explain me this part from problem C :-

if (k < 2 * mn) { dq.front() -= k / 2 + k % 2; dq.back() -= k / 2; k = 0; }