tourist's blog

By tourist, 4 weeks ago, In English

Hope you enjoyed the round!

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
  • +346
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Thanks for the fast editorial :)

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Blogewoosh #8 when?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

Thanks for the interesting problems. Overall an awesome contest.Orz. Will make sure I don't miss your future rounds :)

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for an amazing round and fast editorial:)

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

    will someone please help me telling what's wrong with my div2 B submission:

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        int t;
        cin>>t;
        while(t--){
            int a, b; cin>>a>>b;
            //consider the case when alice serves for the for the first time
            set<int> ans;
            int p = (a+b)/2;
            int q = p;
            if((a+b)&1){
                ++p;
            }
            for(int x = 0; x<=p; x++){
                // a  = p - x + y => y = a - p + x;
                int y = a - p + x;
                int k = x + y;
                if(x>=0&&y>=0&&(b==q - y + x)&&((x+y)<=(a+b)))
                ans.insert(k);
            }
            swap(p, q);
            for(int x = 0; x<=p; x++){
                // a  = p - x + y => y = a - p + x;
                int y = a - p + x;
                int k = x + y;
                if(x>=0&&y>=0&&(b==q - y + x)&&((x+y)<=(a+b)))
                ans.insert(k);
            }
            cout<<ans.size()<<'\n';
            for(auto e: ans){
                cout<<e<<' ';
            }
            cout<<'\n';
        }
        return 0;
    }
    

    I did it exactly like solution given here. please help me fast please

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Awesome contest. Nice challenges! Thank you!

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Can anyone explain how to do D1? I am not able to understand

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

Was O(N √N log(N) ) intended to fail on DIV2 D1?

I believe my submission: 126895459 had that complexity yet it tled on D1 or am I missing something? :(

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

    Nope, but I couldn't find an error in your solution (sorry =(, I am very tired). But you can check mine which has the same complexity and maybe figure out the problem.

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

      I think constant factor of my code was greater than that of yours (around 5 times).

      It required heavy optimizations to pass(barely):); But I still don't understand why the constant factor my code was so high compared to yours.

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

    I think it was. I did the exact same thing as you and it tled. I mean it takes 2*10^5*447*14=1.25e9 operations, which is improbable to finish in 6 seconds.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Thank you for the editorial. In problem A (Simply Strange Sort), why do we have to start swapping odd indices first? Can't we start swapping even indices first? For instance, for this case, why should the answer be equal to 7?

7

6 4 5 3 2 7 1

if we start swapping odd initially. The answer is 7.

  • 4 6 3 5 2 7 1
  • 4 3 6 2 5 1 7
  • 3 4 2 6 1 5 7
  • 3 2 4 1 6 5 7
  • 2 3 1 4 5 6 7
  • 2 1 3 4 5 6 7
  • 1 2 3 4 5 6 7

but if we start from even indices, the answer is 6.

  • 6 4 5 2 3 1 7
  • 4 6 2 5 1 3 7
  • 4 2 6 1 5 3 7
  • 2 4 1 6 3 5 7
  • 2 1 4 3 6 5 7
  • 1 2 3 4 5 6 7

Please, help. What am I missing?

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

    We don't choose the start. We perform operations on the basis of iteration parity and iterations start from 1 . We are not trying to minimize the iterations. Just performing the iterations till the array becomes sorted. :)

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

      Thank you. I should have read the problem statement carefully.

      The algorithm consists of iterations, numbered with consecutive integers starting with 1.

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

    Well, there is a sentence in paragraph 4 says "On the i-th iteration, the algorithm does the following:" which means your first iteration must be odd (your counting must start with number one)

»
4 weeks ago, # |
  Vote: I like it +99 Vote: I do not like it

I was surprised to see the $$$m \leq 2000$$$ requirement in E, as I have a very simple $$$\mathcal{O}(n^2 \log \max a_i)$$$ solution.

In every step, we try to find the path that

  • starts from $$$0$$$
  • loops back to itself
  • doesn't contain only already beaten caves

that requires the minimum initial strength. Then, we merge nodes on that path with 0, and update the values of minimum initial strength and strength gained over initial strength. We repeat this until all nodes have been processed.

This is clearly correct, since taking the path looping back to itself with minimum required strength cannot hurt you: you end up in a cycle, so you can still go anywhere afterwards, and any solution to the problem has to have you travel a cycle.

To find this loop, we binary search the initial strength required to beat it, then do a DFS (or BFS, the order doesn't matter) of caves we can get to with that initial strength. We maintain for every cave the previous cave, and don't allow going back to it. Once we have two paths to some cave, we have found a cycle, as we could take the one that ends with greater strength in the forward-direction, and the other going back.

We can sort edges from vertices in increasing order of the strength of the monster on the cave on the other end, and break once the monster is too strong for the strength coming from our current cave. If we ever end up in the same cave multiple times, we are done, so every vertex gets handled at most once every step. Thus, we take $$$\mathcal{O}(n)$$$ time every step.

We might need to add $$$\mathcal{O}(n)$$$ loops, and do $$$\mathcal{O}(\log \max a_i)$$$ DFS's every time, each taking $$$\mathcal{O}(n)$$$ time, so the total time complexity is $$$\mathcal{O}(n^2 \log \max a_i)$$$.

Code: 126910619

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

    complexity of your DFS should be O(n + m)?

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

      No. Think about using DFS to find a cycle in a undirected graph. While we haven't found a cycle, we have handled at most one in-edge to every vertex (as following the backpointers from a vertex with two in-edges gives a cycle) -- thus we handle $$$\mathcal{O}(n)$$$ edges in the worst case, and the DFS runs in $$$\mathcal{O}(n)$$$ time.

      Here the DFS is a bit different, but we similarly return once we have two in-edges to a vertex, so the same proof works.

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

I like how the same problem is the easiest and toughest in this round, just different constraints.

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

https://codeforces.com/contest/1561/submission/126865692 ---> TLE one https://codeforces.com/contest/1561/submission/126911328 ---> accepted (same code) my submissions of today A question both codes were same one at the time of contest this gave me tle on test case 11 in system testing but now after the system testing i submitted the same code again by removig some comments it got accepted .... with 31ms

can anyone explain why it happened......

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

    This is very strange. I think it might actually be a problem with the judge. One thing to note though is that creating arrays with variable length is not allowed in c++ standard. Most people create them with constant sizes. However, I doubt that's the problem because it apparently works in gnu c++.

    Maybe MikeMirzayanov or someone who knows better can check...

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

      I also thought so,when I actually saw it during sys tests.

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

      felt very sad after this happened ..... i would be near to pupil , but after this now again its so far -120 in the contest due to this ....

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

    It is matter of chance that it got accepted the second time, you are checking the last element also in the odd loop. a[i] > a[i+1] gives undefined behavior for i == n. Maybe your loop ran infinite times in systests.

»
4 weeks ago, # |
  Vote: I like it +166 Vote: I do not like it

 I was quite right with my prediction...

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

    Dr. Strange !

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

      What are instincts ? How much one can rely on their instincts ? When two kind instincts appear which one you should rely on?

      These kind of questions will always be asked by the mankind...and there will be no end to seeking

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for the editorial and the contest. It was great.

»
4 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

I think the editorial of 1561C — Deep Down Below meant to say $$$b_i=\max(\ldots)$$$ instead of $$$\min$$$, likewise for $$$p$$$.

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

What was the role of less space(128 mb) in Div2 D1. And how many iterations can be run in 6 sec time limit?

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

    2e8(cpp)*6==?

    and the first question is explained in the editorial

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

What's the reason behind stopping $$$O(N \log^2 N)$$$ solutions to pass in Div.2 D2? All the solutions utilizing factors rather than multiples already struggle with $$$10^6$$$ inputs and exceed the given 6 seconds, whereas $$$O(N \log^2 N)$$$ fenwick tree solutions take < 2 seconds on those tests.

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

    I thought of fenwick tree approach but only towards the end. Did you find any?

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

      The best I managed is the one described in the last line of editorial (it TLEs on test 7 because of the extra log factor). So fenwick simply doesn't work because it could be avoided by simple prefix/suffix sums or difference arrays, but I got stuck on it. Here are my two submissions for the sake of comparison (in the AC one I traverse from the front, but it is essentially the same thing).

      126906387 126864992

»
4 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

The ordering for 1561C - Deep Down Below can be found with exchange argument too. Consider two sequence of monsters A(a1,a2,...,ap) and B(b1,b2,...,bq) now,

since from the editorial it is clear that, initial power level needs to be greater than max( a1 -0 , a2 - 1 , a3 -2 , ... , ap - (p-1) ) if we go through cave A we create two auxiliary sequence from the original sequence A_aux( ( a1 -0 , a2 - 1 , a3 -2 , ... , ap - (p-1) ) ) and B_aux( b1 - 0 , b2 - 1 , .... , bq - (q-1) )

if A is traversed before B the minimum initial power level in this case needs to be x1 = max( max(A_aux) , ( max(B_aux) - size(A_aux))) [ size(A_aux) is subtracted from the second part because before going to second cave power is incremented by size(A_aux) ]

if B is traversed before A the minimum initial power level in this case needs to be x2 = max( max(B_aux) , ( max(A_aux) - size(B_aux))) [ size(B_aux) is subtracted from the second part because before going to second cave power is incremented by size(B_aux) ]

now we need our initial power level to be small in case to A traversed before B , i.e x1 < x2 => max( max(A_aux) , ( max(B_aux) - size(A_aux))) < max( max(B_aux) , ( max(A_aux) - size(B_aux))) . this custom sort rules can be used to get the ordering of the caves.

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

problem D1 ,how to work sqrt(n) ,please anyone explain this...

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

    If you consider $$$x = p^2 - k$$$, such that $$$p^2 - k > (p-1)^2$$$, then it is straightforward to show that $$$\left\lfloor\frac{x}{\lfloor\sqrt{x}\rfloor}\right\rfloor - \left\lfloor\frac{x}{\lfloor\sqrt{x}\rfloor + 1}\right\rfloor \ge 1$$$ (left-hand-side can only be either $$$1$$$ or $$$2$$$), which means that consecutive addenda up to this threshold point to different cells. Note: $$$\left\lfloor\sqrt{p^2-k}\right\rfloor = p-1$$$, for $$$k>0$$$.

    As to how pick up that threshold might be of form $$$\lfloor\sqrt{x}\rfloor$$$, one of the options would be to start from solution of the related continuous problem. Consider some generic function $$$f(x)$$$, and minimize functional $$$F[f] = -f(x)$$$ with respect to the (continuous) constraint $$$\frac{x}{f(x)} - \frac{x}{f(x)+1} = a, a \ge 1$$$. Or equivalently (using Lagrange multipliers): $$$F[f] = -f(x) + \lambda \left(a - \frac{x}{f(x)} + \frac{x}{f(x)+1}\right) \to f(x)=\sqrt{\frac{x}{a} + \frac{1}{4}}-\frac{1}{2}$$$.

    Then maximize $$$f(x)$$$ within the space of valid $$$a$$$'s: $$$(a=1) \to f(x) = \sqrt{x + \frac{1}{4}}-\frac{1}{2}$$$

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

I think f(n) = n not f(1) = 1 for 1558 B Up The Strip

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

In Problem C, I tried Binary Search on $$$x$$$ in my submission https://codeforces.com/contest/1561/submission/126887144, but was faced with the problem of which array to enter first. I tried implementing some sorting algorithm to sort the vectors according to the current power in the binary search, and if for two vectors $$$a$$$ and $$$b$$$, there exists $$$1 \le i \le min(a.\text{size}(), b.\text{size}())$$$ such that $$$\text{power} \le a[i]$$$ but $$$\text{power} > b[i]$$$, then $$$b$$$ has to come before $$$a$$$ in the order. (You can see other details in the cmp function) However, that solution doesn't pass. Any help?

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

    Lets say b={1,1,10} a={1,3} and power is 2 then according to your logic b should come before a(for i=3). however it cannot enter there.

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

      Yes, and that's OK. Since the Binary Search takes care of which power to choose. For example, in your case, $$$b$$$ comes before $$$a$$$, but anyways $$$\text{power} = 2$$$ doesn't work. Anyways, my submission outputs $$$7$$$ for the input you gave, which is correct.

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

      Anyways, I realized where the error is. Thanks everyone!

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I love how Div 1F and Div 2A are the same problem. I just glanced at 1F to see if I understood the problem (I usually don't), and it was a pleasant surprise.

»
4 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

I have a solution to div1E that does not involve binary searching the initial power and runs in $$$O(NM \log N)$$$. We start off with 1 power. We run Dijkstra on the graph several times, each time starting from the set of defeated caves so far, to find the shortest path to each unvisited cave that requires the least increase to the starting power. This requires keeping track of the power increase along the path. The dijkstra comparator breaks ties among two nodes $$$u$$$ and $$$v$$$ by preferring the one that grants the largest power up to that point.

Technically there are negative cycles, but we just ignore cycles altogether by not revisiting processed nodes. At the end we have a shortest path tree. We can find in this tree the "cheapest" (requiring least increase in starting power) node that has at least one non-tree edge adjacent to it, then "accept" the increase in starting power and visit the path + cycle from this non-tree edge. Each iteration takes $$$O(M \log N)$$$ or $$$O(N \log N + M)$$$ and there are at most $$$O(N)$$$ iterations until we visit all the caves, so $$$O(NM \log N)$$$ in total.

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

The first one is Accept,the second one is WrongAnswer,Why? The only difference between them is

ll ans = 0;
		for (int i = 1; i < n; i++) {
			if (temp[i - 1].first + temp[i - 1].second <= temp[i].first) {
				ans += temp[i].first - (temp[i - 1].first + temp[i - 1].second);
			}
		}

and

ll ans = 0;
		ll aa = temp[0].first;
		for (int i = 1; i < n; i++) {
			aa += temp[i - 1].second;
			if (aa <= temp[i].first) {
				ans += temp[i].first - aa;
				aa = temp[i].first;
			}
		}

126917320 126917418

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

    They look like the same but their basically doing different things.While the second code uses var aa which takes temp.first and keeps adding temp.second till the if statement evaluates to true again, the first code uses only the previous values (i.e.: i-1 in temp.first and temp.second).

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

I had a slightly different approach for Div 2 D / Div 1 B.

Calculating the ways you can reach a number by subtracting was straightforward, but I used suffix sums to calculate the sum of ways you can reach a given number by dividing another number.

The code can be seen here.

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

    That's what I also did. It's seems way more intuitive.

    However I didn't think that you could also hold a suffix sum with the memory constraint so I used the dp array as the suffix sum. I think it's a pretty neat trick 126918785.

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

      hey , why are you adding dp[i+1] again at the end of the outer loop?

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

    In your code dp[i] stands for the sum of ways we can go from n to i. But I have a slightly different way of thinking from yours too: instead of going from n to 1, we can go from 1 to n. dp[i] stands for the sum of ways we can go from i to 1. For every i, for every divisor j ranging from 2 to n / i, it is possible to go from [i * j, (i + 1) * j) to i dividing j. So simply add dp[i] to dp[i * j, (i + 1) * j) using a prefix sum. the time complexity is O(n + n/2 + ... + n/n)=O(n log n).

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Very Good Contest.

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

Can someone please explain the reccurence relation in 1558B- Up The Strip and why it’s time complexity is O(n^2) , Thank you in advance.

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

    The time complexity of a dp recurrence is $$$no. of$$$ $$$states$$$ $$$*$$$ $$$no. of$$$ $$$transitions$$$. Since there are $$$O(n)$$$ states it can visit and it has $$$O(n)$$$ transitions, the total time complexity is $$$O(n^2)$$$.

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

      What exactly do you mean by the O(n) transitions?

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

        Transition time basically means how much time it takes to compute a single dp state. Here, to compute $$$f(x)$$$, you would need to compute $$$\sum_{y=1}^{x-1} {f(x-y)}$$$ and $$$\sum_{z=2}^x {f(x/z)}$$$, both of which take $$$O(n)$$$ time each, therefore $$$O(n)$$$ time total.

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

Can anyone share a way to find a "closed-form" solution in problem B. Charmed by the Game?

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

My solution for D has $$$O(M \sqrt{M})$$$ complexity, but doesn't require to roll back any changes. It got AC in 592 ms. I process insertions in the same order as they are given in the input, and use linked list data structure. Each element of the list contains some continuous range of positions that have already had some element inserted right before them.

Any insertion from the input can increase the size of the list by up to $$$2$$$. Each time the size of the list becomes greater than some constant around $$$\sqrt{M}$$$ (I chose $$$520$$$) we need to squeeze all the elements of the list into one range, so our list has only one element in it after that.

»
4 weeks ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Such a shame that I wasn't able to solve Div 2 D1 yesterday since I was so close to the official tutorial.

I wasn't able to solve the floor function inequality, so I used binary search to find the upper and lower bound of $$$z$$$ instead, which makes my solution $$$O(N\sqrt{N}\log{N})$$$. That turned out too slow for the problem constraints though.

Moral of the story: Math is important. Here's my submission

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Hello there, I tried modifying your code slightly to avoid the TLE and it worked. Because the % and / operations are time-consuming, I tried to use them as little as possible. Link

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

      Wow, I didn't think that such small operations can affect performance greatly. Thanks for fixing my code and pointing out what's wrong!

»
4 weeks ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

This is my code for Question C, it's giving wrong answer and I can't understand where is the issue.Somebody please have a look and let me know what's wrong with my code.(I am using binary search approach here )

code
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    You can use spoiler to show your code:

    Code

    upd: Thanks :)

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

I was in awe for DIV2-D1, time limit was 6s and O(n^2) was not passing.

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

    Not even $$$O(N\sqrt{N}\log{N})$$$ will pass, so a TLE for $$$O(N^2)$$$ is kinda obvious.

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

Can anyone explain more clearly problem D2div2/Bdiv1

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

    My solution for D1 covers a part of the idea for D2.

    Hint for D2:
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain how exactly you would use prefix sums?

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

can anyone explain how to generate all divisors of n with it's prime factors ,div2/d2

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

in problem D, if i is divisor of x+1 why we need to replace i-1 to i ?

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

Will anyone please explain the idea of Problem B? Thanks in advance

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

    Without reducing the generality a >= b.
    First analyse the case (a+b) is even.
    First player has (a) won games. Lets distribute it between held and broken serves. Total quantity of serves for the first player is h = (a+b)/2. Minimum breaks quantity is a-h when first player holds all h his serves. Maximum breaks quantity is h+b, when the first player breaks all h serves of the opponent and the opponent breaks b serves of the first player. When we move one game from holds to breaks the total count of breaks increases by 2.
    So for even (a+b) answer sequence is a-h, a-h+2, ..., h+b
    When (a+b) is odd we may add to even case one break or one hold. Adding one break add 1 to the answer sequence. The answer sequence for odd (a+b) is:
    (a-b)/2, (a-b)/2+1, ..., h+b+1

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

      can you explain why min breaks are a — h why maximum breaks h+b

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

        Minimum breaks we get when the first player holds all his serves — h games. From the rest games first player wins a-h games. All these a-h games will be breaks.
        Maximum breaks we get when the first player wins all h serves of opponent. Plus opponent wins b serves of the first player.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

My solution to div2. D1/D2 or div1. B

Lets define dp[I] as number of ways to reach I from N, therefore dp[N] = 1.

We can calculate the value of dp[I] using the formula (iterating I from N — 1 to 1) :-

dp[I] = sum(dp[I + 1], dp[N]) + sum(dp[J * I], dp[min(J * I + J - 1, N)]); 

where J is [2, N / I]

The sum can be calculated with prefix sums in O(1) giving a time complexity of (N log N) where log N represent sum of harmonic series.

My submission: https://codeforces.com/contest/1561/submission/126890430

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Why can't use greedy in Div. 2 C (I use greedy and I get AC.)

upd. Solution:

For each cave $$$i$$$, calculate

$$$\large p_i = \sum_{j=1}^{k_i}(a_{i,j}-j+1)$$$

and then select the cave in the order of $$$p_i$$$ from small to large .

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

Why "Tutorial is not available" for 1558F

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Excellent contest. Thanks very much. I ran my algorithm exactly the same as the tutorial of div2d1 with case 200000 on my own machine and got exactly 6s runtime... so I submitted but got 3.35s runtime... CF's CPU is so fast!

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

Even the first question was confusing yesterday the level of questions blow my mind

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

Thanks for the amazing problems as always

cheers

\(^o^)/
»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there a reason why the constraint of div2D1 had to be 200000 instead of 100000?

I keep getting TLE with python even though 150000 would have worked.

Did anyone manage to implement the sqrt complexity editorial solution for D1 with python?

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

In problem D1, can somebody explain why there is at most sqrt(n) different values of floor(n/x) for all x in [2,n]? is it just a well known thing?

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

Hello , I am pretty sure that there is a mistake in engine check , please check those 2 solutions for problem C — Deep Down Below: this is my last submission in the contest : http://codeforces.com/contest/1561/submission/126904661

and this is the exact code except that i removed the compare function passed to sort , which actually does exactly the same as sort except when pair.first == pair.second , i choose the cave with more monsters , and this should not affect the solution : http://codeforces.com/contest/1561/submission/126961415

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

For Problem D:

Can someone please elaborate a bit more on why will sqrt(n) we have no repetititon of the quotient.

For example for 19 If we print out 19/1,19/2 and so on i.e

19 9 6 4 3 3 2 2 2 1 1 1 1 1 1 1 1 1 1.

Why till 4 i.e sqrt(19) we dont have any repetition?

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

    You need $$$\frac{n}{i} -\frac{n}{i+1} < 1$$$ or $$$i\cdot(i+1) > n$$$ and $$$i = \sqrt n$$$ is first integer that satisfie so anything larger that that will have consecutive difference with last less then 1 so repeat

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

tourist Editorial for 1558A - Charmed by the Game says "Analyzing the formulas further, we can find a "closed-form" solution". Can you explain how the equations of a and b got reduced to the final 3 "closed" forms ?

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

In editorial for Div2 D1,

Find the sum over all $$$z < sqrt(x)$$$ directly
is not correct ig. Let's say $$$x = 5$$$ & $$$z = 2$$$, then $$$z < sqrt(x)$$$ but $$$5 / 2 = 2$$$ which is less than $$$sqrt(5)$$$ and hence will be covered in loop for $$$c$$$ (refer the editorial).

so loop for $$$z$$$ should be $$$(x / z) > sqrt(x)$$$ or $$$z < floor(sqrt(x))$$$

correct me if I am wrong.

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

Hello guys, in problem 1561A — Simply Strange Sorting. Why can't we just look at a the sorted array and find the maximum difference? Example:
3 2 1
2 3 1 ==> i = 1
2 1 3 ==> i = 2
1 2 3 ==> i = 3

So the maximum distance is moved by 3 and 1 i.e. 2 and answer = 2 + 1 = 3. Using same logic we can solve for other test cases. Can anyone suggest why will this approach fail?

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

In the problem D2 ,when I write int dp[N]={0,1,2}; outside the main() I got a CE --Compiled file is too large [34420807 bytes], but maximal allowed size is 33554432 bytes-- But when I write dp[1]=1; dp[2]=2; in the main(). It will not have this problem. why?

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

In problem 1558A — Charmed by the Game,In the 0<=x<=p and 0<=y<=q.I submitted the same solution but with relaxed constraints i.e 0<=x<=a and 0<=y<=b 126977218.I don't understand why this solution is also giving AC.We can clearly see the constraints we are imposing on x and y in the case of my solution isn't same.Your help is appreciated.

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

can someone help me with problem C, my code is giving right answers for some cases but giving ans + 1 for other. i stored the minimum powers to enter each cave and the power while exiting that cave in a vector pair and sorted according to the entry level powers and checked whether the exit level powers heres the code. 126983320

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

Why is there only a problem A code?

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Sorry for asking this, but can anyone please explain Div2-D2 in more detail? I looked at the others' solutions, but found it slightly hard to find the intuition behind their approach.

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

    I will try to tell how i came up with my solution.

    1. We are moving from n towards 1.
    2. Using moves of kind 1, what are possibles positions from where you can reach i(current index)? it will (i+1,i+2......n). So we will add the ways of reaching these value to the ways of reaching i th position.
    3. Using moves of kind 2, what are possibles positions from where you can reach i(current index)? here things get a bit trick, see if at some place you used z=2 and reached i what were the possible x's? (2i to 2i+1 right? because 2i+2 onwards, on division by 2 will yeild $$$> $$$ i ), similarly by using z = 3 (3i to 3i+2) ,z = 4 (4i to 4i+3), and ya this will be O(nlogn) because it's $$$\sum n/i $$$.
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me how to do this part in the solution of 1558B?

We can achieve that by preparing a sieve of Eratosthenes, factorizing x and generating all its divisors.

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

I tried to implement 1561D1 - Up the Strip (simplified version) according to the editorial, but it's failing for large values can anyone tell what's wrong in my code ?

solve function

127054036

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

    In the second for loop you're condition is z*x<x.

    Otherwise my code is also same as yours and is not working as well.
    I guess there is something to do when $$$z$$$ , $$$c$$$ are near $$$√x$$$

    Help Appreciated!

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

      drunk_phoenix, gjain369, you add the same cell in both loops as early as $$$x=5$$$: $$$c=2$$$ and $$$z=2\to \lfloor x/z \rfloor=2$$$. The reason for that comes from variability in bound of $$$c$$$.

      Given $$$z \in \left\{1, \dots, \lfloor\sqrt{x}\rfloor\right\}$$$, then $$$c \in \left\{1, \dots, \left\lfloor \frac{x}{\lfloor\sqrt{x}\rfloor + 1} \right\rfloor \right\}$$$. Starting from definition of the floor function: $$$\lfloor\sqrt{x}\rfloor \le \sqrt{x} < \lfloor\sqrt{x}\rfloor + 1$$$, one can show that $$$\lfloor\sqrt{x}\rfloor - 1 \le \left\lfloor \frac{x}{\lfloor\sqrt{x}\rfloor + 1} \right\rfloor \le \lfloor\sqrt{x}\rfloor$$$. e.g. $$$x=5$$$ vs $$$x=7$$$.

      But since value of $$$\lfloor \sqrt{x}\rfloor$$$ is known from $$$z$$$-loop, boundary on $$$c$$$ can be computed directly.

      changes to the code
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes I knew there was some problem near $$$\sqrt{x}$$$.
        Thanks to your critical explaination.

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

        yeah , thanks for your explanation.

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

Did we need anykind of algorithm to solve problem B(div2)?if yes please tell me which one.

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

In 1561C, I didn't get the binary search approach. Can someone please help?

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

How can one solve 1561C - Deep Down Below using binary search?

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

For each i>1 that is a divisor of x+1, S(x+1) contains an occurrence of i that replaces an occurrence of i−1.

this line is written as a part of the second approach for the editorial of Div1B Up the Strip. I am unable to understand how we can arrive at this conclusion. Really appreciate some intuition on this. Thanks in advance

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

will someone please help me telling what's wrong with my div2 B submission:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int a, b; cin>>a>>b;
        //consider the case when alice serves for the for the first time
        set<int> ans;
        int p = (a+b)/2;
        int q = p;
        if((a+b)&1){
            ++p;
        }
        for(int x = 0; x<=p; x++){
            // a  = p - x + y => y = a - p + x;
            int y = a - p + x;
            int k = x + y;
            if(x>=0&&y>=0&&(b==q - y + x)&&((x+y)<=(a+b)))
            ans.insert(k);
        }
        swap(p, q);
        for(int x = 0; x<=p; x++){
            // a  = p - x + y => y = a - p + x;
            int y = a - p + x;
            int k = x + y;
            if(x>=0&&y>=0&&(b==q - y + x)&&((x+y)<=(a+b)))
            ans.insert(k);
        }
        cout<<ans.size()<<'\n';
        for(auto e: ans){
            cout<<e<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

I did it exactly like solution given here. please help me fast please

»
4 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

When will the editorial for Div1F be available? Meanwhile, here is a sketch of my solution.

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When can tourist update the Tutorial for Problem F?

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

Sorry, but this is not a newbie friendly editorial.

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

Thanks for good editorial !!!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a more clever (sub $$$N^2$$$) solution for the first problem?