MathModel's blog

By MathModel, history, 18 months ago, In English

Hello Codeforces!


MathModel Setting Tour Continues!
I'm glad to share my tour of problem-setting with you! Recently, I have been setting problems for multiple platforms such as CodeForces Gym, CodeChef, KEP, and more is coming $$$!$$$


We are happy to invite you to RoboContest Round #103 (3.14), which will take place on Friday, March 14, 2025, at 17:30 UTC.

📅 Duration: $$$3$$$ hours.
📝 Number of Problems: $$$9$$$
📈 Rated for All on RoboContest
😎 Statements Avialable in English , Uzbek and Russian

The Round Maintaining Team:

Mr. Robot wish you $$$(\Delta \gt \pi)$$$ and Hope you find the problems enjoyable.

UPD 1: All Cheaters with Confirmation of using of AI Tools Got Banned from the contest , All the banned participants have been reviewed.

UPD2 : Congratulations to Winners ! :

  1. physics0523
  2. Sunnatov
  3. Husanboy
  4. vako_p
  5. diobrando97
  6. heaven2808h
  7. Edeeva
  8. Isamatdin
  9. conqueror_of_timosh
  10. Sardor Salimov

UPD3 : Editorial

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

| Write comment?
»
18 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

sto sto sto MathModel orz orz orz

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

As a tester, I forgot

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

As a tester, problems are great

»
18 months ago, hide # |
Rev. 2  
Vote: I like it +16 Vote: I do not like it

as a participant, i hope i'll reach M (at robo)

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

As a tester, please participate and enjoy:)

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

As a participant, I hope this contest will be legendary!

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

As a forgetful tester, I can't remember much! GLHF!

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

As a tester, I tested

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

It's now advertised on Codeforces.com. It's going to be a lot harder. Because GMs will see it.

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

As a coordinator, thanks to MathModel

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

As a coordinator, I'm busy waking up testers

»
18 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I signed in robocontest and should write any Uzbek region and shool I guess. I hope there's an option of just leave it as empty.

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

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

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

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

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

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

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

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

»
18 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

New problems added to ensure an interesting competition for all contestants , Please Participate :)

$$$9$$$ Problems in total and $$$3$$$ hours.

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

what is the real beginning time at robocontest, because it is set to 22:30 — 1:30. Will you fix it?

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

Contest starts in 1 hour

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

    Why I was suddenly became unregistered during the contest? As a consequence, all my submissions on the scoreboard have vanished and I needed to resubmit them (with a much bigger penalty) to get back on the scoreboard.

    Explain please.

  • »
    »
    18 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    Why my result disappered again from the leaderboard? And rating change wasn't applied? And why I wasn't mentioned in top-10 in the blog? And why I was suddenly became unregistered during the contest? As a consequence, all my submissions on the scoreboard have vanished and I needed to resubmit them (with a much bigger penalty) to get back on the scoreboard.

    Explain what is going on please.

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

Is there an editorial in this contest?

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

    Which problem do you need an editorial of?

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

      I haven't solved G and I, but I guess I can solve problem I by centroid Decomposition. I don't have any useful ideas for G.

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

        How can you solve it with centroids? I only know $$$O(n\sqrt n) $$$ solution using rerooting and sqrt-decomposition for maintaining distances from the root.

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

          My idea is quite similar to the editorial (though I spent a lot of time debugging my dirty code). First we know that for a query $$$q(point, l, r) = q(point, r) - q(point, l - 1)$$$. During the centroid decomposition, we need to construct the centroid tree. For each centroid $$$cen$$$, and in the subtree rooted by $$$cen$$$, I want to quickly know the sum of all nodes within a distance <= x from $$$cen$$$, denoted as $$$presum(cen, x)$$$. For a query $$$q(cen, r)$$$, we need to climb from $$$cen$$$ to the root in the centroid tree to accumulate all contributions. When climbing to a node $$$i$$$, the contribution is $$$presum(i, r - dis(cen, i))$$$. However, this will lead to double-counting, so we need to subtract the contribution from the path between $$$cen$$$ and $$$i$$$. Therefore, during the centroid decomposition, we also need to record the $$$presumson_j(cen, x)$$$ for each subtree $$$j$$$ of $$$cen$$$. BTW, I feel the implementing of square root decomposition method is also quite complicated.

          My dirty code
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it +14 Vote: I do not like it

    will be posted soon

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

As a participant, problems were good. But in problem G why O(n*d(n)) does not works?

Why am I specialist?

  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    You can it with Legendre's formula

  • »
    »
    18 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    $$$O(n \cdot d(n))$$$ doesn't work because consider max test which is $$$(n=960960)$$$ with $$$d(960960)=224$$$ , this yields a total computations of $$$215255040 \approx 2\cdot 10^8$$$ which isn't good within $$$1$$$ second.

    Solution

    Robocontest admin will give ratings soon.