74TrAkToR's blog

Codeforces Round #904 (Div. 2)
By 74TrAkToR, history, 13 months ago, translation, In English

Hello, Codeforces!

I am happy to invite you to my Codeforces Round 904 (Div. 2) which will be held at Oct/22/2023 10:05 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100.

The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.

During the round you will need to solve 5 problems. You will have 2 hours to solve them.

Score distribution: $$$500-1000-1750-2500-3000$$$

We wish you good luck and high rating!

UPD: Editorial

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

Comments Comments (70)
| Write comment?
»
13 months ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester, omg round by coordinator.

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

Why multiple contests on same date ?

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

The problems are very good. Hope you will love solving them. (:3 first time testing)

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

I'll never forget exciting rounds coordinated by you. Hope the round will be fine.

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

Looking at the score distribution this seems like a speed run. Gonna register with the motto Don't participate if you can't dominate.

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

    Looks like the difficulty of problem D is going to be harder than usual

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

      What do these points mean? is there any correlation between points and problem rating?

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

        Generally I have seen Prblm D to be at max of 2000 points, so keeping points high will most probably mean higher difficulty

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

Deleted

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

pshat orz

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

you forgot NOTE THE UNUSUAL STARTING TIME in bold to make people aware

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

Why is the registration for Codeforces Round 905 (Div. 2) saying "Rating should be between 1,600 and 2,099 in order to register for the contest"?

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

I think it's better if you write in the post that only >1600 can register and get rated

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

    This is Round 904. Rated for everyone below 2100. You are talking about Round 905

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

      Yeah but even the registration page of Round 904 says that I'm registering out of competition... probably it's not mentioned properly in the announcement, or it's a bug.

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

Seems like Codeforces Round 905 (Div. 2) gonna be blue-purple war!

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

Why is it said here that the competition will be for rated participants with a rating of no more than 2100, but at registration this is a rated competition for participants with a rating from 1600 to 2099

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

I guess at CFR904 and 905, there will be chaos because of the back-to-back rounds and tricky format of CFR905. So I suggest some unusual rules for them:

  • The rating change of CFR904 won't be updated until CFR905 ends so that avoiding double-register (and getting double-rated mistakenly) for CFR905
  • Everyone is rated by the division in which they registered even if the participant gets division promotion from CFR904.
    • Another choice is to update the rating rapidly and remove double-register before the round starts.
  • Rated participants of Div1 or Div2 of CFR905 should be kicked out from Div3 of CFR905, Otherwise some penalties will be avoidable by submitting their solution for Div3 first.
  • Open hacking is disabled for CFR905(Div3). Only div3 participants get open hacking is unreasonable unless the problemsets are disjoint.
    • Another choice is to introduce open hacking for all 3 rounds. Anyway, I don't like the parallel rounds with different rules without suitable reason.
→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When the registration for division 905 will be open? Usually I get an email with invitation.

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

Why there was said in the announcement that "this round will be rated for all the participants with rating strictly less than 2100.", but there was said in the register page different "You are registering "out of competition", reason: rating should be between 1,600 and 2,099 in order to register for the contest"? I'm getting confused, can anyone help me to figure out it?

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

    There was a mistake on my side setting up the round. Now everyone below 2100 should be able to register as usual. I'm sorry for the inconvenience. We'll automatically change the status of already registered and having rating below 2100 to official contestants before the round, you don't need to do anything.

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

The rating changes for a round are sometimes cancelled and then recalculated, which takes about 1 day.

Round 905 starts just 2 hours after round 904 ends. Consider the following situation.

You participate in round 904, your rating changes, and then you participate in the corresponding division of round 905. After a few hours, rating changes for round 904 are cancelled and recalculated, causing your division to change and meaning you haven't participated in your division of round 905.

The chance of this happening is very small, and it's interesting to know what would happen in this case.

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

Why there are so 2 contests on the same day?

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

    you should guess it bro the reason's really written in both announcements

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

I registered in both 904 (in div 2) and 905 (in div 3). In case, for 904 my rating increased to be >=1600 and rating update happens before start of contest 905 but after registration end time. So in this scenario, will my registration in 905 as div 3 still be considered valid even if my rating now becomes >= 1600. Wont it create any confusion?

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

(13-21) — 9 days 0 contest. (22) — 1 day 4 contest!

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

Why there are 4 contests in one day, and for the next week there's no contests?

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

Hoping to become CM in this contest!Only 9 ratings!

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

It's time to rage(100%)

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

This is my first contest. Can i join it?

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

More suitable for Chinese baby constitution

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

Hats off to US contestants who will join at 00:05 am and 04:00 am today.

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

Nice start to a Sunday afternoon (╥﹏╥)

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

How to solve problem C?

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

      Can you please elaborate the solution for Problem :C ..

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

        lets fix some point P, and make a[P] max, how we can guarantee that it will be max? to do it we can use only segments which are l[i] <= P <= r[i], then find min and max for this.

        we need to do it for every important point, we can find this important points after compression l and r. but it is O(n^2) which is too slow

        lets add and remove segments greedily, and to do -1, 1 operation with lazy segment tree, and find min max also with it, so complexity will be O(nlogn) because we add every segment only once and remove also only once

        upd: actually using Lazy segment tree is overkill

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

        suppose some point is the point with the maximal value(call it p1), then only segments that pass this point are relevant. because for any other point that may be the minimal point(call it p2), segments that only pass p2 are obviously necessary to delete, and for those who passes p1&p2 at the same time, we won't have to delete them, since they dont affect with the outcome of v(p1)-v(p2).

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

    Maximum number of overlapping segments that don't end in $$$m$$$, or maximum number of overlapping segments that don't start in $$$1$$$. I have 5 lemmas to prove this, and it passed system tests.

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

    First sort segments by increasing left border. Then go through them, maintaining a priority queue of the right borders to determine when a segment goes out of consideration. We can observe that if the mth square or the 1st square is not covered, then the min is 0. Otherwise the min is the minimum segments covering the 1st or mth square. The max is the amount of segments currently considered. Code

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

    No need for segment tree or priority queue. Assume that in the optimal covering, the min point is left of the max point. Then we might as well take the min point to be as left as possible, or index 1, because there is no reason to add segments left of the min point. Therefore, we just use all the segments that don't cover index 1 and do an inverse prefix sum to find the max. Same argument for the min point is right of the max point. Take the max of both and that is your answer.

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

How to solve problem D?

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

    Use the principle of inclusion-exclusion on gcd. This can be done using Mobius function. Time complexity will be O(nlog^2n) I think.

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

    You can count "bad pairs" instead of "good pairs".

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

I found $$$D$$$ so much easier for $$$2500$$$ points. If $$$a_k$$$ divides $$$a_i$$$ and $$$a_j$$$, this means it must divide $$$gcd(a_i,a_j)$$$. So, iterate over $$$gcd(a_i,a_j)$$$, Let $$$gcd(a_i,a_j) = m$$$, find $$$num[m]$$$, denoting number of pairs having $$$gcd = m$$$, can be found easily using recurrence $$$num[m] = cnt[m]\cdot(cnt[m]-1)/2 - \displaystyle \sum_{r=2}^{\lfloor{n/m}\rfloor} num[r \cdot m]$$$, where $$$cnt[m]$$$ is the number of indices $$$j$$$ such that $$$a_j$$$ is a multiple of $$$m$$$ in $$$O(n \cdot logn)$$$.

Now, after fixing $$$m$$$, we just need to check if some index $$$k$$$ exists such that $$$m$$$ is a multiple of $$$a_k$$$ or not. This can also be checked easily.

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

    You can also do it using mobius inversion

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

    I agree, I think there should be another problem to fill in the gap between D and E.

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

      D had pretty less no of solves, its a div2 anyways i think it was fine

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

    yes, D is basically gcd convolution exercise..

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

Problem B: https://ideone.com/GV1ZXe why wrong answer on pretest (4) ?

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

pE too hard :((( can someone help me, thanks

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

C was very similar to this problem: link

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

is there a non brute force solution for A if k>10 ?

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

Couldnt debug C in time I just need 5 more minute :((

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

Made a screencast for this round: link. Very unedited and just made on a whim.

Got A-D and was almost done implementing E. Probably would've got E if I didn't spend so much time explaining stuff. Lmk any suggestions.

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

Very trash Problem E with 0 thought but +inf boring implementation.

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

Ratings updated preliminary, it will be recalculated after removing the cheaters.

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

It was a nice round! Congrats to all participants!

→ Reply