azberjibiou's blog

By azberjibiou, history, 21 month(s) ago, In English

Hello Codeforces and welcome back to another div2 round.

YeongTree and I are excited to invite everyone to participate in Codeforces Round 851 (Div. 2), which will be held on 09.02.2023 17:35 (Московское время).

This round is rated for the participants with ratings strictly lower than 2100. You will be given 6 problems and 2 hours to solve them. All the problems are authored and prepared by YeongTree and me.

We would like to thank

The score distributions will be updated later.

UPD1: Score distribution: $$$500−1000-1500-2250−2500-3000$$$

UPD2: Congratulations to the winners!

Overall:

  1. jiangly
  2. MakaPakka
  3. MahiruShiina
  4. maspy
  5. tute7627

Rated participants

  1. MakaPakka
  2. _10circle_
  3. JJcjn
  4. 1cm
  5. YouPervertSucker

AC submissions at the last second

UPD3: Editorial is out

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

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

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

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

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

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

as a tester, qwexd ORZZZZ

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

As a tester, the problems were really good.

Participants, please enjoy the contest!

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

As a tester, I enjoyed the round and the statements were brief and clear. I hope to see you on the scoreboard!

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

As a tester, this was the best contest I have ever seen.

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

    as a tester, this was the best contest I have ever seen.

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

      As a participant , hoping this would be the best contest of [Contests I have ever seen + this contest]

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

As an apparent tester (I don't remember testing this round recently), I'm sure the problems are good :P

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

Good luck to everyone!!!

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

Good Luck for every Candidate Master to promote to Master!

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

OMG South Korean setters, good mathematical problems coming on the way :)

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

    Hahaha as a tester I cannot say about that now, but good luck if you participate!

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

      hahaha haha hahaha haha hahaha haha :(

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

    Haha nicely predicted.

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

Omg announcement shorter than tourist round

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

This contest may be a bit late, I guess I fell asleep at that time.

»
21 month(s) ago, # |
Rev. 4   Vote: I like it -19 Vote: I do not like it

good luck everyone!

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

As a tester, I tested this round in the period about when I was orange for the first time.

Problems are nice tho!

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

My first contest was tourist round. I solved 1st 2 problem and earned 389 rating. This will be my 2nd contest .

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

I will skip an academic seminar in my university and participate in this round.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

As a participant, I confirm that i will participate.

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

Sometimes I really want to skip school.

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

Please down me, thx.

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

As a tester, I enjoyed this round. Good luck!

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

Thanks for your excitation to invite us to participate in round !

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

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

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

Good Luck and Have Fun!

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

I will skip an academic seminar in my university and participate in this round

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

Wishing you all a positive delta!!

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

Best wishes for everyone

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

Worst Contest I have Ever Seen. What are these strict time limits !?!?

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

Me after solving C

Waiting for contest to end
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Same lol

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

    Can you please tell your approach on C?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      • Approach for C;
      • Let sum of all the numbers [ 1 to 2n ] : S_2n = ((2n)*(2n+1))/2;
      • After the construction of pairs, we will get [n] consecutive numbers
      • let's say the minimum sum of any pair be x;
      • Now, the sum of these [n] consecutive numbers, S_x = (x) + (x + 1) + ... + (x + (n-1))
      • S_x = n*x + (n*(n+1))/2 = S_2n [ just the sum of all numbers ]
      • After solving the equation minimum sum possible => x = (3n + 3)/2;
      • Then just try to construct pairs with sum x, x+1, x+2, ..., x+n-1.
      • Hope this helps.
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

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

is that a pattern finding round?

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

Mo

Starting with problems A Motivation 100 to 50 B Motivation 50 to -100 C Motivation -100 to +50 Depression enters :)

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

How to solve E? Is this some dp? maybe we can precompute the maximum index, i can jump to from index j while keeping the sum of elements from i to j >= 0 . Am i thinking in the right direction ?

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

    no you need to solve A+B first

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

    I thought of doing a segment dp like:

    dp[L][R][0] — ans for [L; R]

    dp[L][R][1] — ans for (L;R]

    dp[L][R][2] — ans for [L;R)

    dp[L][R][3] — ans for (L; R)

    But had some troubles with calculating dp[L][R][0]. Other states are easy to calculate

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

Might be an unpopular opinion, but I think all problems were very good and interesting. Congrats to the authors for a beautiful contest. I enjoyed doing the contest very much. Thanks!

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

Did someone constantly get wrong answers on problem B?

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

    it's me, huh! My final ratings will be negative. But next contest, i will gonna hit harder..

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

    You probably converted the number to string and left a leading zero on during the output (not converting it back to int). It would fail for 101, where you would output 01 and 100. Just my guess. You would have to delete all the leading zeroes instead of just the first one

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

How to solve C?

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

How to solve B?

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

    Distribute digit by digit.

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

    Divide n into 2 numbers evenly. One number may be 1 greater than the other. Compare the 2 numbers digit by digit. The digits are either (1) same, (2) 1 vs 0, or (3) 0 vs 9. Keep track of the sum of digits of the 2 numbers so far. In case 3 above, distribute the 9 as 4 and 5 or 5 and 4 depending on the current difference of the sums of digits so far.

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

E looks standard. Can it be solved by dp with d&c?

upd: i think i overcomplicated it

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

    dp[i] = max(dp[i — 1], dp[j] — j + i) while sum(j + 1 ... i) >= 0 (j < i) using map to keep (sum[i], dp[i] — i) increase.

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

C is too hard

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

The difference between C and D was massive.

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

did anyone else also got wrong answer on test 5 in E

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

    yeah me

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

      What was your approach.

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

        I used binary search on previous minimas of sum<=sum[i] if sum[i]<0 for getting subsegment with maximum length ending at i.

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

    Yes, i did the classic dp like LIS but get WA on test 5 don't know why

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

      I know now i forgot about dp[i] = max(dp[i], dp[i — 1])

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

        Hello i am also doing same mistake in other method but not getting ig as i am getting same 126 as answer in test case 5. It will be a great favour if you please look into it

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

I think that this round had very interesting problems with pretty beautiful possible solutions. Thanks for the contest!

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

My solution to problem E:

First, create the prefix sum array $$$p_0 = 0, p_i = a_i + p_{i-1}$$$ and compress it. Let $$$dp_i$$$ denote the best answer for the prefix upto element $$$i$$$. Suppose the last segment we take containing $$$i$$$ goes upto $$$\ell+1$$$ and misses $$$\ell$$$. Then $$$\ell < i$$$ and we must have $$$p_i \geq p_{\ell}$$$, and the best possible answer in this case would be $$$dp_{\ell-1} + (i - \ell)$$$. To efficiently compute these values, create a max segment tree over the compressed $$$p_i$$$ values and each time we compute $$$dp_i$$$ as $$$i$$$ plus the maximum over the segment $$$[0, p_{i}]$$$ in the segment tree and after performing $$$dp_i = \max(dp_i, dp_{i-1})$$$ (in case we don't take $$$i$$$ in the optimum answer) we update the $$$p_{i+1}$$$th location by maximising it with $$$dp_{i} - (i+1)$$$. That's it, done. Overall solution works in $$$\mathcal O(n \log n)$$$.

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

https://www.youtube.com/watch?v=1jbhevleu-Y Copy of Problem B...Do Something

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

ABCforces

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

    how to solve C

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it -9 Vote: I do not like it

      assume consecutive sum of n pairs is : k, k + 1, k + 2, ..., k + n — 1. If u add everything u have k*n + (n — 1)*n / 2. Which should be equal to 2n * (2n + 1) / 2 (sum of 1, 2, ..., 2*n). Equate both terms and you will get k = (3n + 3) / 2. Now figure out the pairing part by yourself, it's not that hard.

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

        Asks for a solution, gets "figure out xyz by yourself, it is not that hard".

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

          Hint: If you cannot figure out the pattern, try to write a brute force solution for small cases.

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

        haha, I did until this step, it's intuitive. I couldn't figure out the pairing part.

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

      I brute forced for n=7 and the find the answer (4,8) (5,9) (6,10) (7,11) (1,12) (2,13) (3,14) then we are done.

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

        hello sir, I am unsure of how to write a brute force algorithm for this question. Do you think you could help me? Thanks.

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

my total score : 390-8*50.. It looks very difficult, was this contest really hard?

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

    It's normal for a new account to solve only the first (or even zero) problem is the first contest. You just need to take more contests to get familar with the process of CF contests.

»
21 month(s) ago, # |
Rev. 13   Vote: I like it +8 Vote: I do not like it

Problem D cost much time for me and I didn't have enough time for E.

2D dynamic programming with 6 different arrays to maintain (RL, RL_sum, LL, LL_sum, LL_cnt, LL_cnt_sum) is too easy to make mistake at some details. I've spent much time to find a bug that I allocated too much space on the stack for 2D arrays (using something like ll RL[n][n], where n=3000) instead of declare them as global variables.

How to solve D
My approach for E (Now it has been accepted)

Update: Now my submission 192969220 has been accepted.

AC code of E
  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    Observe that the answer is equal to the number of adjacent points which moves toward each other.

    We may check every two points $$$x_l,x_r$$$ and count the number of subsets in which $$$x_l$$$ and $$$x_r$$$ are adjacent and move toward each other, which is equal to $$$2$$$ to the power of $$$(L_{l,r}+R_{l,r})$$$, where:

    $$$L_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l<x_l-x_p$$$;

    $$$R_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l\le x_p-x_r$$$.

    for a fixed $$$l$$$, $$$f(i)=L_{l,i}$$$ is monotonic. Similar for $$$R$$$.

    The code for the solution above is very easy to implement.

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

      [deleted]

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

      Why are you not considering point which can possibly lie in between xl & xr in the subset? For ex: If x[]={1,13,14,20} and if l=1 & r=4, then by your soln ans would be 1 ({1,20} would be the only such subset), however there could be one more subset ({1,13,14,20}) as well, here also 1 and 20 would meet each other.

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

        for {1,13,14,20}, although 1 and 20 meet each other, they end up in the same place as 13 and 14's. So it is calculated when l=2 and r=3.

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

          Ok, so when two particles collide, they just stop there. I thought that the colliding ones just disappear!

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

        It's the sum over all $$$(l,r)$$$ such that $$$x_l$$$ and $$$x_r$$$ meet each other and are adjacent.

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

      Same approach. It is a miracle that this came to my mind during the time of contest. Finally i can see some improvement.

      Thanks to this contest i reached specialist rating.

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

    I didnt use DP. I just iterated over every pair $$$(i,j)$$$ and found the number of subsets of points such that $$$i$$$ and $$$j$$$ meet each other. The idea and code are both simple.

    Code for D
    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Excellent solution. Comparing to yours, my solution can even be regarded as wrong answer.

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

      I see that you've used this header file #include <atcoder/modint>

      Is it supported in codeforces?

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

        No, it is only available in Atcoder, not in codeforces. My actual submission looks like this

        But the AtCoder Library GitHub repo provides a python script that takes a C++ file and replaces the atcoder header file with the atcoder library, enabling it to submit to all platforms. I also use the VSCode extension called CodePal which automates this process.

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

    Can you please explain your dp approach for D . I tried doing this by dp but failed and my obervation skills suck , hence wasnt able to do the question the other way too.

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

      We consider what would happen if we add a new dot at right. We call the previous 2 right-most dots i, j (assume there's >=3 dots in the set, because set with only 2 dots is trivial). In the previous set j would move left since it's right-most dot, and i could move left or right. If j still move left after we add a new dot, the number of final points will not increase. But if j move right, there's 2 situations: if i moves left (we call this situation LL), then it would like RR...LL --> RR...LRL, we can see there's one more final point (by the "RL" we've created), and if i moves right (we call this situation RL), then it would like RL --> RRL, where number of final points remained same. Therefore we can get the transition formula. (don't forget to consider situations of RL when there's only 2 dots in the set)

      Also this DP approach need to store prefix sums for optimization. See this comment for a simpler solution.

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

Was D just a DP on pos[previous][current] then looping through [current+1, n) to try placing the next particle?

The observation there I believe is that for all values <= a[i] + (a[i] — a[p]), the direction is left, while the rest are right, so you can do some casework there to add on that subarray after precomputing prefix sums (the number of dots is equal to the number of adjacent RL's that show up in the final subsequence), but I had a stroke implementing ;-; does anybody have a simple enough implementation of that idea?

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

    Wouldn't this be $$$n^3$$$ ? Each of your $$$O(n^2)$$$ values take some $$$O(n)$$$ time unless there is a trick I am missing.

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

      I couldn't even get the n^3 working cuz I'm bad but I think that the recurrence would look like


      for j in range(i+1, n): if (P is closer to I than J): // place an L in this case DP += solve(i, j) //(if previous was R, then add 1, otherwise don't add) else: // place an R in this case DP += solve(i, j) (never add in this case)

      Then since every single transition is just solve(i, j) + (a bool) in either case, then you split it up into the ranges whether the bool is true or false with bsearch. The second range never gets added to, and the first range you would casework and then multiply by the length of that range.

      So in the end the transition is DP += (sum of everything from DP(i, [j+1, n) )) + (len of good range) * (caseworked boolean)

      (though again I didn't get the casework working so I'll still need to work out the conditions)

      Though it seems like other people had easier solutions ;-;

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

    had a similar observation but could not come up with the implementation ;(

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

    I have a simpler approach, iterate over i,j (i<j), for every i,j find out a,b such that a<=i,j<b and if every element between [a,b) is not present in a subsequence (except i,j) then $$$a_i$$$ moves towards $$$a_j$$$ and vice versa. Also, $$$b-a$$$ should be minimum so that we exclude minimum elements. Now add $$$2^{n-(b-a)}$$$ to the answer.

    Code: 192957360

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

    Let's assign directions to the dots in some subset, they will look like:

    (RR...RRLL...LL)|(RR...RRLL...LL)|......|(RR...RRLL...LL)

    So the number of distinct endpoints is the number of "LR" adjacent pairs + 1 (to account for the first block). So we can iterate on every pair $$$(i,j)$$$ and count in how many subsets they can exist as an adjacent LR pair.

    Based on $$$x[j]-x[i]$$$, we can know how many dots before $$$i$$$ can be directly before $$$i$$$ in a subset and how many dots after $$$j$$$ can be directly after $$$j$$$ in a subset. If $$$[l, i-1]$$$ is the left range and $$$[j+1, r]$$$ is the right range, then the left subset counts can be $$$2^{l-1}$$$, $$$2^l$$$, ..., $$$2^{i-2}$$$, and the right subset counts can be $$$2^{n-r}$$$, $$$2^{n-r+1}$$$, ..., $$$2^{n-j-1}$$$.

    So, add $$$(2^{l-1}+2^l+...+2^{i-2})\cdot (2^{n-r}+2^{n-r+1}+...+2^{n-j-1})$$$ to $$$ans$$$. Make sure to initiate $$$ans$$$ with $$$2^n-n-1$$$ to account for the first block in all the subsets.

    Submission

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

B was much more difficult than C In B only case we need to worry about is n%20==19 but even after that it was more of implementation problem than maths which it seemed to be initially

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

    you can solve B with binary search

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

      Could you tell how please?

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

    Since the guy with more elo literally posted the same answer as mine and my comment is being ignored because of it, I might as well just remove it.

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

      you're too sensitive for these things

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

        Yes I am, because it's happened before. Good thing it was a 5 minutes comment and not a full editorial.

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

    $$$B$$$ can be implemented simpler. Iterate over digits. If digit is even, split it equally for both answers. If digit $$$x$$$ is odd, add $$$x / 2$$$ to first answer, $$$x / 2 + 1$$$ to second answer and then swap them.

    At the end remove leading zeros.

    Example: 16934 -> 1**** + 0**** -> 13*** + 03*** -> 035** + 134** -> 1342* + 0351* -> 13422 + 03512

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

Feels like massive cheating on C, I might be wrong but it feels like it.

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

    Cheating is happening too much nowadays..

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

    i guess it is for both B and C, B was much harder than c

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

      In what universe is B harder than C, only if you cheated cause code might be more trivial for C. To figure out idea for B it takes less than 50 seconds.

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

What is test 2 for B?

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

    i think it could be 100,1000,10000 etc

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

      i think its easy to guess for these nos n/2,n/2=> {50,50},{500,500}....

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

guessforces

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

Any proof for C I solved it by just some observations

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

    if n is even then "NO". else sum of first pair should be (3*(n+1)/2). proof: S1 + (S1+1) + (S1+2) + ....... + (s1+n-1) = 2n*(2n+1)/2

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

The worst round

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

    I also wanna say this... but to be honest the problems are fine and I'm just unlucky.

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

    For me too :(

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

    why? D was alright but maybe D > E. I guess A,B were easier than usual for sure.

»
21 month(s) ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

Imagine asking how to solve D and getting -13 ^D

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

It was great PatternForces Round <3

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

I wish C was 1500-1600, but unfortunately it's more likely to be 1200

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

Anyone know why my sol for D is wrong?

dp[i] stands for sum where i is chosen, and tot[i] is total of chosen & not chosen

dp[0] = 1;
tot[0] = 1;
for (int i = 1; i < n; i++) {
	dp[i] = 1;
	for (int j = 0; j < i; j++) {
		if (j == 0) {
			dp[i] = (dp[i] + 1) % mod;
		} else if (x[i] - x[j] < x[j] - x[j - 1]) {
			dp[i] = ((dp[i] + tot[j - 1]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod;
		} else {
			dp[i] = ((dp[i] + dp[j]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod;
		}
	}
	tot[i] = (tot[i - 1] + dp[i]) % mod;
}
cout << (tot[n - 1] - n + mod) % mod << '\n';
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

I wast stuck in problem C for approximately 2 hours, In problem C multiple kind of pairing was possible so it must be mentioned in the question that we can output any valid answer. I am not talking about order of pairs... actually you can pair any number with 2 values and accordingly I found 2 valid answer exists for each odd number.

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

Any Hints For D? I Was Thinking In A DP Direction :(

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

    the main observation is that the distinct points increase when $$$ith$$$ index moves left and $$$i+1th$$$ index moves right. Now try to figure out the contribution of each $$$i$$$ seperately by fixing the position that moves left and the position that moves right.

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

Toooooooooooooo much Cheating

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

Can anyone explain E for noobs?

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

Why is answer no for even n in C?

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

    s, s + 1, ..., s + (n — 1) are sums. So s * n + n * (n — 1) / 2 = 2n * (2n — 1) / 2, so s = (3n + 3) / 2 => n % 2 == 1

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

    s, s + 1, -- s + n — 1

    suppose they are sum of pairs as given in problem

    if we put

    s + s + 1 + s + 2 — = 1 + 2 -- 2n

    we get

    n * s + n * (n — 1) / 2 = n * (2n + 1) we get

    s + (n — 1) / 2 = 2n + 1

    s = 3 / 2 * (n + 1)

    for s to be integer n + 1 should be even

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

An unbalanced round. I got ABC very quickly, but couldn't come up with a fast enough solution for D in time and didn't attempt further problems. I won't say that the problems were bad because they weren't (C was just guessing a pattern, didn't like it that much; others were good). I just think that there should've been a 1600-1800 rated problem between C and D. But the round was still nice.

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

    yea, I agree. Maybe A,B,C could've been made slightly harder to ease up the gradient.

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

Actually had more trouble with C than F haha.

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

solved D during the contest, but forgot that modular arithmetic template takes $$$O(\log n)$$$ to calculate $$$2^n$$$... So got TLE couple of minutes before the end after simply rewriting formula I got on paper :(

contest submission: https://codeforces.net/contest/1788/submission/192959799

upsolve submission: https://codeforces.net/contest/1788/submission/192968394

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

Great contest with good problems , thanks!

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

Great contest, and super fast rating changes, wow! Absolutely loved all the problems that I read (A-E)!

Also, while I understand the need to have tight TLs on D, as $$$n^3$$$ solutions were to be rejected, I'm slightly irked by the fact that my Java submission failed despite being $$$n^2log(n)$$$. Anyway, that was to be expected since I was using TreeMaps, and Binary Search is understandably faster. So yeah, happy to have learned one more thing :)

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

Great contest with very clear statements!

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

ok thanks

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

    The product of the array can go up till pow(2,1000) which is way too large to even fit in long long

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

AC submissions at the last second

Ac submissions at the last second is very nice , but i am pretty sure that last second submission of problem D by gsmdfaheem is copied. i have seen exact same code that is leaked at just 10 minutes before the contest end.

he just changed the variable names.

Channel
Leaked-Code
His submission at last second
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

In B if i print 1 as 01 it consider it wrong but both are equivalent integers and no intructions are provided regarding leading zero .

stupid testing got WA 2 times.

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

According to me my E is working but my solution gets WA on test 5 can anyone please help me where i am lagging https://codeforces.net/contest/1788/submission/192944044

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

GOT AC LAST SECOND

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

 D just 3 seconds before!!

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

The time limit of F is too tight. I wrote the correct solution but got TLE on pretest 58. I think it's better to decrease the value of $$$n,q$$$ to 1e5 or increase the tl to maybe 5 secs.

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

Problems are fun! thanks to authors :)

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

Can someone give a small test case on which my solution 192923926 fails?

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

Very very very standard problem E and F. I cannot accept that.

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

Weak testcase in B no. In the statement, given 1<=n<=1e9. Unconciously, I used int(as datatype) and passed the pretest. After the contest I noticed my mistake and expected to get wrong answer. But, after final judgement , my solution passed all the testcase :)

192907426

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

    What do you think range int has in GNU C++17 7.3.0 (your used compiler)?

    You can always check in Custom Invocation smth like this:

    #include <limits>
    #include <iostream>
    
    using namespace std;
    
    int main() {
        using IntLimits = numeric_limits<int>;
        cout << IntLimits::min() << ' ' << IntLimits::max() << endl;
        return 0;
    }
    
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest! you can find the video editorials for problem C and D here .

hope this helps you! happy coding!

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

Hello! I submitted two implementations of treap in E, and the "faster" version works 5 times longer! Can anyone explain it? "slower": 193052447 "faster": 193052503 I know that "faster" gets TL on a test with a = {0, 0, 0, ..., 0}, but I can't realize the reason of O(n) height of a treap.

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

hopeforces

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

Problem B. Sum of Two Numbers ***** my solution get wrong answer on test case 8, my solution is true and that makes me sure that I take this code copy and submit it again and get accepted, plz check it for my. the solution which gets wrong answer during the contest the same solution gets accepted after the contest !!!

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

Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.

In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540

[user:KAN][user:MikeMirzayanov][user:azberjibiou]