mainyutin's blog

Codeforces Round 938 (Div. 3) Editorial
By mainyutin, history, 3 weeks 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

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

Thanks for the editorial.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Too dumb to understand H

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Enjoyedd it as always ;)

→ Reply
»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks 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

    → Reply
    • »
      »
      »
      2 weeks 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".

      → Reply
»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anyone explain this swap preparation

→ Reply
  • »
    »
    3 weeks 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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does preparation mean in this context?

      → Reply
      • »
        »
        »
        »
        3 weeks 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.

        → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the editorial!

→ Reply
»
3 weeks 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?

→ Reply
  • »
    »
    3 weeks 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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So should we always use ordered map?

      → Reply
      • »
        »
        »
        »
        3 weeks 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.

        → Reply
  • »
    »
    3 weeks 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.

    → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you for fast editorial

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved the problem G with bfs?

→ Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did with same approach

    → Reply
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u elaborate how u come up with this formula

    → Reply
    • »
      »
      »
      3 weeks 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

      → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
      • »
        »
        »
        »
        3 weeks 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

        → Reply
    • »
      »
      »
      3 weeks 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)

      → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simpler maths https://mirror.codeforces.com/contest/1955/submission/256833759

    → Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 weeks 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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    yaa same doubt

    → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

F — Greedy Approach 255903652

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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 :-(

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why is BFS getting TLE for problem G ?

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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

→ Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
  • »
    »
    3 weeks 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
    → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
      • »
        »
        »
        »
        3 weeks 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

        → Reply
        • »
          »
          »
          »
          »
          3 weeks 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?

          → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please give me the reason for the TLE : https://mirror.codeforces.com/contest/1955/submission/255756069

→ Reply
  • »
    »
    3 weeks 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}$$$

    → Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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)

→ Reply
»
3 weeks 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.

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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)

→ Reply
  • »
    »
    3 weeks 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.

    → Reply
  • »
    »
    3 weeks 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.

    → Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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?)

→ Reply
  • »
    »
    3 weeks 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

    → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Towers are located on empty cells

    → Reply
»
3 weeks 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!

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Great News guys,got accepted already.

    What was wrong:
    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    which topic to study for solving this problem

    → Reply
    • »
      »
      »
      3 weeks 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.

      → Reply
»
3 weeks 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)

→ Reply
»
3 weeks 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

→ Reply
»
3 weeks 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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey anyone have solved Problem E using Segment Tree??

→ Reply
»
3 weeks 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 ;-;

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    vector erase is O(n)

    → Reply
    • »
      »
      »
      3 weeks 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

      → Reply
      • »
        »
        »
        »
        3 weeks 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

        → Reply
        • »
          »
          »
          »
          »
          3 weeks 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

          → Reply
»
3 weeks 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)

→ Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
    • »
      »
      »
      3 weeks 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?

      → Reply
      • »
        »
        »
        »
        3 weeks 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.

        → Reply
»
3 weeks 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.

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why vector on E solution??

→ Reply
»
3 weeks 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

→ Reply
»
3 weeks 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 ???

→ Reply
  • »
    »
    3 weeks 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..

    → Reply
»
3 weeks 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

→ Reply
»
3 weeks 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?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      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 computer by us would be 4 whereas the actual answer is 5.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D

My submission 256118405 is getting TLE. Need help.

→ Reply
»
3 weeks 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

→ Reply
  • »
    »
    3 weeks 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

    → Reply
»
3 weeks 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.

→ Reply
»
3 weeks 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.

→ Reply
»
2 weeks 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

→ Reply
»
2 weeks 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!

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Anyone used binary search for E?

→ Reply
»
2 weeks 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

→ Reply
»
2 weeks 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?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks 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

→ Reply
»
11 days 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

→ Reply
»
6 days 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 ?

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C without deque using 2 pointers — https://mirror.codeforces.com/contest/1955/submission/257982926

→ Reply
»
3 days 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);
    }
}

}

→ Reply