BucketPotato's blog

Codeforces Round #809 (Div. 2)
By BucketPotato, 21 month(s) ago, In English

Hi Codeforces,

We're excited to invite you to Codeforces Round 809 (Div. 2), which will take place at Jul/18/2022 17:35 (Moscow time). All problems were created and prepared by lunchbox, lce4113, and me. It will be rated for all participants with ratings lower than 2100.

Thanks to the people that made this round possible:

You will be given 2 hours to solve 5 problems, one of which will be divided into 2 subtasks. The scoring distribution will be announced later.

UPD: The scoring distribution will be $$$500 - 1000 - 1250 - (1000 + 1250) - 2250$$$.

UPD2: The editorial has been posted at https://codeforces.com/blog/entry/105008.

UPD3: Winners

Official

  1. WYZFL
  2. c8k
  3. tiger1926
  4. b6e0
  5. iztrax

Everyone

  1. tourist
  2. SSRS_
  3. WYZFL
  4. Rubikun
  5. noimi
  • Vote: I like it
  • +472
  • Vote: I do not like it

Comments Comments (167)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +119 Vote: I do not like it

As a tester...

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

As a massive fan of hugs, cosy blobs, and the problem-setting team, I am looking forward to the contest!

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

As a tester, tester is just a premutation of setter

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

    Damn

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

    As a contestant, contest is just a prefix of contestant

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

As a useless problemsetter, I hope you enjoy this round!

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

    As a contestant, waiting for the score distribution...

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

As an author, BucketPotato orz.

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

BucketPotato round orz

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

BucketPotato orz.
As a tester, I can confirm that the problems are very interesting and would recommend everyone to participate in the contest.

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

    So you want to say I won't loose cm first round after I reached it? :thinking:

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

      Congratulations for CM!
      Yeah, hopefully you will not lose CM just after you reached it.

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

        Thanks, then I'm like 2 times calmer to participate xdd

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

BucketPotato hard carry orz

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

As a tester this round is extraordinary

Take it or BucketPotato will come to your house and enact his revenge

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

As a CFer, BucketPotato orz

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

Seeing sus as a tester makes me feel really excited about this round!!

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

Through the last two competitions, I have reached “pupil”. I hope my rating can reach 1300 in this competition!

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

Can anyone tell me how to become a tester for cf contest? What are the criteria for it ?

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

    How to become a CodeForces tester 101:
    Step 1. Become friends with some setters
    Step 2. Profit

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

      How to become friend with some setters?

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

        Seduction works

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

          Unspoken rizz

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

          I don't know how to seduce :( probably just gonna make myself an e-girl

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

As a contestant I hope I can become Specialist

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

    as a contestant I hope I can become expert :D

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

BucketPotato orz

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

I hope this Div2 gets easier!

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

Good luck everyone. I hope this round is easier than the last round.

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

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

Best of luck everyone! Lets's give our best in this contest.

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

:pkinghi: BucketPotato Orz. Master of hugs.

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

You will be given 2 hours to solve 5 problems, one of which will be divided into 2 subtasks Can someone explain what divided into 2 subtasks means.

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

    I think we could have same two problems with different constraints as b1 b2 for example

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

    It doesn't always mean different constraints. That means we will have 6 problems, but two of them will be very similar.

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

as a participant I am participating

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

I hope this is a Codeforces round and not a Mathforces one.

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

As a Rating-rapid-decline-er, I hope I can enjoy this round.

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

Hope there will be more contests in the near future <3

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

I think codeforces have best userInterface amongs all comptetive coding platform.

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

Scoring distribution when

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

It's time for Pupil :)

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

How do I become a tester?

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

for proposing problems that didn't make it to the final version of the round. XD XD.

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

hoping not to become pupil again

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

Looking forward to this round! After this round, I should become green.

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

I like B.

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

What's the backstory of naming D1 as Chopping Carrots?

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

    Originally, the statement looked something like this (this is a very condensed version of it):

    You are preparing carrots to cook. The carrot can be modeled as a non-decreasing array, and your chopping skills are represented by an integer k. The roughness of an array p is max(a / p) — min(a / p), find the minimum roughness of the carrot you can achieve.

    The flavor text was ultimately taken out since testers found it made the statement more confusing.

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

B is way harder than C to me.

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

    B is greedy

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

      How? I see only dp solution.

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

        How can you please explain your approach?

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

        difference between index of 2 same colors should be odd so that we can put them in same tower

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

        We need to have odd distances between indexes of each frequency to build

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

          Yes, wiered named friend, but how is this greedy?

          The dp is more or less simple:

              vvi dp(2, vi(n+2));
    vi ans(n);
    for(int i=n-1; i>=0; i--) {
        dp[i%2][c[i]]=dp[1-i%2][c[i]]+1;
        ans[c[i]]=max(ans[c[i]], dp[i%2][c[i]]);
    }
          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            It's dp because you solved it using dp and its greedy because I solved it using greedy.

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

How to solve D1?(Just some hint)

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

Is the main idea for $$$E$$$ to maintain a DSU and for each 'root' node mantain the set of intervals covered and then merge them appropriately?

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

    This wasn't my approach. I used DSU with small-to-large merging to find the earliest time at which vertex v is connected to vertex v+1, for all v. Then, queries can be answered by storing these times on a segtree and storing the maximum values within the range [L, R-1].

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

      This is exactly what I did, only difference is I used when v is connected to v-1.

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

    That was what I thought of during contest (164782058), but realized only after that a much simpler solution exists.

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

Hi, I have a hard time debugging my code. For example, today's Div2D1, I felt I had made it but then I had WA on pretest 3 and I couldn't debug fast. Here is my submission. https://codeforces.com/contest/1706/submission/164793681 Any tips on fast debugging? Thanks!

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

In problem C when n=6 there will be 3 possibilities right (2,4) or (2,5) or (3,5)?

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

    if n = odd, it becomes trivial. If n = even: For every tower we want to make cool we can pick it up from 2 array:

    1) 2,4,6,8,... 2) 3,5,7,9,...

    Suppose you pick i from 1) then you need rest (n/2-1-i) from 2). Just iterate over i and take the min.

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

      I saw many guys use dp to solve problem C, i don't know why. The problem description says "maximize the number of cool buildings."

      I think we have 1 option for n % 2 == 1, and 2 options for n % 2 == 0.

      n == 6 is a special case and has 3 options.

      So what I missed?

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

        You can "skip" a building in case of n % 2 == 0
        Consider the case of
        10 9 7 7 7 7 9 10

        "odd" and "even" options use 2 + 1 + 3 = 6 floors

        10 (9->11) 7 (7->8) 7 (7->10) 9 10
        10 9 (7->10) 7 (7->8) 7 (9->11) 10

        while optimal solution

        10 (9->11) 7 (7->8) 7 7 (9->11) 10

        uses only 2 + 1 + 2 = 5 floors.

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

          If n is even: For some building x, choose all odd indexed in the left to x, and all even indexed buildings to the right of x. So there is a gap of two non-cool buildings near x.

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

            10 9 7 7 7 7 9 10

            0 1 0 1 0 1 0 0

            0 0 1 0 1 0 1 0

            there are only two options, right? I need an example which has more than 2 options except n == 6, cause (6 — 2)/2 = 6-4

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

              3 options:

              01010100 (6 floors)
              00101010 (6 floors)
              01010010 (5 floors)

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

Easier Div2?

  • I like B, it's good D2B
  • I saw some tasks similar to C somewhere
  • Why so tight ML for D2? I have a painful work making the memory of my solution < 64MB
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Linear memory is intended I think. My submission with $$$3n$$$ integers on a BST (instead of heap) only used 6MB, so if anything I think it could have been 32MB

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

    Agreed re: D2. The process of solving D2 was very unpleasant for me--I came up with/recognized the main observation in <2m, then took the vast majority of my time dealing with the memory optimization. In particular, because $$$\sum a_n$$$ was unbounded, my approach to optimizing the memory was dependent on the fact that the number of tests was small, as it leads to a time complexity of $$$O(n \sqrt{n}) + a_n)$$$ per test case. The problem is solvable in linear memory, but the process of optimizing to linear memory is not at all interesting, and the linear memory solution doesn't feel any more clever than the $$$n \sqrt{n}$$$ memory solution.

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

    Sorry for the trouble, there is a $$$n \sqrt n$$$ two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct $$$O(n)$$$ memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory without any optimizations.

    As for the difficulty, there was originally a problem F, but testing suggested that up to E was hard enough.

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

      My O(n) memory solution requires me to change std::vector to std::list, or free the memory of std::vector correctly (.clear() doesn't free the memory).

      It's a bit annoying. :(

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

        I also MLEed once due to clear().

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

        Sorry to hear :(

        Our correct intended solutions take some more thinking, but have clean and easy implementations (no optimizations needed).

        So I guess the difficulty of this task was in, do you want to optimize your code or think of a cleaner solution?

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

          I believe the core idea of mine (the one changed to std::list 164802621) and the posted solution doesn't differ a lot. (to me, it's just some computation order)
          Are there any more clever solutions?

          I know knowing the programming language I used is also a part of CP, but just don't like it to be kinda the only point of a problem.

          btw, what do u mean by optimizing my solution?

          Anyway, other problems are not bad.
          Thanks for the contest!

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

            The main idea is the same, but the way you go about it is different:

            Your solution uses a vector<list<int>> to help determine cmx (using variable names from your code), and has to update the lists as you sweep through.

            The intended solution also finds all values of cmx, but uses the additional idea of prefix maxes on increasing functions to simplify the memory usage to a single int pf[100000 + 1].

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

        I had MLE with vectors too, but during contest I forgot about std::list and wrote custom (164757358)

        Changing vector to list in upsolving gives AC but sadly it is ~9x times slower than custom (164886835)

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

    I was using a linear memory solution, but it was using vector<vector<int>> and the memory still blew up and used > 64 MB.

    Then I learned that .clear() does not necessarily reallocate to make the capacity back to 0. To "force clear" a vector, one can use vector<int>().swap(x)

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

    I also agree about seeing C somewhere. I did try spending a little bit of time looking for it, but ended up not finding anything. I don't know how similar the problem I remember was, but it involved this idea of a[i] > a[i — 1] and a[i] > a[i + 1]

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

wow, memory limits in D1 are divine. I submitted with O(n*3000) time, using 2d arrays, but it got ml. I changed algorithm for 2d arrays to 1d, and it passed. 5 incorrect attemps, rest in peace. But i had to gain only 4 points to reach CM

164778279

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

Is it Div.3?

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

I think my solution to D2 only uses O(N) memory, but still can't pass TC11.

upd: std::vector is so hard (.shrink_to_fit() is stupid)

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

In the end, I solved three problems, which made me very happy. But how to solve D1?

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

    I think you fix either the max or minimum value and use brute force, but I didn't solve it, so I'm not too sure.

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

      Yes, but instead of brute force use two pointers.

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

Video Solution for Problem C.

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

    I did pretty much the same thing.

    Here is my submission:164775959

    Can anyone give me a fail-case.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Testcase
      Your output
      Correct Output
      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

I think the input constraints in problem D2 are really confusing. Why those $$$O(n\sqrt n\log n)$$$ solutions can get pretests passed but a $$$O(A\log n\log A)$$$ solution (my idea) can't get PP (only $$$\sum n$$$ is $$$10^5$$$ but $$$\sum A$$$ isn't) so I wasted a lot of time on this problem and I didn't solve problem E (or even carefully read the statement) which I found a solution just 5 minutes after the contest.

Anyway, good contest & problems, hope the next round will be better.

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

    If $$$n=100000$$$,$$$\sqrt{n}\approx320$$$,$$$nlog^2n \approx 256$$$,but the constant of segment tree is so big that it is greater than $$$320$$$ after multipliying $$$256$$$.

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

I used DSU to get when each point is first added to the connected graph, and then use segment tree to query the maximum values within the range [L+1, R].Why I couldn't get a accepted?my submisson

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

    that's not correct. Added to connected graph does not mean connected to previous node.

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

I used Overall dichotomous( $$$O(n \log^2 n)$$$ ) ，but TLE on 4. Am I wrong ? mysubmission

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

I think the most difficult problem in this contest is at most *2200 :(

so it like div.3.

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

    we heard you the first time now shut up jesus christ

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

    Maybe most difficult one idk about that, but A, B and C's are not far from expected div2 difficulty

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

D seems to be an easy one but when I started I found it a bit complicated :)..

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

Why problem B Complexity: O(n) can not pass?164782973

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

Well, problem E is better to be put in an edu round. And D2 is a totally trash problem I think.

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

    Sorry to hear. What did you dislike about D?

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

      Too difficult to implementation.

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

        just about 10 lines except for careful memory management. Where is difficult?

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

        Hi, the intended solution codes for D2 have now been posted (here and here). IMO, the implementation in both is very clean and easy, no optimizations needed.

        As I said in a different comment, the difficulty in this problem seems to lie on whether you want to painfully optimize a simple idea or think a little more to find a nicer solution.

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

          It says "you are not allowed to view the requested page" when I click on 2nd link(/here).

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

            Sorry, the link has been fixed

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

              Thanks for the contest!Awesome problems especially B,D2 and E!

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

First time to AK a div 2 contest!

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

Is the below statement true?
for integers a and p, where 1<= p <= sqrt(a) . floor(a/p) is unique.
Proof if any?

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

How to get unique elements of a/p for an integer a and p <= k, efficiently for problem D2?

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

    Iterate over segments:

    start with [1, 1]

    then next for [l, r] will be [r+1, a / ( a / l )]

    in each segment a // i is constant (l <= i <= r).

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

      Thank you very much. And are the number of unique a/ps around sqrt(a)?, if we consider k as infinity.
      I wanted to calculate time complexity.

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

        There will be no more than 2 * sqrt(a) such segments

        First part where r <= sqrt have l = r

        In second part a / p = sqrt ... 1

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

Ratings updated preliminary. As I said here: https://codeforces.com/blog/entry/104766?#comment-932270 cheaters will be removed later.

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

thx for specialist-1... im totally fine after today's contest

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

div2.5

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

I'm sorry I missed the fight

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

How to become stronger quickly

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

Problems were somewhat hard in this contest.

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

Could anyone have a look at this code?

https://codeforces.com/contest/1706/submission/164815320

The solution got TLE before I added an early exit trick, then it got AC, I have no idea why. It seems that the early exit trick is wrong. So is the data too weak or the early exit is actually correct?

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

    why are you glorifying this shenanigan by calling it a "trick"

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

      Is the word trick kinda glorifying? I don't think so.

      And, if actually it can be proved at most a certain amount of updates lead to the minimized answer, then it's not a shenanigan. This is also why I am asking here. I'm not able to construct a case failing the solution.

      Besides, early exit is sometimes useful in OI competitions.

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

For problem B:

I understand vectors are slower than arrays but can someone help me understand why I got TLE. Thanks.

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

    You are making vectors of size 100005 irrespective of n. Instead make vectors of size n, it will get accepted :)

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

Hi MikeMirzayanov. My solution for problem A was detected as coincide with another solution. However, this is not a violation because I have not leaked or copied the code. This is only because the logic for problem A is quite simple so the 2 solutions may have looked quite the same. I also encountered this last time. I do not have concrete evidence to show that this is a false cheating detection. But I just want to inform you so that you may reduce the detection for easy problems. This may help other coders too and more importantly, I do not want to see my account blocked because of this incorrect detection.

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

Why are my ratings rolled back without any message like cheating warnings?

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

    They have been temporarily rolled back for everyone. It will be back after removing cheaters

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

Hi MikeMirzayanov. my solution 164765949 for the problem 1706B significantly coincides with solutions with others. But I have solved it myself you have take a look at submissions of my previous contest solutions, in which I have used same methodology to solve the problems. I haven't indulge in any malpractice in during the contest.

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

    Even in the apology comment, you are copying from others' apology comments LMAO.

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

As a tester, please give me contribution.

The only goal for joining the test is to get more marks and get more ratings.

→ Reply