RDDCCD's blog

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
By RDDCCD, history, 21 month(s) 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 31.03.2023 17:35 (Московское время).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?
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    As a tester, give me 2147483647 TON.

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

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

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

As a tester, give me TON.

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

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

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

May this will be my color change contest

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

Finally a div1+2 round after half month.

→ Reply
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't this usual nowadays ?

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

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

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

Nostalgia hit me.

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

My first div1...ready to face the challenge

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

so excited !

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

TON is about 2.10$, Thank me later :)

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

hope to be Expert

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

As a tester, give me TON.

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it -40 Vote: I do not like it

I will AK it using Genshin Impact:)

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

.

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can put your ton wallet address in your account settings

    → Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +30 Vote: I do not like it

We need a TON of positive delta rating!

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

facing long in queue problem!!

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

Will a scoring distribution be announced?

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

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

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Definitely, you can. Best Wishes.

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

Where's score distribution?

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

Where's score distribution?

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

What Happened to tourist ?

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +39 Vote: I do not like it

jiangly! best of the best

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

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

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

hard round.

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    standard heap runs fine in pypy

    → Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +96 Vote: I do not like it

Historic Submission: https://codeforces.net/contest/1810/submission/200000000

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      I solved it with DSU and merging sets

      → Reply
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for D?

→ Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

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

How to do E?

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1810/submission/200007256

Why did I get WA?

→ Reply
»
21 month(s) 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://codeforces.net/contest/1810/submission/200015122

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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://codeforces.net/contest/1810/submission/199997167

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

is Div2D solvable with just math?

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Amazing performance today! (despite FST!)

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

    FST((

    Anyways congratulations with almost becoming red!

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

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

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

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

    → Reply
    • »
      »
      »
      21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah i dont get it too lol

      → Reply
      • »
        »
        »
        »
        21 month(s) 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
  • »
    »
    21 month(s) 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
  • »
    »
    6 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

Problem D is really orz

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

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

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

Jiangly!!!

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

A round with a 200000000 parcel?

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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://codeforces.net/contest/1810/submission/200022673
→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you very much, now I got AC.

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

Anyone knows why my C fails?

https://codeforces.net/contest/1810/submission/199982867

Any help is appreciated.

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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

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

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

How and when do we recieve toncoin prizes

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much I will remember it .

      → Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) 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
»
20 months ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
  • »
    »
    20 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not yet (TON't)

    → Reply
»
19 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
»
8 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