RDDCCD's blog

By RDDCCD, history, 19 months ago, In English

A. Beautiful Sequence

Hint
Tutorial
Solution

B. Candies

Hint
Tutorial
Solution

C.Make It Permutation

Hint 1
Hint 2
Tutorial
Solution

D.Climbing the Tree

Hint
Tutorial
Solution

E.Monsters

Hint 1
Hint 2
Tutorial
Solution

F.M-tree

Hint 1
Hint 2
Tutorial
Solution

G. The Maximum Prefix

Hint
Tutorial
Solution

H.Last Number

Hint
Tutorial
Solution 1(floor sum)
Solution 2(fibonacci)
  • Vote: I like it
  • +269
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Wow. Tutorial was released even before system testing was over. Nice contest overall <3

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

well prepared !

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

Wow! . Very Fast . Excellent Contest . Jiangly is new No. 1 :)

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

OMG!Jiangly rk 1!

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

The announcement has disappeared?

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

Problem F is basically a generalization of 1705E - Mark and Professor Koro. I described a segment tree-free solution here that can easily be generalized to this problem.

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

Can someone please help me with problem C My approach was to find the upper bound for each value and calculating values required to be removed and added using it Code

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

    work with lower bound

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

      Could you please help me with a tc where this might fail. Or why does this fail.Thank you for your time

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1
    2 813259240 924953903
    21 100
    
    run this....
    
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problems and fast editorial.

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

In problem E, how do they come to conclusion that |S(u′)|>2|S(u)|?

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

    If $$$u'$$$ can reach any vertex in $$$S(u)$$$ then it can reach all vertices $$$v$$$ in $$$S(u)$$$. Before reaching $$$v$$$, $$$|S(u')| > |S(u)|$$$ and after visiting all of $$$S(u)$$$, $$$|S(u')| > 2|S(u)|$$$

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

      It has to visit all of $$$S(u)$$$ angin, why eventually one vertex can not be visited more than $$$log(n)$$$ times

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

        Lets say $$$v$$$ is visited by $$$u_1,u_2,...,u_i$$$, then $$$|S(u_i)|>2^i|S(v)|$$$.

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

      Also, the reason why $$$|S(u')| > |S(u)|$$$ before reaching $$$v$$$ is because there must be some $$$x$$$ which we could not reach from $$$u$$$ (because $$$a_x > |S(u)|$$$) and $$$x$$$ was in $$$E(S(u))$$$ i.e $$$x$$$ was one of the neighbour of $$$S(u)$$$.

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

        Are you saying that $$$ |S(u')| > |S(u)| $$$ because we reach this $$$x$$$ that is not in $$$S(u)$$$ before we reach any vertex of $$$S(u)$$$? And reaching such an $$$x$$$ would require the above condition.
        But is it not possible that $$$x$$$ could only be reached after visiting some vertices in $$$S(u)$$$. Or am I understanding it wrong? Could you please explain

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

          To clear up your confusion, I will list two lemmas, which would help you understand my above claim if you put them together.

          1. If you can reach some vertex of $$$S(u)$$$ from $$$u'$$$, then you can reach all the vertices in $$$S(u)$$$ from $$$u'$$$.
          2. If there exists some vertex $$$x$$$ with smallest $$$a_x$$$ which is not part of $$$S(u)$$$ and this vertex $$$x$$$ can be reached by $$$u'$$$, it means $$$|S(u')|$$$ before defeating $$$x$$$ should be at least $$$a_x$$$.
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Right, I understand these two lemmas. Now from what I get, you can get to $$$x$$$ from $$$u'$$$ before touching any vertices of $$$S(u)$$$, which gives you $$$|S(u')| > |S(u)|$$$ by Lemma-2
            Then you touch all the vertices of $$$S(u)$$$ by Lemma-1 since you can reach $$$v$$$ from $$$u$$$ and this gives you the extra $$$|S(u)|$$$ in $$$|S(u')|$$$.
            However I still don't get why we can reach $$$x$$$ before touching any of the vertices in $$$S(u)$$$ necessarily. Could you explain that?

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

              Oh, now I get what your confusion is. We will always reach x before reaching any vertices in $$$S(u)$$$ because these vertices form the boundary of $$$S(u)$$$. We cannot reach an internal vertex without going through the boundary.

              Example:- let's say the minimum $$$a_x$$$ value of a vertex $$$x$$$ which is not reachable from $$$u$$$ is $$$10$$$ and assume that $$$|S(u)|$$$ is $$$6$$$. Then it is impossible to reach any vertex in $$$|S(u)|$$$ without passing through a vertex with $$$a_i$$$ less than $$$10$$$.

              Also, we assume that the answer exists. Meaning that we can defeat all the monsters.

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

In problem B, "Then consider how the binary representation changes..." — I mean, all of a sudden people have to consider binary representation of a number? :) I find this kind of problem a bit weird. I know that the idea and solution is nice and neat but when you solve it you kind of expect more general approaches to work here like backtracking or some easy calculations but this kind of reasoning seem to be not suitable for problem B. I solved it exactly the way it is described in the solution, but it was just kind of a luck.

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

    When $$$n$$$ is odd, either one of $$$\frac{n + 1}{2}$$$ or $$$\frac{n - 1}{2}$$$ is odd. You can perform the operation that makes $$$n$$$ remain in odd, eventually $$$n$$$ will end at $$$1$$$.

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

is there any reason as to why we do not consider the 40 spell limit in the 2nd question?

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

    Each operation you might want to do increases the number of significant bits in the number's binary representation. As the maximum value of $$$n$$$ we might want is $$$10^9$$$ which has only $$$31$$$ bits, we would need at most $$$31$$$ operations (+/-1 if my logic has some off-by-one error) which is clearly less than $$$40$$$.

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

Can anyone help me in my solution for C. https://codeforces.net/contest/1810/submission/200018474.

Spoiler
»
19 months ago, # |
Rev. 6   Vote: I like it -72 Vote: I do not like it

Cheers to authors. Overall Great round. I wanted to share my opinion on problem D.

Problem D is the little bit bad for C++ users compared to python.

There is a formula to find number of days require to reach height 'h'.

But instead of using formula, if we use BINARY SEARCH , then there is very stupid long long overflow.

Sincere request to authors to avoid these kind of problems which are language specific. In this problem, using binary search in c++ is 10x more difficult than using python. RDDCCD

Below is my implementation in c++, EVEN AFTER USING LONG LONG, I am getting overflow. is there any way to overcome this ?


// "ll" stands for long long ll getDays(ll h, ll a , ll b) { // returns minimum number of days required to reach height 'h' ll l = 1LL , r = h; while(l < r) { ll m = (l+r)/2LL; ll climb = (m-1LL) * (a-b) + a; // this line gets overflow if(climb >= h) { r = m; } else { l = m+1LL; } } return l; }
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    One possible way is to set $$$r = \lceil \frac{h}{a-b} \rceil$$$ I think. Or using int128. You can also detect whether overflow occurs, like checking (climb > (8e18/(a-b)). If it occurs, just set r = m.

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

    There exists 128-bit integer in C++ which is big enough since you aren't crossing ~$$$10^{27}$$$ and 128-bit integer can hold numbers up to ~$$$10^{38}$$$.

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

    You can also use the thing I used to get AC : 200027884. This prevents overflow. I got this idea from ' binary search — edu section ' of codeforces.

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

    I faced a similar problem, so I just decided to use math to compute the #of days and it got AC. Not until I had like 10 WA's tho lol (mostly b/c i kept changing the bounds of my binary search)

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

Great round, thank you problemsetters!

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

The proof of the time complexity of E is quite an impressive part of this problem. I like it very much. (I came up with this solution in the last 20 minutes, but I thought that was $$$O(n^2log\ n)$$$ and lost the chance for a nice rating change. T_T)

ABCD are a little too easy, considering the difficulty difference between D and E. I was somehow slower on ABCD than usual, and then my rank fell down a lot.

Anyway, a nice contest. Really enjoyed it.

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

    the proof is similar to tree-dsu, basically we can merge sets from small to large and our complexity will stay nlogn, something like that.

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

      Right. In this problem it's easy to find we're merging sets, but the fact that $$$\vert S(u') \vert \gt \vert S(u) \vert$$$ before adding vertex $$$v$$$ , is not that obvious, I think.

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

200033270 I am getting the wrong answer in test case 7. I think there is some overflow error, but I cannot get it. I am using long long everywhere still. It will be helpful if somebody can find out what I am doing wrong. Thanks in advance.

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

Today's Codeforces contest crossed the mark of 200 million submissions, what a coincidence! Congratulations!

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

In problem D, the tutorial and the solution use different formulas to compute n, given h, a and b. When I tried, the tutorial formula gives Wrong Answer on Test Case 7 or something. Can someone please help me understand how to arrive at the formula given in the solution code? Also, please confirm if the tutorial formula is wrong. Thanks in advance :)

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

    It is correct,see my code there.

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

    They are actually the same, based on the fact that $$$\lceil \frac{x}{y} \rceil = \lfloor \frac{x+y-1}{y} \rfloor$$$.

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

      Thank you so much for the proof RDDCCD, and the confirmation HELLO2024. After a lot of struggle, I finally figured out that the issue was with Python's floating point precision in the division of large numbers using the division / operator. The integer division // operation somehow doesn't suffer from the same precision problem. And hence gets Accepted! My Wild guess: " Perhaps the // operator knows ahead of time that the return value is going to be an integer, and hence can allocate all the precision to the integer part of the answer". Using floor or ceil after a / operation is simply not foolproof, because the first division operation will give us imprecise results. Conclusion: Use C++, or just learn more about the limitations and features of your language better.

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

        with c++ also you can get the same thing , may be one case better than yours haha,

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

    You can check my simple solution 200085618. I hope it helps.

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

      Thanks mate. The issue was not with the formula but with the precision of my programming language(Python).

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

    just submitted it using c++ 17, the same code was not getting accepted in c++20 282393808

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

Problem B is exactly the same as problem D from yesterday's Constructor University contest.

D. Mana

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

in problem B , why loop started from 29

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

In Problem C, if we take c = 1, d = 1 and a = [3, 5, 6, 7, 4, 5]. The algorithm in tutorial gives answer 3 while according to me, the answer should be 5 calculated manually. Can someone explain how the minimum cost is 3?

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

    If you add $$$1$$$ and $$$2$$$ and remove $$$5$$$ the array will be $$$[1,2,3,5,6,7,4]$$$, which is a permutation. You added two numbers and removed one number so the total cost is $$$3$$$.

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

First time ever editorial released this fast. Thanks RDDCCD

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

Anyone solved problem C using DP ? If yes please provide the solution.

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

    solution I didn't name the arrays (rm -- cost to remove all the elements behind, and is -- cost to insert to the current element) dp, but I guess it could be expressed as a dp method

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

For Problem D why is it

ll ans1 = max(1LL, (L - b - 1) / (a - b) + 1) , ans2 = max(1LL, (R - b - 1) / (a - b) + 1); `

and not

ll ans1 = max(1LL, ceil((double)(L - a) / (a - b)) + 1) , ans2 = max(1LL, ceil((double)(R - a) / (a - b)) + 1);

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

    These two could mean the same thing, but we always prefer to process integers only, because double (float number) has error from its essence.

    P.S. In my submission 200018265 I used

    ll nl = max(0LL,l-a)/(a-b) + (max(0LL,l-a)%(a-b)!=0) + 1;

    ll nh = max(0LL,h-a)/(a-b) + (max(0LL,h-a)%(a-b)!=0) + 1;

    which might seem more natural

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

Here's my solution to E, which I find pretty beautiful too :

We'll add vertices one by one by danger increasing, keeping connected components with a dsu. For each component, we remember if we can visit all of it starting from one vertex (say it is good).

Initially, all vertices of danger 0 are marked as good.

When we add a new vertex, for each of its neighbors (smaller than him), if its component is smaller than the current danger, it becomes bad, since all of its neighbors are stronger than its size. Then we merge, the new component being good if one of the two was.

At the end, we just check if only one component is left and if it is good.

This gives a $$$O(nlog(n))$$$ solution, which is little more to implement than a dsu.

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

    Thank you for the solution. Much easier to understand.

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

What is $$$mdash$$$ doing in code for F?

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

    That's a format error. Fixed now.

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

Hello I am here to solve problem C using Binary Search. 1. First Step of Binary Search to choose minimum and a maximum of the answer:-

we know that we have two operations:- 1. remove an element from array a of length n (c cost per remove) 2. insert from array a of length n (d cost per insert at any position)

So, if the array is initially in the permutation form then we need zero operation but if not then we need a maximum operation to convert the array into permutation form by removing all the elements and inserting only one element which is 1 i.e** n*c+d **.

This means we need minimum operation zero(0) and maximum operation n*c+d.

  1. The second step of the Binary Search approach is to find the bool function:-
  • parameter for bool function -> (array->a,c,d,k) this function will return that is it possible to convert an array 'a' into permutation array in 'k' cost.

  • first, we have to check that many different elements are present in the array because, in the permutation array, no duplicate elements are allowed.

  • let array 'x' contain a different element of the array 'a' in sorted order.

  • So we have to remove the (n-x.size()) element from an array 'a' because no duplicate elements are allowed, which takes cost c*(n-x.size()).

  • and array 'x' must contain 1 element because without one permutation array is not possible. therefore, if x does not contain 1 then we have to insert 1 in the first place which takes cost 'd'.

  • Finally, we come to the last operation of this problem where we have to convert the 'x' array into a permutation array:-

    • we declare a variable 'cnt' which is initialized by one.
    • we traverse in the array 'x' and check if x[i]-cnt>0 if yes then means we have inserted the element in this position to make permutation array till index 'i' or we remove all the from i to n-1 inclusive.
    • we have to update cnt accordingly which statement we choose.

Code for bool function :- bool helper(ll n,ll cost,set&s,ll c,ll d){ cost -= (n-s.size())*c; std::vectorans; for(auto i : s){ ans.push_back(i); } if(ans[0] != 1){ ans.insert(ans.begin(),1); cost -= d; }

if(cost < 0){
    return false;
}

ll cnt = 1;
for(ll i=0;i<ans.size();i++){
    if(ans[i]-cnt > 0){
        ll temp = ans[i]-cnt;
        ll temp1 = ans.size()-i;

        if(temp1*c <= cost){
            cost -= temp1*c;
            break;
        }else if(temp*d <= cost){
            cost -= temp*d;
            cnt += temp+1;
        }else{
            return false;
        }
    }else{
        cnt += 1;
    }
}

return cost >= 0;

}

My Code for this Solution using Binary Search:- https://codeforces.net/contest/1810/submission/200121687

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

Is it possible to solve problem E with the algorithm for finding bridges online?

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

I am getting WA in TC 4, I don't know why? Can somebody help me? Solution:https://codeforces.net/contest/1810/submission/200348409

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

My codes Why will it overflow?And I don't no what's wrong will my solution.

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

Can anyone explain in problem H, how the formula $$$d_i = n - \lceil\frac{i}{\phi}\rceil + 1$$$ pops out from $$$\sum_{j=1}^k{[d_j-j \ge d_k]} + n - d_k + 1 = k$$$ in the second lemma proof? Is this a known fact and does it have any name on it? You have to at least come up with shape of the formula in order to proceed through the proof further anyway...

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

Can we solve problem F using Huffman Tree? Although they seems similar I still have no idea about that. I can only do it in $$$O(qnlogn)$$$.

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

In editorial of problem E, v is add into S(u′) again . We are considering only the case when v is add. We would be processing v also when we add it to some E(S(u')). In this case, the condition |S(u′)|>2|S(u)| might fail.

What am I missing?

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

    Ah, you can try to think in another way: if we only consider adding v to some $$$S(u)$$$, it will not exceed $$$log(n)$$$ times per vertex. And what happened when we add v to some $$$S(u)$$$? We visit all it's neighbors and (possibly) add them to $$$E(S(u))$$$. That would not exceed $$$deg(v)$$$ times. Overall, it will not exceed $$$log(n) \cdot \sum{deg(v)} = m log(n)$$$.

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

Note that in H, $$$O(N_{max}+T)$$$ time and space works as well. We sort the queries and simulate the part before $$$x$$$. Since the part after $$$x$$$ is just an alternating-sign sum and we're adding/removing elements from the sum in 2-pointers style, it's easy to maintain the current sum until the last duplicate element and extend it to all required elements for each query. The only tricky part is implementation since there's some casework based on parity and $$$O(N_{max})$$$ space is a lot, I used bitset to denote which elements are duplicated.

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

What kind of test is testcase 4 : [5189th token] in problem E? (wrong answer expected YES, found NO)

»
11 months ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

Nice Explanations