74TrAkToR's blog

Codeforces Round #904 (Div. 2)
By 74TrAkToR, history, 3 years 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 (72)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

As a tester, omg round by coordinator.

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

Why multiple contests on same date ?

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Why are ratings 1600-2099 so lucky they can participate in two Div.2 competitions.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

shatokhinp orz

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Why there are so 2 contests on the same day?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

It's time to rage(100%)

Spoiler
→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please note the non-standard start time for the round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

This is my first contest. Can i join it?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

More suitable for Chinese baby constitution

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Nice start to a Sunday afternoon (╥﹏╥)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve problem C?

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

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

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve problem D?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

C was very similar to this problem: link

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone please show me why my code goes wrong

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply