GlebsHP's blog

Nebius Welcome Round Editorial
By GlebsHP, history, 21 month(s) ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +293
  • Vote: I do not like it

Comments Comments (106)
| Write comment?
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Very fast editorial! Thanks!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +105 Vote: I do not like it

I was too scared that $$$O(2^n \cdot n^2)$$$ is too slow for E so I ended up figuring it out in $$$O(2^n \cdot n)$$$ with $$$O(2^n)$$$ memory.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Could you explain this solution?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +78 Vote: I do not like it

      For each subset $$$msk$$$, compute $$$dp[msk]$$$ as the possible last vertices $$$v$$$ of simple chains starting at $$$u$$$ and ending at $$$v$$$ (where $$$u$$$ is the minimum vertex in $$$msk$$$). Use bitwise operations to check for a given $$$msk$$$ all the new vertices $$$v'$$$ that can be added (condition is $$$graph[v'] \cap dp[msk] \neq \emptyset$$$).

      Code: https://codeforces.net/contest/1804/submission/197139926

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +49 Vote: I do not like it

Can't solve D :(

How to improve solving greed problems

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    It's not a greed problem!

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      It is. At least my solution is

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Hmm, it looks like it is. I had easier solving it with DP lol.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          how was ur dp

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Can you please explain your DP solution?

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it -55 Vote: I do not like it

            Nah

            → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Maximizing $$$T_2$$$ is easy, so the only problem is to minimize it. $$$T_0 + T_1 + T_2 = \frac{m}{4}$$$, so instead of minimizing $$$T_2$$$ you can maximize $$$T_0 + T_1$$$. You can do it by calculating $$$dp_i = \max T_0 + T_1$$$ on prefix $$$i$$$. Transitions are easy, I'm sure you can figure them out.

            → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +38 Vote: I do not like it

          Your solution is essentially greedy without you noticing it

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            During the contest, I only realized that I need to maximize certain 2-sized flats without realizing that taking the one with minimal index always works.

            → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    tags: greedy Ratings: 1700+ Should work

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Damn! Editorials are out even before the system test. Coolest round ever!(for me)

→ Reply
»
21 month(s) ago, # |
← Rev. 5   Vote: I like it -6 Vote: I do not like it

Why my approach to problem C is wrong?

We need for every $$$1 \le f \le p$$$ to check if:

$$$ \begin{aligned} x + \sum_{i = 1}^{f} i &\equiv 0 \mod n \\ x + \frac{f (f + 1)}2 &\equiv 0 \mod n \\ f ^ 2 + f &\equiv -2x \mod n \end{aligned} $$$

We end up checking the value of $$$f ^ 2 + f$$$ (mod $$$n$$$), which is equivalent to checking $$$m ^ 2 + m$$$ whereas $$$m \equiv f \mod n$$$.

From the previous reasoning, it is enough to check all possible values, $$$1 \le f \le \min(p, n)$$$.

The vague part is going from $$$f$$$ to $$$m$$$. Why isn't it correct?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    You can't multiply by 2 so you have to go up to min(p, 2n) not min(p, n)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      To be accurate, if $$$n$$$ is odd, $$$2$$$ is invertible $$$\mod n$$$ so you can multiply by $$$2$$$ and check only up to $$$n$$$ when it is odd.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain why exactly I can't multiply by 2?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 4   Vote: I like it +19 Vote: I do not like it

        This is because you want "$$$\iff$$$" (**if and only if**). Therefore, you need to be abble to multiply by $$$2$$$ (always works) but you also need to divide by $$$2$$$ (only works if $$$n$$$ is odd).

        1) Multiplication by $$$2$$$ (always works)

        Let $$$f \in \mathbb{Z}$$$ (an integer) and assume that $$$x + \dfrac{f(f + 1)}{2} = 0 \mod n$$$.

        This means that $$$x + \dfrac{f(f + 1)}{2} = \lambda n$$$ for some $$$\lambda \in \mathbb{Z}$$$.

        Therefore $$$2x + f(f + 1) = 2 \lambda n$$$.

        Since $$$2 \lambda \in \mathbb{Z}$$$, $$$2x + f(f + 1) = 0 \mod n$$$.

        2) Division by $$$2$$$ (only works if $$$n$$$ is odd)

        Now, let's assume that $$$2x + f(f + 1) = 0 \mod n$$$. Can we say that $$$x + \dfrac{f(f + 1)}{2} = 0 \mod n$$$?

        2.a) Assume $$$n$$$ is odd

        Then $$$\dfrac{n + 1}{2}$$$ is an integer.

        Thus, $$$\dfrac{n + 1}{2} (2x + f(f + 1)) = 0 \mod n$$$.

        By simplifying, and since $$$\dfrac{f(f + 1)}{2}$$$ is an integer, you do obtain $$$x + \dfrac{f(f + 1)}{2} = 0 \mod n$$$.

        2.b) Assume $$$n$$$ is even

        Then $$$\dfrac{n + 1}{2}$$$ is not an integer so the above trick does not work.

        What we would like to do is to deduce that $$$y = 0 \mod n$$$ from the fact that $$$2 y = 0 \mod n$$$.

        However, remember that $$$n$$$ is even so $$$n = 2m$$$ for some $$$m$$$ in $$$\mathbb{Z}$$$. Taking $$$y = m$$$, $$$2 y = 0 \mod n$$$ but $$$y \neq 0 \mod n$$$.

        Therefore, you cannot assume that $$$x + \dfrac{f(f + 1)}{2} = 0 \mod n$$$ if you only know that $$$2x + f(f + 1) = 0 \mod n$$$.

        EDIT: I missclicked on post instead of preview, I'm going to finish writing my message. xD EDIT 2: I finished my message.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I believe you have to check f up to min(p, 2n). I got the same equation as you, but I found out 2n is needed after trying out a few examples. I'd be happy to learn why 2n is needed. EDIT: See Beaboss's comment.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

You're given 3 problems and two hours to solve them

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

I have trouble understanding the additional question at the end of the tutorial for problem c:

"Question, can you build the test that required Vesper to use $$$x$$$ more than $$$100k$$$?"

Can somebody explain the question please? (not the solution though, I wanna solve it ^^')

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess it’s asking you to find a case (i.e. find a $$$n$$$) for which only a $$$x > 10^5$$$ could make the answer “Yes” for an enough large $$$p$$$.

    Formally, find $$$(n, x, p)$$$ ($$$x > 10^5$$$) which would result “Yes” while would result “No” for any $$$x \le 10^5$$$.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But x<n and n<=10^5 so constraints clearly say that x can't exceed 100k limit so how is it possible for x to be more than 100k

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, then it might be $$$f$$$ instead of $$$x$$$.

        Find (n, x) that requires a f $$$> 10^5$$$ to make (x + f(f+1)/2) % n == 0

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes you got the right interpretation, thanks.

          There is indeed only one tuple $$$x, n$$$ with $$$0 \leqslant x \leqslant n - 1$$$ and $$$n \leqslant 100,000$$$ such that you can indeed reach $$$0$$$ starting from $$$x$$$ for some $$$f > 100,000$$$ such that you cannot do it for any $$$f \leqslant 100,000$$$.

          → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

why it will be tle ? i only use upper_bound get AC 197098569

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Delete the vector re from your code. Its size is big and it gets initialized for each test case.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

it is logically very obvious that

 (2n*(2n+1)/2)%n=0

So, logically it is obvious that if we try out values from 1 to 2*n and do not get answer then we would not get answer after that too. But can anyone prove it mathematically though? Still cannot convince myself about the 2*n thing.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The sum up to $$$f$$$ is the same as the sum up to $$$f + 2n$$$ ($$$\mod n$$$).

    $$$\dfrac{(f + 2n)(f + 2n + 1)}{2} = \dfrac{f (f + 1)}{2} + f n + n (f + 1) + n (2n + 1)$$$
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do we try adding 2n to f by just intuition or their is something behind that?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is indeed something behing it (although the fact that $$$2n$$$ is going to work feels intuitive as well).

        By going back to the definition of $$$x = y \mod n$$$ (that is $$$x = y \mod n \iff \exists \lambda \in \mathbb{Z}, x = y + \lambda n$$$), you can prove that $$$x$$$ is a solution to $$$\dfrac{x}{a} = b \mod n$$$ if, and only if, $$$x$$$ is a solution to $$$x = ab \mod an$$$ (assuming that $$$x$$$ can be divided by $$$a$$$).

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Because $$$x + i(i+1)/2 \equiv x + (i+2n)(i+2n+1)/2$$$ ($$$mod$$$ $$$n$$$), the value of $$$x + i(i+1)/2$$$ $$$mod$$$ $$$n$$$ will repeat itself after $$$2n,$$$ so we only need to check from $$$1$$$ to $$$2n$$$ which is good enough

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but why it didn't give tle when p reaches 2*n under 10^4 testcases as n=10^5

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Because the sum of $$$n$$$ cannot be bigger than $$$2*10^5$$$

        → Reply
»
21 month(s) ago, # |
  Vote: I like it -18 Vote: I do not like it

Why is my submission failing for B

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Easiest div2 d I've ever seen, I wish I registered for the contest

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think in task F you have used about 150 cpu-days

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this giving the wrong answer for the maximum value in problem D?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

:( Came home 1 hour late so couldn't join. Sad thing is I knew how to solve F because I did it in an approximation algorithms course before.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +159 Vote: I do not like it

F actually highlights something that is missing from Polygon (or maybe some online judges in general): the ability to declare that "this is the correct output file" without having it be generated by the model solution. In contrast, CMS (e.g. at IOI) treats the output files as the true ones and doesn't care if you didn't generate them using the model solution.

This is a niche usage of course, but it would be nice to give approximation problems without hacks like "the last line is an encoded version of the true answer". Approximation algorithms aren't really the CP meta right now, but e.g. for one task in an ICPC-style contest, why not? Compute the correct answers using some slow brute force or a commercial ILP/SAT solver and the checker can just check the approximation factor.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can implement an approximation problem on Polygon using an interactor instead of exposing an encoded answer.

    • The test case file contains the actual input to the problem and also the real answer.
    • Interactor reads the test case file and only shows the actual input to the program. Then it compares the program's answer to the test case's answer.

    For this specific problem F it wouldn't allow for hacks because it's hard to implement a validator that checks we have the exact answer. However this method would allow hacks for many approximation problems such as minimum vertex cover.

    The problem could be "Given a graph, find a vertex cover that is at most twice the size of the minimum vertex cover." In this case we don't need a strict requirement that we have the optimal vertex cover in the test case, just some vertex cover. Then someone would be able to hack an incorrect program as long as they can find a vertex cover that is less than half the size of the program's answer.

    → Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it -6 Vote: I do not like it

Randomised solution for E:

DFS going deep for 2 random child every time. If you get loop — check if union of neighbours in it covers everything. If it does, then we found required loop in editorial. Repeat until you have spent almost 2 seconds. Print "No" otherwise. Not sure how to estimate probabilty of failure though.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

Btw, fun fact about problem F.

There is a paper that proves that under SETH it is impossible to solve problem F in $$$O(m^{1-\varepsilon})$$$ time per query if we would need to answer queries online, there were also edge deletions, and we had to provide a $$$2-\delta$$$ approximation (here $$$f$$$-factor approximation means that we should provide an answer that is not smaller than the actual answer and at most $$$f$$$ times larger; I am not sure whether this theorem can be generalized to the notion of approximation that is used in problem F).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem D it should be $$$T2=max(0,m4−∑yi=0⌊l′i2⌋)$$$ not $$$T2=min(0,m4−∑yi=0⌊l′i2⌋)$$$

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

The system test of E is weak. My brute force solution (with special check for cut-edges) passed it.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +41 Vote: I do not like it

By the way, there is another solution for F.

Instead of running a binary search, you can just start bfs with updated vertexes and existing distances, not from scratch. This is too slow, but we can not run bfs each time, but only when sum of immediate increases (differences between end and start of added edges -1) is half of the current answer.

This is correct because this sum is the upper bound of the answer decrease.

The more tricky question why it is fast.

  1. After distance is less than $$$O(\sqrt(n))$$$, it is $$$O(nsqrt(n))$$$ even if we run bfs each time
  2. While difference is big, each edge is decreasing distance by at least factor 3/4 for at least $$$O(\sqrt(n))$$$ vertices.

This looks like very rough bound, probably in practice it's better.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please provide more detail as to why 2. is true?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hm. I was quite sure about it during the contest, but not really sure now.

      But I think it's still subquadratic. Idea is following. If we have a big shortcut (order of answer), then at least for second half of the vertices on the old shortest past to further end of shortcut, distance decreased significantly. Now we can say, that we either processed a lot of queries, or at least one of them is big.

      It seams it can lead to $$$N^{7/4}$$$ or $$$N^{5/3}$$$ bound. I'm not sure.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I am a bit confused by what you call "sum of immediate increases".

    For instance, let's say I start the bfs from vertex $$$A$$$ and et's say I have two vertices $$$B$$$ and $$$C$$$ such $$$dist(A,B) = 42$$$ and $$$dist(A,C) = 50$$$. If I add the edge $$$(B, C)$$$, would the "immediate increase" be $$$50 - 42 = 8$$$?

    Also, when you say "this sum is the upper bound of the answer decrease", do you mean that the sum is an upper bound of the decrease of the diameter of the graph when adding the edge $$$(B, C)$$$?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the specific test in C? (last sentence in editorial)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    65536 0 131071

    Did not expect to see a power of 2 tbh. Seems all n = 2^k with x = 0 will need 2*n - 1

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem C has a brilliant name. No thinking, just pull your luck ))

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem C, I was shocked. I write AC code but I thought it was WA. Because I thought the loop needed p time every test case. if I loop run P time then I got TLE. That's why I didn't submit my code. but after finishing the contest I submit my code and it was an AC code.


void solve()
{
    ll n, x, p;
    cin >> n >> x >> p;

    ll rem = n - x, sum = 0;
    if( x == 0 ) rem = 0;
    vector< int > v;
    for( ll i =  1 ; i <= n * 2 ; i++ )
    {
        
        sum += i; 

        if( sum % n == rem )
        {
            cout << "YES" <<  endl;
            return;
        } 
        if( i == p) break;
    } 
    cout << "NO" << endl;
}
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    because of this

    It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅10^5

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +48 Vote: I do not like it

Bonus question, can you guess the total number of cpu-days we have used to compute all the answers? Post you version in the comments!

To find the diameter of a general graph, we will need $$$n$$$ BFS, and each takes $$$O(n+m)$$$ time, overall $$$O(n*(n+m))$$$ per query. $$$O(n*q*(n+m+q))$$$ per testcase.

This problem has 80 testcases, assuming worst case $$$n=m=q=10^5$$$, its $$$80*10^5*10^5*(3*10^5) = 2.4*10^{17}$$$, assuming $$$10^8$$$ operations per second, on the normal computer we need $$$2.4*10^9$$$ seconds = ~3e5 days.

I was expecting the answer for generating testcases to be < 100s, using 1e5 parallel cpus.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +206 Vote: I do not like it

    Both authors retired from CF in 2017, guess that's because they have been busy generating the test cases ever since...

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    I think there are better algorithms / heuristics to enormously speed up the brute force. For example: If you add an edge, for the current diameter, you run BFS from one of the endpoints and if the edge addition doesn't improve the diameter, you don't need to calculate anything at this step of the algorithm anymore.

    Also, things like keeping some upperbounds of diameters ending in nodes, and not running a BFS if isn't strictly needed. Maybe not worstcase complexity improvements but they will speed up the brute force a whole lot.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 6   Vote: I like it +36 Vote: I do not like it

      I have a solution that works in $$$O(nm + q(n + m + q))$$$ for all tests except special ones.

      The idea is very simple, at the very beginning we calculate the furthest distance from each vertex with $$$n$$$ BFSs and call this value upper bound.

      Now, after adding the next edge, we go through the vertices in descending order of upper bound and recalculate the furthest vertex from them. If it has not changed, this upper bound is the answer after adding edge.

      But unfortunately, it's still not fast enough and an additional hack is needed. And this hack is simple — in addition to recalculating the farthest vertex, let's update the upper bound of other vertices $$$u$$$ as "max distance from current vertex" + "distance from the current vertex to $$$u$$$".

      This is already enough to pass all the tests except for special ones, which are essentially built against such solution (at the moment, my solution can generate an answer to every test except two special in an hour).

      But it was not used as a model solution, but was rather a validator for validating the simplest distributed algorithm.

      Сode snippet for better understanding
      → Reply
»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

Bonus question, can you guess the total number of cpu-days we have used to compute all the answers? Post you version in the comments!

7

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A using DFS?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it might time out, but you can keep the track of the path you have traveled, once you reach the destination you can compute the cost of that path.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there a ")" missing here for D?

and isn't max?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for fast editorial

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my solution got TLE even if it is O(nlogn).

My Solution: https://codeforces.net/contest/1804/submission/197105822 Can someone help me, please?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: There's one line wrong, causing you to get stuck in an infinite loop

    Spoiler
    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain why we are counting "at least one dark window segment" in problem D rather than one dark window segment .

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, in last line, I think it should be max not min.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +42 Vote: I do not like it

F is a beautiful problem with a very scary statement

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

cool way to get the correct answers in cool problem F

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +55 Vote: I do not like it

Problem E: I was blown by the idea of using the first set bit to represent start of the circle. Very clever.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D, my approach for finding the maximum value is to, first calculate "01" or "10", then "00" and at last "11", and assign this as two widowed rooms, and the remaining ones are single windowed. Can anyone point out my mistake? submission

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What I do in C is, I run a loop from i = 1 to 1e5 and checking if i*n-x exist as sum of p natural number in logP overall time complexity is O(n*logP) but still it got TLE Why?

https://codeforces.net/contest/1804/submission/197293170

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that you only loop from 1 to 1e4,so it would goes wrong when n is large enough.

    If the answer is No,it will run the loop completely,and your function f is $$$O(\log p)$$$,so the total is $$$t\times 10^4\times \log p=3\times 10^9$$$ and it goes tle.At least you should replace 1e4 with n*2.

    BTW,I'm not sure whether it's right or not to use binary search.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

I have received a mail that my solution of C problem in Nebius Welcome Round is coinciding with Somebody else . In mail it was written , to post about the evidence .

C Problem was not too difficult for a person with average coding skills . The only trick in C was to get a control over the loop . I have seen many tutorials of past contests and in C problem , I used that for controlling the loop as the most common approach in these types get solved in nlog(n) or n root(n) . So I did it for n root(n) and then the code was simple a Brute force logic . It took me a number of contest and practice to reach specialist . Please reply me if i need to submit any supporting proof and what else can i upload . Please help GlebsHP , MikeMirzayanov . please do reply.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C.. I want to understand the repetitive behavior of the function (sum_from_1_to_2n % n), Please mention a mathematical or intuitive (better :) reasoning..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

F is really fascinating.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone give me any hint for problem H? Is the problem approachable with bitmask dp and meet in the middle?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    H can be solved with bitmask DP, but you have to come up with some methods to sum up the costs cleverly.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem I am facing is, I have two option, counter-clockwise and clockwise.

      I mean if its counter clockwise i have to add (a — b) * cnt[i][j] and (b — a) * cnt[i][j] if its clockwise. If i had only clockwise/ counter clockwise, i could have split the equation and take the sum independently (a * cnt[i][j] — b * cnt[i][j] for only counter clockwise). But now, how do i know which one is clock wise and which one is counter clockwise.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's the main difficulty of the problem. An approach is to consider the problem not from the perspective of characters, but from the edges on the cycle, that is, how many times each of them is used.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a formula mistake in tutorial of problem F.

Having the correct value of $$$c_(G_i)(v)$$$ we can use the binary search ...

That should be: Having the correct value of $$$c_{G_i}(v)$$$ we can use the binary search ...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tutorial is not available

    Why:(

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Looks like it takes some minutes for Codeforces to load the editorial from polygon's package. It is available now

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple DP for D... why is the editorial so complicated?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am very curious how the data of problem F was made, LOL

It is a really interesting problem, lots of thanks to the problem provider!

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

For the editorial of problem C, can you prove the following line?

"The remainders of x of modulo n will repeat after 2n steps".

In other words, How can you prove that, sums of all integers from 1 to i (1 <= i <= 2*n) will generate all the remainders from 0 to n-1, when diving by n?

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

Great problem C! Would like to share my approach. I observed a fairly obvious thing, for f=1, you will land on (x+1)%n [obviously], after that you can keep adding i (2<=i<=n) to the latest number. Eg: For n=5, x=2: 2 (+1)-> 3 (+2)-> 0 (+3)-> 3 (+4)-> 2 (+5)-> 2 , so now you again reached your starting point (2 in this case). This will hold for any odd n, as n*(n+1)/2 will by k*n which is congruent to 0 (mod n). So after n such steps you will always reach the starting x. After that the pattern pretty much loops, so we don't need to add more elements. For even n, this will not be true! (Reason: n*(n+1)/2 and n=2k => k*(2k+1) which need not give remainder 0 with 2k), but what will hold now is the same pattern twice! For eg: n=4, x=2: 2 (+1)-> 3 (+2)->1 (+3)->0 (+4)->0 (+1)->1 (+2)->3 (+3)->2 (+4)->2 !! (see how after one chain we reached 0 and not 2, but after 2 such operations we reached 2 again, proof is pretty simple, now as n=2k => 2n = 4k, so 4k*(4k+1)/2 = 2k*(4k+1) which is congruent to 0 (mod n=2k).

After that you can store the n values (for odd case) and 2n values (for even case), and find the minimum index of 0. If there is no 0, that means for any p, you cant ever win. Else if p>= min_index : yes Else: no Here is my code for reference. Hope this explains well!

→ Reply