maomao90's blog

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
By maomao90, history, 12 months ago, In English

Hello Codeforces,

We are very glad to invite you to participate in CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Nov/25/2023 17:50 (Moscow time). You will be given 8 problems and 2.5 hours to solve them. The round will be rated for everyone.

All the problems are written and prepared by lanhf, Mike4235, thenymphsofdelphi, xuanquang1999 and me.

We would like to give our sincere thanks to:

The score distribution is $$$500-1000-1500-2000-2250-2750-3250-(4000+1000)$$$.

Hope everyone can enjoy the round!

Congratulations to the winners!

  1. Radewoosh
  2. ksun48
  3. ecnerwala
  4. maroonrk
  5. jqdai0815
  6. hos.lyric
  7. zh0ukangyang
  8. 244mhq
  9. Vercingetorix
  10. BigYellowDuck

Congratulations to the first solves as well!

UPD1: The contest is delayed by 15 minutes due to prior issues with the registration system in order to make sure everyone is correctly registered. Please double-check that you are registered.

UPD2: Editorial

And here is the information from our title sponsor:

Hello, Codeforces!

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

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

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

The winners of CodeTON Round 7 will receive valuable prizes.

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

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

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

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

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

As a tester, i know, that problems are interesting and the round itself is exciting

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

    That's what they all say

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

    As a newbie...i was completed 1st two problem in 23 minute and then after 2+ hours i'm trying to solve problem C. But, i can't . Anyway, It's 1st time 1 complete 2 problem in div. 2. Thanks all writer and tester...!

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

      Thanks to you for participating!

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

      i am also tracked in problem C in div.2 for many times. often their solution are greedy... it is a little hard to construct a methed and prove its validity.

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

As a contribution, please give me tester

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

As a specialist, I miss my Expert color when I tested this round ;(

Anyways, problems are very interesting; you should read all problems' statements.

Good luck ;)

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

Do I get TON

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

Why there's no 1,024-2047 places: 1 TON each?

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

@everyone announcement is posted https://codeforces.net/blog/entry/122539. Can farm contribution if you want

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

As a tester, I forgot the problems. But they were enjoyable I remember.

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

-1024 TON

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

As a tester I can guarantee that the problems are good

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

    How do u become a tester? Do they reach out to you or do you apply to be a tester?

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

      I know the creator personally but you can randomly be invited to test

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

good luck & fun !!!

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

Good luckkkkkkkkkkkkkkkkkkkkk

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

But I did not get the prize of round 6 (xd

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

The main writer when you cannot solve the problems.

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

18o3 the 'TESTER' ::orangeheart::

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

as a participant, increase TON

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

I hope to win the money for two KFC-Crazy-Thursday!

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

I hope to win the money , I need to take care of my family.

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

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

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

What's TON?If I get the prize,how can I turn the TON into common money?

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

Hope i'll became pupil after this contest ...!

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

:(

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

Good luck to all the participants, do your best ^_^

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

Why are you wasting time testing Codeforces round Yoo_Jeongyeon! We were waiting for TW-LOG @ 5TH WORLD TOUR ‘READY TO BE’ ep.JEONGYEON

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

will the rate updated before the upcoming codeton contest lol

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

    The previous contest has become unrated I guess.

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

      Definitely not, unless I missed some announcement that said that. Sometimes ratings just take a long time to update.

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

What does 4000+1000 score mean?

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

    That problem (problem H) has two versions H1 and H2: an easier version and a harder version. Solving the easier version gives $$$4000$$$ points, solving the harder one gives $$$1000$$$ points. It might seem really stupid: why does the harder version give less points? The reason is that almost always the solution to the harder version directly solves the easier version (you can submit the same code to both and get AC). Thus, solving the harder version effectively gives $$$5000$$$ points, i.e. it is only slightly more difficult than the easier version.

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

Wow, split H?

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

Good luck

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

one refresh cost me 15 minutes

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

Please let me reach Pupil today

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

DelayForces

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

Delayed agaaaaaaaaaaaain... Okay I'll have to go to sleep 15 min later...

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

Hope to become a pupil today

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

now its gonna be 1:30 AM for me when it ends :skull:

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

guessforces.

$$$1$$$. Guess the answer. $$$2$$$. Guess the answer $$$3$$$ Guess the construction.

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

    There was no guessing involved wdym.

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

    Just to be sure, do we need to use segment tree in D?

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

      No, set plus some annoying math and casework is enough

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

        please elaborate?

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

          The rough idea is that you maintain indices of ones and twos, then you consider the first 1, if sum to the right including it is at least x it is possible. Otherwise we need to include the twos to the left, so you try to get the max sum starting from the first 1 with the same parity as x by removing the suffix of twos, and a one.

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

        What annoying math and what casework

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

          Okay, it’s not that bad, it can surely be done more elegantly. But my solution was quite casework-based because… don’t know why.

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

      No XD

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

      Nope, can be done with a regular set.

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

        Oh, yeah, right, to maintain first and last positions of '1'?

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

          Yes and a heap (priority queue) is even faster

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

            Thanks, i actually wasn't sure which data structure could deal with this

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

      segment tree also works you have to find the prefix sum just less than the given sum it can be done using bs on segment tree and then you just have to think how you can increase the subarray sum by 1

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

    Man what about Problem-D .....xD. Any approach?

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

Nice problem set.Enjoyed the problems!!!

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

Very nice contest! First time ever doing 5 questions in a div 2!

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

Sorry for weak tests on B :(

Hope everyone still enjoyed the round!

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

How to solve C? greedy only gives best possible x, but how to get exactly x?

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

    Still gready. Sort b and cyclically shift it to the left by X. So you get a gready answer for sorted a. Then "unsort" b by 'a' and check answer is ok.

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

      It worked but still can't understand why shifting to left works, Are we garunteed to get a new ai > bi on every shift? (assuming there is an answer).

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

        Yes, it's tricky. But intuition is simple. Lets consider some worst case after shift (x = 3):

        a = 1 2 3 | 5 6 7

        b = 7 8 9 | 4 5 6

        As we can see, if answer is exists and a is sorted, b must be also sorted.

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

          Thanks, I understand now. So to put it in words : for the current smallest element of ai the best current answer is next maximum of bi, and at some point in the middle if this condition doesn't hold that's because there are not enough elements on b that can satisfy the smallest elements of a so no solution.

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

Can someone please explain to me why this solution is not correct for problem D. My idea is if there is a prefix sum that is equal to the queried sum, then print yes, otherwise check if there exists an element with value one at which the prefix sum is greater than the queried sum, and if it exists the answer is yes, otherwise no.

Submission: 234308986

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

    I have not seen your code, it's looks quite complex to be honest, but based on your idea, Isn't answer of this Test Case is No, but should be YES

    Array : 1 2 2

    queried sum : 4

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

Thanks for the great round! Could someone please share the implementation/approach to D?

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

    Store the positions of $$$1$$$ s in the array in a set. Now calculate the maximum even and odd subarray sum you can get.

    If the whole array has an even sum, the maximum even subarray sum is just this sum. To find the maximum odd subarray sum, we need to remove a single $$$1$$$ from the array. From the first and last $$$1$$$ s, find which one is closer to the edge of the array and remove it along with any $$$2$$$ s between it and the end of the matrix.

    You can get similar results for if the whole array has an odd sum, and need to recompute these maximum odd and even subarray sums each time an element is updated. Then when we get a subarray sum query, check if its less than the maximum of corresponding parity.

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

    First, store the positions of all 1's in a set. Then you can retrieve first and last 1's easily. For the first 1, there will be only 2's before it, and for the last 1, there will only be 2's after it. Let l be the position of the first 1, and r be the position of the last 1. For any prefix ending with a 1, you can get all elements from 1 to the sum of the prefix, and for any suffix ending in 1 you can do the same. You can also add the 2's before and after the suffix and prefix, respectively. So for a query, you only need to check if either x is less than this suffix and prefix sum, or that it is a multiple of two(which is less than the total number of twos before or after l or r) above the suffix or prefix sum. Handle prefix/suffixes with a segment/fenwick tree. Updates queries can then be done easily.

    Implementation

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

Nice problems. It would have been better if samples for C could cut wrong output format. I was printing b according to sorted a. I proved my solution but could not figure out anything for too much time.

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

    Same man same! Wasted more than 30 minutes in it.

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

Very interesting H! I think I was pretty close to something like $$$\mathcal{O}(4^k)$$$ solution, but couldn't finish it

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

C>>>D

→ Reply
»
12 months ago, # |
← Rev. 8   Vote: I like it +60 Vote: I do not like it

A. Note that if a[1]==1, we will always be able to do some operation if the permutation is not sorted (consider minimum i such that a[i]>a[i+1], because a[1]==1 we have i>1), and each operation will decrease the inversion number of it, so the answer is YES. Otherwise, since we cannot change a[1] by operations, the answer is NO.

B. Consider the beginning B's and ending A's of the string, they can't be moved. So we can ignore them and assume the string begin with 'A' and end with 'B', then the string will be like this: "ABBB | AB | ABBBB | ... | AB", and if we process "ABB...BBB" blocks from right to left (and move 'A' from left to right in each block), we can get ans=len(s)-1.

C. We can assume a[i] is sorted. When we need to choose x indexes such that a[i]>b[i], and choose n-x indexes such that a[i]<=b[i], we need to choose large a[i] and small b[i] for the first type, small a[i] and large b[i] for the second type. So we can assume that a[i]<=b[i] for 1<=i<=n-x, and a[i]>b[i] for n-x+1<=i<=n. Then we need choose x smallest values of b[i] to fill the range [n-x+1, n], and n-x largest values of b[i] to fill range [1, n-x]. To satisfy the inequalities as more as possible, these values also need to be sorted within two ranges. Finally we need to check if the answer we build is valid.

D. If we maintain the total sum T of the array, if s>T the answer is no. Let's assume that s<T for remaining part. Notice that if a[1]==1, all integers in [0, T] are valid, because there must be some i such that sum[1, i]=s or sum[1, i]=s+1, and for the second situation, we have that sum[2, i]=s. For the general cases, Let's assume there are k1 occurences of 2 before the first occurence of 1, and k2 occurences of 2 after the last occurence of 1. (So a[i] is something like " I1: 22222...2 | I2: 1.....1 | I3: 2...2222") Let r=T-2*(k1+k2) be the sum of I2, then similar with cases for a[1]=1, all integers in [0, r+2*max(k1,k2)] are valid (think about subarray I2+I3 or the inverse of I1+I2), and if s>r+2*max(k1,k2), I2 must be contained in the subarray we need (for any subarray doesn't contain I2, it will be contained in I1+I2 or I2+I3), Then we have (s-r) must be even. We can find k1 and k2 by maintaining a set of indexes such that a[i]==1.

E. For each i we let range T[i]=[i, a[i]], then the answer of a[i] will be (a[i]-i)%n — (the number of other ranges contained in T[i]), and we can calculate tha number of ranges by fenwick tree.

F. If sum of s[i] is odd or s[1]!=s[2*n] there's no solution. Otherwise, we can solve the problem in 3 operations. First, Let's ignore s[1], s[2*n] and look about s[2, 2*n-1]. For each even i in [2, 2*n-2], if s[i]==s[i+1], we put "()" on corresponding positions of b, Otherwise we put "((" or "))" instead (because sum of s[i] is even, there will be even occurences of such i, so we can choose "((" for first half and "))" for second half) Then we let b[1]='(', b[2*n]=')' and do the first operation. After that, for all even i in [2, 2*n-2], we have s[i]==s[i+1]. In the second operation, b[1] and b[2*n] are the same with first operation, and we put "()" for 00 and ")(" for 11 this time. Then for all 2<=i<=2*n-1, we have s[i]==0. If s[1]==0, we are done. Otherwise we need the third operation for b="(()()()...())".

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

    Thanks :D

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

    How can we calculate the number of ranges inside a range using fenwick tree?

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

    In problem E, can you please elaborate on how to calculate the number of ranges contained inside T[i].

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

      First, these ranges are considerd circular, which means for [L, R] when R<L, this range is the union of [L, n] and [1, R]. To solve this issue we can turn in into [L, R+n], and for any other range [L2, R2], if L2<=R2, then we check if [L, R+n] contains [L2, R2] or [L2+n, R2+n] (they can't both be contained), and if R2<L2, we check if [L, R+n] contains [L2, R2+n].

      Then we turned the problem into this: There are some pairs of (l[i], r[i]), we have some queries in form (L, R), find number of i such that L<=l[i]<=r[i]<=R.

      We can solve it by offline: Sort queries by L, and for a certain i, we add 1 to r[i] on time 1, and minus 1 to r[i] on time l[i]+1. Therefore, we add 1 to r[i] between time 1 and l[i]. Then for query (L, R), we find the prefix sum on [1, R] on time L, which will be the answer of the query.

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

    Thanks :) its really helpful

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

What is E idea?

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

    You can represent the distance from where a number is and a number should be as segments. Then you need to count for each segment, the number of other segments which it completely overlaps.

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

      why completely isn't enough to be an intersecting

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

In problem D can I use segTree to solve it?

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

Nice problems. Thanks for the round!

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

Nice Contest <3

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

I can't submit E now, so can someone confirm, is it just using ordered set for any index $$$i$$$, to find number of elements that will remain at the same time, when $$$i$$$ will be fixed. We will sort the ranges of {curr_idx, right_idx} by right_idx.

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

    Yes, that's what I did at least

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

      Oh no, I took much time to realize it (>...<)

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

    You can use BIT instead of ordered_set also

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

      Yeah, I would've gone for BIT if OS hadn't fit in TL.

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

in c, i was thinking about finding upper bound for the numbers in array a for the bi and swap it , and check whether we can get x combinations or not, can we solve it like that

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

Are rating changes from last Educational going to matter on the new rating calculation? I ask because the ratings were updated almost at the begining of the contest and codeforces bot is not taking care of that at least for me

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

Choked on G and lost 64 TONs.

Super cool contest, interesting ad-hoc problem F&G.

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

    Super cool F indeed! Can you share your solution of G?

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

      Divide $$$n^2$$$ numbers into $$$n$$$ groups.

      Repeating Following Steps:

      • Find the maximum in each group
      • Find the maximum of the maximums and take it.
      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did a spaghetti implementation, I get MLE and I can't replicate it with a non-adaptive grader :(

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

nice contest. can somebody ask my teacher not to take online classes during contest?:|

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

What is solution for E?

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

    If you consider cyclic subarray i,...,a[i]. Then ans[a[i]] is going to be the number of elements which you push out of this subarray because each operation pushes 1 element out of this subarray.

    An easier implementation would be subtract number of elements which does not need to be pushed from total elements like this

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

problem F is very cool!

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

What's wrong in this submission of D- 234302167

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

Thanks ! It's my first time becoming a candidate master and geting tons!

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

Woah, it seems I massively overcomplicated my solution to E.

I take the permutation and make a $$$2n$$$-element array $$$p'$$$ which is just the permutation repeated twice with all the "arrows" from the first $$$n$$$ elements pointing right instead of left. Then I take that array as the leaves of a segment tree where each node is a sorted vector of its segment's elements. (So it's just like the tree you'd get from a merge sort). Then for each element of the permutation I can range-query in $$$O(\log^2 n)$$$ for the number of elements in the segment $$$[i, p'_i]$$$ that are greater than $$$p'_i$$$ using binsearch, which is exactly the time it will take for the $$$i$$$-th element to get to its place. This yields a $$$O(q \log^2 n)$$$ solution with $$$O(n \log n)$$$ memory, but with too big of a constant on the memory complexity. This got me a MLE.

So instead of holding the entire mergesort tree in memory I first make "phantom" queries into a segment tree and for every node remember which queries use it. Then the mergesort doesn't have to persist vectors at every level of the recursion, instead partially answering each query on the node it is in. Neither the time nor the memory complexity change, but with a better constant this got AC.

Also it's funny how I basically immediately got the idea for how to solve E while not being able to solve D at all. But it seems I'm the weird one and the order of the problems was chosen well :P

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

Ka-chow!

About problems:

I love H.

G is nice+. I don’t know if $$$2n^2-n+1$$$ wouldn’t be nicer, but I guess that’s what makes the problem hard, so I guess $$$2n^2-2n+1$$$ is a good decision.

The rest is good as there’s mostly nice thinking instead of coding, but no 0-coding. Maybe F is so-so, as it’s really a pattern made on paper, but it’s not that bad too.

Is E linear? Or is $$$n$$$ up to million because you were afraid of quadratic solutions? Anyway if high limits caused no problems (I got a bit scared, but time didn’t really grow during systests, so that’s nice) then everything is fine. It’s fine if the solution is linear too ofc.

Good problemset in general, definitely enjoyed!

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

    Congrats on solving all the problems.

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

    Congrats on #1!

    I also enjoyed G and H, though G ended up being too hard for me. :)

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

    Yes its because $$$O(n^2)$$$ ran super quickly so I had to make $$$n$$$ bigger. I doubt there are any linear solutions.

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

Seems like the test set is not strong enough for problem F. Some greedy solutions got accepted by doing something like this: let's make up another bracket sequence until there are no 1s left in the original string, and while composing the new sequence from left to right, we will try to eliminate another 1 if it is possible. Here is my implementation: 234305022.

There are also greedy solutions that do some sortings instead but I'm not sure. Maybe someone can share the details.

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

How could I get the prize? I won 2 TON according to the rules.

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

First time ever to solve a DIV2 problem C and became pupil after the contest. love this round:)

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

Link to my screencast and editorial of A, B, C, D, F.

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

A-F speedrun sub-1hr hitless

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

I solved problem 1896D - Единицы и двойки with std::bitset in time $$$O\left(\dfrac{n \times q}{64}\right)$$$ during the contest. My accepted submission works 1248 ms.

Here are some hints how to keep and update a set of prefix sums with bitset:

  • bitset[s] is equal to $$$1$$$, if there is a prefix sum with value s, and 0 otherwise;
  • the number of segments with sum equal to s can be calculated with (bitset & (bitset << s)).count();
  • the update of $$$i$$$-th value in array by some delta can be implemented with bitset = (bitset >> s[i] << (s[i] + delta)) | (pref << (size - s[i]) >> (size - s[i])).

Remember, that bitset >> K << K sets to zero first K elements without changing of other elements and bitset << K >> K sets to zero last K elements.

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

Why am I getting RTE on pretest 1 when it works on my IDE? Thanks!

234307252

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

Why I can't see the Editorial? When I click the "Editorial", it just tell me "You are not allowed to view the requested page".

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

Can anyone of you help me find out why this submission for C is wrong. https://codeforces.net/contest/1896/submission/234350576.

Thanks in advance!!

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

dude i overthought A too hard...

I just made algorithms and algorithms for B until one worked. This one just kinda popped into my head when I was thinking of another idea...

I did B then couldn't think of a solution for A C or D...

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

Im_dik from Chongqing defeated the famous Legendary Grandmaster Um_nik in last Educational Codeforces Round.But we didn't see their duel again in yesterday's contest.It's so disappointing!

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

    He is a tester. Do you think this is fun?

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

As a newbie really interested the round

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

Will I receive TON if I registered a wallet after the end of the contest? Also thanks for the round.

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

How do I get TON? I just created a wallet

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

Hi codeforces, how i can get my codetoins?

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

An explanation of how my code for E in this round is similar to Akamu's code.

We did not communicate about E during the competition, but the code of question E is similar Akamu and I are friends, and three days before the competition, I wrote a problem with him when we learned the problem of statistics under the condition of two-dimensional partial order, which was basically the same as the solution of problem E.

https://www.luogu.com.cn/problem/P2163 Here is the title link for that question. https://www.luogu.com.cn/record/136243512 This is my submission record when I wrote this topic. In addition to clicking the link, you can also search for the submission record of dreamjoker2023 in Luogu and LuoguP2163 (you need to log in and pass this question to view the code by link). This submission was made on 2023-11-21. It can be proved that the code we used this time came from before the competition, and the code of LuoguP2163 is similar to the code of E. Since non-users of this site cannot directly view the code in the submission link, the administrator who needs to verify the authenticity of this record can send me a private message and I will provide my Luogu account number to prove that it is true.

It can be noted that the solutions and codes of the two problems are very similar, and the time we wrote the two problems is only three days apart. Since that problem is a model of this kind of problem, I have provided my code to him by LuoguP2163 on November 21 as a solution template for this type of problem. In this competition, Akamu and I both wanted to pass the E question by modifying the code we used before, so the code was similar.

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

I wonder if the $$$2n^2-2n+1$$$ bound of G is tight. If it is, can anyone please provide a mathematical proof?

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

    I had no proof whatsoever for the bound of G, it was simply the best solution I could think of at the time :) I hope that other people could find out a nontrivial lower bound though!

    → Reply
»
11 months ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

Hello, Codeforces.

I managed to solve 4 problems in this round. However, after the end of the round, the Codeforces verification algorithms considered that my solution https://codeforces.net/contest/1896/submission/234264306 identical to the solution https://codeforces.net/contest/1896/submission/234269475 . Because of this, all my attempts were ignored and the rating was lowered. First of all, I do not know this person. Secondly, his decision is not identical to mine. Thirdly, task C is a fairly simple task, and in my opinion it would be wrong to consider a remotely similar solution to be identical.

Unfortunately, I have no video or other evidence that cheating did not happen. But I hope for an individual review of this comment and a change in the verdict on cheating.

Good luck to everyone!

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

next codeton when

→ Reply