azberjibiou's blog

By azberjibiou, history, 14 months 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 Feb/09/2023 17:35 (Moscow time).

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?
»
14 months 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).

»
14 months 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).

»
14 months ago, # |
  Vote: I like it -39 Vote: I do not like it

as a tester, qwexd ORZZZZ

»
14 months 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!

»
14 months 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!

»
14 months ago, # |
  Vote: I like it -30 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

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

    • »
      »
      »
      14 months 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]

»
14 months 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

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

Good luck to everyone!!!

»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Good Luck for every Candidate Master to promote to Master!

»
14 months ago, # |
  Vote: I like it +35 Vote: I do not like it

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

  • »
    »
    14 months 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!

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

      hahaha haha hahaha haha hahaha haha :(

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

    Haha nicely predicted.

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Omg announcement shorter than tourist round

»
14 months 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.

»
14 months ago, # |
Rev. 4   Vote: I like it -19 Vote: I do not like it

good luck everyone!

»
14 months 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!

»
14 months 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 .

»
14 months 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.

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

As a participant, I confirm that i will participate.

»
14 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Sometimes I really want to skip school.

»
14 months ago, # |
  Vote: I like it -85 Vote: I do not like it

Please down me, thx.

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

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

»
14 months 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 !

»
14 months 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).

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

Good Luck and Have Fun!

»
14 months 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

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

Wishing you all a positive delta!!

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Best wishes for everyone

»
14 months ago, # |
  Vote: I like it -55 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Me after solving C

Waiting for contest to end
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Same lol

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

    Can you please tell your approach on C?

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

    same

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

is that a pattern finding round?

»
14 months 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 :)

»
14 months 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 ?

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

    no you need to solve A+B first

  • »
    »
    14 months 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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Spoiler
»
14 months 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!

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

Did someone constantly get wrong answers on problem B?

  • »
    »
    14 months 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..

  • »
    »
    14 months 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

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

How to solve C?

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

How to solve B?

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

    Distribute digit by digit.

  • »
    »
    14 months 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.

»
14 months 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

  • »
    »
    14 months 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.

»
14 months ago, # |
  Vote: I like it +46 Vote: I do not like it

C is too hard

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

The difference between C and D was massive.

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

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

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

    yeah me

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

      What was your approach.

      • »
        »
        »
        »
        14 months 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.

  • »
    »
    14 months 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

    • »
      »
      »
      14 months 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])

      • »
        »
        »
        »
        14 months 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

»
14 months 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!

»
14 months 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)$$$.

»
14 months 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

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

ABCforces

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

    how to solve C

    • »
      »
      »
      14 months 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.

      • »
        »
        »
        »
        14 months 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".

        • »
          »
          »
          »
          »
          14 months 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.

      • »
        »
        »
        »
        14 months 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.

    • »
      »
      »
      14 months 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.

      • »
        »
        »
        »
        14 months 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.

»
14 months 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?

  • »
    »
    14 months 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.

»
14 months 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
  • »
    »
    14 months 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.

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

      [deleted]

    • »
      »
      »
      14 months 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.

      • »
        »
        »
        »
        14 months 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.

        • »
          »
          »
          »
          »
          14 months 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!

      • »
        »
        »
        »
        14 months 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.

    • »
      »
      »
      14 months 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.

  • »
    »
    14 months 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
    • »
      »
      »
      14 months 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.

    • »
      »
      »
      14 months 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?

      • »
        »
        »
        »
        14 months 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.

  • »
    »
    14 months 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.

    • »
      »
      »
      14 months 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.

»
14 months 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?

  • »
    »
    14 months 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.

    • »
      »
      »
      14 months 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 ;-;

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

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

  • »
    »
    14 months 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

  • »
    »
    14 months 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

»
14 months 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

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

    you can solve B with binary search

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

      Could you tell how please?

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        code
  • »
    »
    14 months 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.

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

      you're too sensitive for these things

      • »
        »
        »
        »
        14 months 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.

  • »
    »
    14 months 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

»
14 months 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.

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

    Cheating is happening too much nowadays..

  • »
    »
    14 months 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

    • »
      »
      »
      14 months 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.

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

What is test 2 for B?

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

guessforces

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

Any proof for C I solved it by just some observations

  • »
    »
    14 months 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

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

The worst round

  • »
    »
    14 months 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.

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

    For me too :(

  • »
    »
    14 months 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.

»
14 months ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

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

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

It was great PatternForces Round <3

»
14 months 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

»
14 months 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';
»
14 months 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.

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

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

  • »
    »
    14 months 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.

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Toooooooooooooo much Cheating

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

Can anyone explain E for noobs?

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is answer no for even n in C?

  • »
    »
    14 months 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

  • »
    »
    14 months 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

»
14 months 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.

  • »
    »
    14 months 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.

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

Actually had more trouble with C than F haha.

»
14 months 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.com/contest/1788/submission/192959799

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

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest with good problems , thanks!

»
14 months 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 :)

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

Great contest with very clear statements!

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

ok thanks

  • »
    »
    14 months 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

»
14 months 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
»
14 months 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.

»
14 months 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.com/contest/1788/submission/192944044

»
14 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

 D just 3 seconds before!!

»
14 months 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.

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

Problems are fun! thanks to authors :)

»
14 months 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?

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

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

»
14 months 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

  • »
    »
    14 months 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;
    }
    
»
14 months 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!

»
14 months 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.

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

hopeforces

»
14 months 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]