RDDCCD's blog

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
By RDDCCD, history, 19 months ago, In English

Hello, Codeforces!

I'm very glad to invite you to participate in CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Mar/31/2023 17:35 (Moscow time).You will be given 8 problems and 2 hours to solve them. The round will be rated for everyone.

I'd like to give my sincere thanks to:

Hope everyone can enjoy the round!

UPD: The tutorial is here.

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 4.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 4 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

  • 1st place: 1,024 TON
  • 2–3 places: 512 TON each
  • 4–7 places: 256 TON each
  • 8–15 places: 128 TON each
  • …
  • 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 4 and hope you enjoy the contest!

  • Vote: I like it
  • +687
  • Vote: I do not like it

Comments Comments (168)
| Write comment?
»
19 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

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

    As a tester, give me 2147483647 TON.

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

      Unfortunately, they only award prizes that are powers of 2.

      → Reply
»
19 months ago, # |
  Vote: I like it +130 Vote: I do not like it

As a tester, give me TON.

→ Reply
»
19 months ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester, problems are great, recommend everyone to participate!

→ Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

May this will be my color change contest

→ Reply
»
19 months ago, # |
  Vote: I like it +59 Vote: I do not like it

Finally a div1+2 round after half month.

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

    But the provincial team selection contest will be held in tomorrow morning. I'm going to miss this round :(

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

    Isn't this usual nowadays ?

    → Reply
»
19 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope I can bounce back from my horrendous performance last time.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +50 Vote: I do not like it

Nostalgia hit me.

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

My first div1...ready to face the challenge

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

so excited !

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

As a tester, problems are educational and wonderful, hope everyone can enjoy

→ Reply
»
19 months ago, # |
  Vote: I like it +34 Vote: I do not like it

TON is about 2.10$, Thank me later :)

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

hope to be Expert

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

    You are already Expert bro . What are you talking about? This time you will reach it . I will try not to blunder this time.

    → Reply
»
19 months ago, # |
  Vote: I like it +31 Vote: I do not like it

As a tester, give me TON.

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

    How are the first two letters of your nickname black (at least in chrome mobile)

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

Hope I will solve A anh B @@ As a participants, hope everyone have the best work!!

→ Reply
»
19 months ago, # |
  Vote: I like it -40 Vote: I do not like it

I will AK it using Genshin Impact:)

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

.

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

Where will these ton tokens be transferred? I mean we haven't filled a wallet address whole registration neither is there a link to put our wallet address on website or any other place.

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

    in past times, the wallet was asked after only those who won something

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

    you can put your ton wallet address in your account settings

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

Can anyone explain why we can read many times ".... give me a TON"?

→ Reply
»
19 months ago, # |
  Vote: I like it +26 Vote: I do not like it

As a tester, I think this contest is very worthwhile to participate in. I hope everyone who join this contest can get satisfactory results.:)

→ Reply
»
19 months ago, # |
  Vote: I like it +30 Vote: I do not like it

We need a TON of positive delta rating!

→ Reply
»
19 months ago, # |
  Vote: I like it +49 Vote: I do not like it

I hope to reach 2100, and I wish everyone all the best!!

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

Will try to cross 1500 this time. Looking forward to solve upto 4 problems.(atleast 3).

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

facing long in queue problem!!

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

Will a scoring distribution be announced?

→ Reply
»
19 months ago, # |
  Vote: I like it +28 Vote: I do not like it

I'm jiangly fan,jiangly is No.1!!!

→ Reply
»
19 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I really wanna reach 1900 today. The mark has been psyching me out for so long now. I dont wanna care about my rating!!!! I wish me and you all the best!! (I just wish it a tiny bit more for myself :D)

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

    Definitely, you can. Best Wishes.

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

Where's score distribution?

→ Reply
»
19 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Where's score distribution?

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

What Happened to tourist ?

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

    No worries. Anything can happen. As I'm a tourist fan, I believe that tourist will beat No.1 next time.

    → Reply
»
19 months ago, # |
  Vote: I like it +39 Vote: I do not like it

jiangly! best of the best

→ Reply
»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I'm very excited to see editorial for task H!

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

Good round! Sadly I ran out of time for D and I think I would have been able to solve with ~10 more minutes.

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

hard round.

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

Problems were great overall, but needing to use Fibonacci Heap for E in Java to not TLE was obnoxious.

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

    standard heap runs fine in pypy

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

    What exactly was your solution, you should be able to use bucket sort since values are in $$$[0, n]$$$.

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

      Small to big with a disjoint set, where you merge the smaller priority queue of edges into the bigger priority queue every time you need to merge two nodes.

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

        Very convoluted. Suppose you add all vertices with $$$a_i = X$$$ to the graph with all $$$a_i \leq X-1$$$. If you can defeat $$$X$$$, you can defeat the component. If you can defeat $$$X$$$ now, you could have defeated $$$X-1$$$ before, which means you were able to defeat the component. You can maintain if the whole component is defeatable together with its size in DSU.

        → Reply
»
19 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Problem B is the same problem as one of the problem in Constructor Open Cup Contest yesterday

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

    Ah... An interesting coincidence :( The two contests are so close.

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

    Actually there was a small difference: solution was guaranteed in Constructor Open Cup, and today there was a -1 option.

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

The time of which of the submissions counts to the result on codeforces? The first or last?

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +96 Vote: I do not like it

Historic Submission: https://mirror.codeforces.com/contest/1810/submission/200000000

→ Reply
»
19 months ago, # |
  Vote: I like it +32 Vote: I do not like it

B is almost absolutely the same as a problem in Constructor Open Contest 2023 which was yesterday

→ Reply
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Submited D in last second but system didnt register it, also B is harder than C or D

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

    I just drew a binary tree from 1 and got the greedy idea, and I found B quite easier than C (just my opinion) Didn't even get time to look at D

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

Problem E is solvable using "Kruskal Reconstruction Tree" technique. The weight of edge (u, v) is max(a[u], a[v]). After we built the tree, we climb from leaves with a[u] = 0 and check if we can climb up to the root in the reconstruction tree.

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

    It's also solvable with Boruvka's algorithm + BFS

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

      I solved it with DSU and merging sets

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

        Also solvable by shuffling all zeroes and performing BFS from each of them. The only optimization is to start only from zeroes which we had never reached before.

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

          Wow, that is smart. What is the expected complexity of your solution?

          → Reply
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            I would like to know that too.

            Edit: Even without shuffling, this algorithm will visit each node at most $$$\log(n)$$$ times. So the upper bound complexity is $$$O(m \log^2 n)$$$. Maybe with shuffling we can get smth better.

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

              I did this too: I think it's $$$O(m\log n)$$$ since the expected number of 0s you start from is $$$O(\log n)$$$ and each time you can explore almost all the edges in the graph?

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

                Could you explain how the expected number of 0s we start from are $$$O(log n)$$$ ?

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

          Correct me if I'm wrong, I think you don't need to shuffle the zeroes as the worst case will only visit all N nodes at most log(N) times.

          → Reply
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            ← Rev. 3   Vote: I like it +3 Vote: I do not like it

            Yeah, got it, you are right. So we don't need to shuffle and the overall complexity is at most $$$O(m \log^2 n)$$$ using priority queue inside BFS.

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

              why are we visiting each node at most $$$logn$$$ times ?

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

            This complexity analysis is so hard. I came up with the solution immediately but didn't dare code it because I though it was $$$O(n^2)$$$. Now I play around some linked-list cases and can see that it is indeed impossible to reach $$$O(n^2)$$$, but can you please elaborate on how to prove $$$O(mlog^2n)$$$?

            Edit: it was in the editorial.

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

          I did the same thing. Here is my solution. 200012713

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

          I upsolved the prob using a similar strategy, But I didn't realize that that optimization would be enough, so after performing each BFS, I combined all visited nodes into a "super-node" to make sure that i didn't iterate over each node too many times. The core logic is super similar tho.

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

Any hints for D?

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

    try to keep the minimum and maximum possible length of the tree after each query

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

      thanks, was very close to this just made some calculation mistakes

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

How to do E?

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

bool isPossible(long long int mid, long long int height, long long int a, long long int b)
{
    if(((a-b)*(mid-1LL)*1LL) + a >= height) return true;
    else return false;
}
long long int calDays(long long int height, long long int a, long long int b)
{
    if(height == 0) return 1;
    if(height <= a) return 1;
    long long int left = 1; long long int right = 1e18;
    while((right - left) > 1)
    {
        long long int mid = left + ((right - left)/2);
        if(isPossible(mid, height, a, b)) right = mid;
        else left = mid+1;
    }
    if(isPossible(left, height, a, b)) return left;
    else return right;
}

In question D, I was trying to find number of days taken by snail to reach height h, given a and b using Binary search. Is something wrong in my approach as I am getting WA in TC5.

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

    probably overflow on (a-b)*(mid-1LL)

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

      So, taking long long right = 1e9 will solve the overflow issue? BTW I don't think overflow is the problem, because I have submitted the code with a value of right less than 1e9. And still I got WA in TC5.

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

        IDK, I did long long right = 2 * 1e18 / (a-b) to avoid this issue

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

        I think setting right = 1e9 is also bad, for example, when a=2,b=1, h = 1e15

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

    Same problem with me! But why BS doesn't work here??????????????

    It is equivalent to the direct math formula, both calculate the same.

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

      It is working well. You just have to be careful of the overflow.

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

        I was already careful! My binary search limits is 0 and 2e9 Submission: 200007394

        Update: The problem is that we need the limit to be upto 1e18 which may lead to overflow. Thanks!

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

https://mirror.codeforces.com/contest/1810/submission/200007256

Why did I get WA?

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

Can anybody Tell me why my code fail in Problem C

https://mirror.codeforces.com/contest/1810/submission/200015122

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

    Firstly,You haven't considered all possible start mex values(according to your code you have checked for 1 and 2) and even after this,all possible combinations of insertions and deletions that are possible are not considered (try looking at the editorial or look into my submission for a better understanding of it) Happy Codeing:)

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

Any ideas why this D is failing pre-tests? I spent 1 hour debugging and could not find the bug:

https://mirror.codeforces.com/contest/1810/submission/199997167

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

    I think the tree height can be more than 2e9 (for example if a snail has $$$a = 10^{9}, b = 1$$$ and $$$n = 10^9$$$)

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

I got 7 WAs on D trying to use binary search before realizing it was just math...

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

is Div2D solvable with just math?

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Determining whether a node is good (you can start from the node and reach the entire graph) is just implementation.

The solution of E is quite straightforward when you observe that if a node is not good, the nodes it can reach are also not good.

Edit: Systest accepted, but not sure if there is an test case that will TLE this

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it +45 Vote: I do not like it

Nice div1+div2 contest. Solved A-E. My solution of F passed pretest but it's very likely to get TLE on system test.

A: We just to need check if there's any i where a[i]<=i.

B: We can only get odd number by operation, so if n%2==0 there's no solution. Otherwise, we can represent (n-1)/2 in binary, and add 1 to all digits (for example: 17 -> (17-1)/2=8 -> 8=1000(2) -> answer is 2 1 1 1).

C: First we can remove all numbers and add single 1, which costs n*c+d. Otherwise, assume the size of the final permutation we get is k (and k>1), and there are m missing numbers in range [1, k] in the initial array. Then we need to add m numbers and remove (n-(k-m)) numbers, the cost is c*(n-(k-m))+d*m = c*n + (c+d)*m — c*k. If we let k+=1 and m+=1 (which means, k+1 is a missing number in the initial array), the cost will increase by d, so in any optimal answer, k must be a number in the initial array. So we can iterate for every possible option of k and get the answer.

D: Implementation problem. We just need to maintain the upperbound and lowerbound of h for each type-1 query, and for type-2 query we need to check if the answer for (h_max, a, b) and (h_min, a, b) are the same. Be careful for case a>=h.

E: DSU. We sort edges (u, v) by the value of max(a[u], a[v]) and add them by this order. First mark all nodes with a[u]==0 as good. WLOG assume a[u]>=a[v]. When mergeing (u, v), if v is good and the size of component of v is not greater than a[u], we mark all nodes in the component of (u, v) good. To defeat all monsters, we need the graph to be connected and all nodes are good.

F: The answer is ceil(log_m(sum(m^a[i]))). We need to maintain the base-m representation of sum(m^a[i])) by a segment tree, and update it by binary search.

Update: Upsolved F with atcoder library: 200024728

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

    Amazing performance today! (despite FST!)

    → Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    FST((

    Anyways congratulations with almost becoming red!

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

    gratz! Great performance anyway, amazing result of your constant upsolving

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

    Can you please explain logic behind (n-1)/2 in B?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Let f(x)=(x-1)/2 and see how operations affect f(x):

      Operation 1: x --> 2*x-1

      f(x)=(x-1)/2 f(2*x-1)=x-1

      which is: f(x) --> 2*f(x) (put a 0 after a binary number)

      Operation 2: x --> 2*x+1

      f(x)=(x-1)/2 f(2*x+1)=x

      which is: f(x) --> 2*f(x)+1 (put a 1 after a binary number)

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

    For problem B, I didn't get this point "Otherwise, we can represent (n-1)/2 ". Can you explain a little bit more?

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

      Yeah i dont get it too lol

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

        I think he is trying to say that since number is always odd as we progress from 1 to our desired number n, that we can go from n downwards in this fahsion:

        we could get to n etiher by number (n-1)/2 or by number (n+1)/2, whichever of them is odd(other one always isnt) is the number from which we came to n

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

    Could you (or someone else) please elaborate the logic behind your algorithm for E? I don't seem to understand it at all. Thanks!

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

    Can you explain the merging part of your solution for E please?

    → Reply
»
19 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Although managed to solve D and probably will get positive delta, still problem D was awful in my opinion. There was nothing interesting about it. It just required being extra careful, which is very annoying.

A was ok, B and C were nice.

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

I don't understand problem D, anyone help me:((

→ Reply
»
19 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Problem D is really orz

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

As a contestant who won 4TONs, please give me TONs

→ Reply
»
19 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Jiangly!!!

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

May I know why my problem A's submission is still in pretest passed stage?

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

weak pretests on E? I passed pretests in 295 ms and seemed to have failed systests :(. Hurts more since I was going to reach CM.

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

    Looks like this is on me. My solution is the same as edi's except I set visited as 0 for all nodes each time I bfs instead of setting visited as 0 only for nodes visited in the last bfs which significantly worsens complexity.

    Still sad how the pretests didn't catch this.

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

A round with a 200000000 parcel?

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

Congratulate nightcrawler0112 for submitting the 2e8-th solution 200000000 in this contest!

→ Reply
»
19 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Due to a network failure, I accidentally submitted my solution to problem D twice (see 199967726 and 199967904) and got a resubmission penalty. Is there a way to get my score back?

Also, hats off to everyone who prepared this fantastic contest, and I'm excited to finally become red after 5.25 years of cp!

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
Help! Why is the code for my question D passable in GNU C++17 or GNU C++14, but not in GNU C++20? I used the ceil function at first, but changed it later and still had the same problem. Here is the link to my code:https://mirror.codeforces.com/contest/1810/submission/200022673
→ Reply
»
19 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Awesome contest (at least problems A-D)!

However I have a question regarding the problem D. This is what some test case (second test case in Example) can look like:

3
1 6 5 1
2 3 1
2 6 2

The answer is 

1 -1 1

Why is the second number $$$-1$$$, and not $$$3$$$?

From the first event we can get that $$$h=6$$$. That is the only possible solution for $$$h$$$. We have $$$h$$$ and in the second event we are given $$$a$$$ and $$$b$$$. We can now calculate $$$n$$$ with formula $$$n=$$$ $$$\lceil \frac{h-b}{a-b} \rceil$$$ and that equals $$$3$$$.

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

    from the first event you can get that 1<=h<=6

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

      can you please explain 2nd event also? It will be helpful for us.

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

        from the first event you know that 1<=h<=6 in the second event if h=4 for exampe it needs 2 days to reach the top but if h=6 it needs 3 days to get to the top thats why you can't know how many days it needs.

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

      Thank you very much, now I got AC.

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

Anyone knows why my C fails?

https://mirror.codeforces.com/contest/1810/submission/199982867

Any help is appreciated.

→ Reply
»
19 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Is it suspicious if someone submits D and E with 8 mins gap and there's different style of giving brackets in all the submission (submissions of D and B don't have extra space before curly braces while E, C and A have)

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

How do we receive TON, if we ranked below 1024? Did we have to fill some form or will we automatically receive mail for the same?

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

Isnt the test case 5 of C wrong, the min cost comes out to be 22, not 20.

Dropping a duplicate 4: 2

Inserting 1,2: 2*8 = 16

Dropping 7,8: 2*2 = 4

Total = 2+16+4 = 22

while the answer is given to be 20. Can someone help me with this, if I am wrong? Thanks

→ Reply
»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Finally turned purple with this contest. Thanks for the Amazing round!

→ Reply
»
19 months ago, # |
  Vote: I like it -14 Vote: I do not like it

D was undoubtedly unclear problem statement. Much more clarification was needed

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

How and when do we recieve toncoin prizes

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

Can someone please help me with my submission of problem D submission Thank You

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

    Try avoiding ceil() function. ceil() has some precision issues for large numbers. That's why your answer is wrong for large input. Use below, it will get accepted.

    void tim(ll up,ll dw){
    if(l==-1){
    cout<<"-1 ";
    }
    else{
    ll lb=1+((l-up)+(up-dw-1))/(up-dw);
    if(l<up)lb=1;
    ll ub=1+((r-up)+(up-dw-1))/(up-dw);
    if(r<up)ub=1;
    if(ub!=lb)cout<<"-1 ";
    else cout<<ub<<" ";
    }
    }

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

      Thank you so much I will remember it .

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

@RDDCCD

RDDCCD

EDITORIAL IS NOT ACCESSIBLE.

I had written one comment on yesterday's editorial. After which I had received some downvotes. Is that why I am banned from seeing an editorial page...

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

    i dont think so, i cannot see it either :3

    Edit : editorial is open again

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

    Ah, that's maybe because I was wrting the editorial of H at that time. I don't know it will make the editorial unaccessible :(.

    Anyway, editorial for H is finished now.

    → Reply
»
19 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Has anyone received TON coins? When will it be released?

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

    Do I need to do anything other than add my ton wallet to codeforces?

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

    Not yet (TON't)

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

Edit: I just received it, thank you!

Am I the only one who didn't receive the ton prize?

It's been over a month now.

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

I was notified the my solution for the contest match with some other solution in problem A. When this round took place I was not aware about how to address this issue so I am commenting now. Your solution 199973419 for the problem 1810A significantly coincides with solutions shreyansh_125/199969542, Mr.Roamer/199973419. Look at the solutions , I am shocked that the plag checker also checked Problem A , as it's code is so simple everyone can write it's code similar to mine. It's just a coincidence that we used same variable names (which are also common names). Pls check both solutions I did not copied any code.

→ Reply