Блог пользователя chromate00

Автор chromate00, 15 месяцев назад, По-английски

Oh hello there. This is chromate00, just casually on the announcement of Codeforces Round 1009 (Div. 3). And now, you see a drawing.

$$$\square$$$ — $$$\triangle$$$ — $$$\triangle$$$ — ◯ — $$$\triangle$$$ — $$$\square$$$ — $$$\triangle$$$

And then, you think. You see a square, a triangle, and a circle. Also, a Korean problemsetter. You immediately imagine the certain survival game that popped up in your memory. And you may be right. Or you might be wrong. Whatever, what I can ensure you is that you will be absolutely stunned to see the problems. Or astonished. You might not believe what you see. This round might change everything.

Anyways, the preface was a bit too long. Starting from Mar/11/2025 17:35 (Moscow time), you will be given $$$\mathbf{7}$$$ problems to be solved in $$$\mathbf{2.5}$$$ hours. There is at least one interactive problem, so I strongly urge you to read the guide if you are unfamiliar with the format.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution but the usual penalty of 10 minutes for each wrong submission, following the rules of educational rounds.

Remind yourself that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • not have a rating of 1900 or higher at any moment in time.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).

Also, note the (relatively recent) rule restricting the use of AI. If you are caught while breaking this rule, you will be terminated.

This round is made possible by the help of the following people:

I hope that you will also be in the spectacular moment.

UPD: Editorial has been posted.

UPD2: Congratulations to the top participants definitely except for the ones who cheated their way out!

All participants:

  1. ksun48
  2. arvindf232
  3. StarSilk
  4. maspy
  5. risujiroh

Trusted (rated) participants:

  1. sharvil_cpp
  2. Xing_Kong_C......has been terminated
  3. jxu
  4. 1zaid1
  5. eysikingE
  6. PlasticMemories
  7. Lappland_the_Decadenza
  • Проголосовать: нравится
  • +84
  • Проголосовать: не нравится

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +39 Проголосовать: не нравится

As a tester, cherry without her is cry

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

As a tester, I can confirm that this round is somehow ralated to squid games!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

As a tester, this round was shocking.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +59 Проголосовать: не нравится

as a tester, IVE PLAYED THESE GAMES BEFORE!!!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

As a tester, I can confirm there are two squares, four triangles and a circle in the announcement.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

as a tester, i can confirm chromate00 cooked the greatest div3 ever made

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

As a tester, this round is enjoyable!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

As a first time tester, this was truly one of the rounds of all time.

Mandatory motivational picture
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

As a tester, I was indeed stunned to see the problems.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

As a tester, cry offers poor people for testing and forces them to play children's games.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

As a (not so) pink soldier, your life may be on the line this round... so I hope you get AC!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

As a tester, if I catch any of you using AI in an illegal manner, I will personally order chromate00 to yeet you into the Ohio river.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

First time as an unrated participant

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

STPC 2025 Spring when? xD

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Score Distribution:

$$$ □ — △ — △ — ◯ — △ — □ — △ $$$
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

□ — math

△ — greedy/dp

◯ — speedforces

Put your predictions here

v

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

I have a feeling that there will be more than one interactive problem.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Last time a Div. 3 have interactive is Div. 3 Round 988.

It was at problem E and very balanced.

Let's hope we're having a blast too.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hoping to climb back to EXPERT !!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

;gimme 1530

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I will give my best to be back to CYAN in today's round, inshaAllah!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

If you are caught while breaking this rule, you will be terminated.

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I hope to become a specialist after this round.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

chromate00 orz !!!

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Why is there (VIP) before the name of some testers?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Going to give my very first contest today, Hopefully Codeforces Round 1009 (Div. 3) Ends Up Good For Me!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

This Blog Missing You for particirating

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Why give 7 geometry problems?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

GeometryForces!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

If you know someone who needs a geometry sheet, send them this contest.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

It turns out that I had been warned in advance

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

I love the sudden change of topic.
Thanks for the contest!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I mean, you needn't to eat too much geometric figure...

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

This kinda contest is Errichto's wet dream~ He would surpassed tourist, no doubt!

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +76 Проголосовать: не нравится

Those who participated Div3 today

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится

even though I am not geometry enjoyer, best div 3 round I have participated in

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    same bro, like usually any problem solved by 3k+ people till like div 2, I usually know at least how to proceed, in this one I gave full 45 mins to the question(I knew I wont be able to do E and G) but still couldn't figure out a single thing

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -27 Проголосовать: не нравится

Welp. I really did not like this round. I feel like the problems (considering this is div 3) are just getting creative for no reason. For instance, E is just... I don't know how one does that.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +55 Проголосовать: не нравится

    do you want tasks to be uncreative?

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится +3 Проголосовать: не нравится

      Don't get me wrong, obviously codeforces is not meant to be something like CSES. But it feels like there's barely any consistency anymore, so those that are not already at a high level that can easily adapt have a hard time progressing any further. For instance, do you think that geometry is really a good test for division 3? I think absolutely not.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится +31 Проголосовать: не нравится

        funny thing is the most "geometry" problem is A (and that is weakly geometry).

        All the tasks have geometry settings, but nothing to do with actual geometry. (for example, half the tasks are just about definition of triangle, which is a simple mathematical concept)

        • »
          »
          »
          »
          »
          14 месяцев назад, скрыть # ^ |
           
          Проголосовать: нравится +1 Проголосовать: не нравится

          I knew someone was gonna point this out. But I mean, take E. What is that supposed to test? I spent 2 hours thinking about that and still only thought of a probabilistic solution that still failed multiple times. Unless there is some real insight that I missed, a problem like that is pointless in div 3. Things like implementation, greedy, sorting, basic data structures, case analysis, etc. should be the focus of div 3.

          • »
            »
            »
            »
            »
            »
            14 месяцев назад, скрыть # ^ |
             
            Проголосовать: нравится +9 Проголосовать: не нравится

            i agree that E is not a good problem in a round, but at the same time, I think its a ok educational problem. The insight to take away is that randomized algorithms are something to consider as well. For example, take last div1A/div2C, some people solved it through randomization since they were too skill issued to solve normally. (and its applicable to a lot of places)

            i was not really defending the round, just pointing out a fun fact about how the round is geometry but not at all geometry at the same time.

        • »
          »
          »
          »
          »
          14 месяцев назад, скрыть # ^ |
          Rev. 2  
          Проголосовать: нравится -30 Проголосовать: не нравится

          E was guesswork

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        I get what you mean, when starting its easier to focus on a limited amount of techniques and algorithms, but in all fairness its the same for everyone and i think it would be benificial for most to get to know a lot more topics then just the few kind of problems codeforces has been limited to in lower divisions. The memes of pupils knowing segment trees are there for a reason.

        For example on E randomized Las Vegas algorthims, are really not too hard to understand and actually really cool!

        • »
          »
          »
          »
          »
          14 месяцев назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится

          Specifically with E, what is one supposed to do when exceeding the query limit (my submissions will show TLE if you check because I put that as a tripwire to tell me I had too many queries) since this is a random problem. I did a random solution but consistently exceeded the queries....

          • »
            »
            »
            »
            »
            »
            14 месяцев назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            your solution would work if the point given by the adaptive interactor would be random. Instead of replacing always the first point you should replace a random one.

          • »
            »
            »
            »
            »
            »
            14 месяцев назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            The problem statements clearly explains how to handle query limits and wrong answers. Essentially, your program should immediately quit (i.e. call std::exit(0) for C++, sys.exit() for Python) whenever -1 is read (for $$$n$$$ or as a response to a query).

            The statements of many past interactive problems were fairly vague on when the interactor gives -1, but this problem actually does a good job on this.

            • »
              »
              »
              »
              »
              »
              »
              14 месяцев назад, скрыть # ^ |
               
              Проголосовать: нравится 0 Проголосовать: не нравится

              I think you misunderstood what I meant. I was pointing out the problem with having a randomized problem in a round, not the fact that it is "difficult" to determine when the queries are exceeded.

              • »
                »
                »
                »
                »
                »
                »
                »
                14 месяцев назад, скрыть # ^ |
                 
                Проголосовать: нравится 0 Проголосовать: не нравится

                As long as your program handles -1 properly, you will receive the WA verdict when your program exceeds the query limit. You don't have to count your queries yourself and do infinite loop or whatever -- just implement what is stated in the statements and you will receive the correct verdict.

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      next contest will have twosum

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Why on mirrors that are not behind cloudflare (like mirror.codeforces.com or m1.codeforces.com) images are still behind cloudflare and are not displayed? Very inconvenient for such a round where several problems have images.

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится -9 Проголосовать: не нравится

[deleted]

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +29 Проголосовать: не нравится

    what geometry knowledge is required?

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится -32 Проголосовать: не нравится
      • Being comfortable with x axis and y axis and drawings on them and imagine how things go so you can solve (visualizations) for example I do this on graphs on a software and I used to do this with graph for this contest I was searching for any similar thing like geogebra and I was suffering consider this suffering for many problems ex: for problem D I was trying this software and make a circle to see patterns tgen I found that I have drawn many trying to fix this so delete my main circle and ahhh... (I know for u, you may not draw or even read the problem to get ACC, but for me now I do this)

      • nondeg idea for traingle if someone saw it many times he can solve quickly, but if someone saw it for the first time today and it was in two consecutive problems it is not something good, like I remember when I saw it for the first even its translation to my language was not ez to understand until I knew it just mean to be able to make a triangle

      • yes, even first problem Ok its sol is all dirs should be equal, but why not for example letting every side be equal to the other three like (d2 + l2) == (d2 + r2) == (u2 + l2) ....

      I did this for the first time and got penality so just guessed all should be equal, but to be sure I should draw and be comfortable with geometry

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
      Rev. 5  
      Проголосовать: нравится +1 Проголосовать: не нравится

      Problems A, B, C, D, and E involved geometric figures to some extent. Since I couldn't come up with a good idea for problem E, I assumed that it required a strong understanding of geometry. Now that I know problem E isn't a geometry problem, I see that my assumption was incorrect.

      P.S. It turned out that in problem E, I simply forgot to input N

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Bro i couldnt even solve C my bitwise problems are cooked ;-;

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -18 Проголосовать: не нравится

was E just a luck checking task or there is some formal proof ?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Someone tell me how you did D pls

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Both C and D makes me sweat in keyboard and note + pen.

Have no time left for actually solve E.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

I could only solve A :(

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

E is the most "guess till you AC" problem i have ever seen, thanks for the round.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The compiler on CodeForces is so stupid, it gave me compilation error because i used "goto" keyword on problem C.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Nah, your code is bad and the compiler is correct, according to the C++ standard. See cppreference.

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Finally, the following solution worked (still using goto multiple times). https://mirror.codeforces.com/problemset/submission/2074/310172545

      All I had to do was to split every statement (which contains the initialization of variables that get skipped over by goto) into two statements (one statement contains the declaration and one statement contains assignment: using '=' operator).

      Not sure why microsoft visual studio doesn't catch such compilation error even though I have all warnings turned on.

      Anyway, this compile-error is very stupid in my opinion.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        It's not very hard to deal with those compile errors. Basically you need to move the variable definitions up before any goto statements and labels.

        You can change this:

        void func() {
            goto A;
            int x = 0;
        A:  cout << x << endl;  // Error
        }
        

        to this:

        void func() {
            int x;
            goto A;
            x = 0;
        A:  cout << x << endl;  // Not error, though x is undefined
        }
        
        

        The C++ standard clearly says a goto jumping over variable definitions with initializers is ill-formed, so the compilers must issue a warning or an error when they see such gotos ("ill-formed" means the compilers must issue a diagnostic).

        And there's a good reason why such gotos are prohibited. Essentially they screw up constructors and destructors. The constructor and the destructor of an object must be called exactly once each, but gotos screw up object lifetimes pretty badly. Think about the following example:

        void func() {
            goto A;
            string s("abc");
        A:  cout << s << endl;  // Has the constructor of s been called?
            // And what about the destructor?
        }
        
»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve $$$G$$$ ?

and btw, was the intended solution for problem $$$E$$$ to use randomization ?

because I used a randomization solution and it got AC

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    yes this is heavily hinted upon (no hacks, only 35 hardcoded test cases)

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    $$$G$$$ can be solved with dynamic programming. Let $$$dp_{i,j}$$$ (with $$$i \lt j$$$) be the maximum score IF you only use points from $$$i$$$ to $$$j$$$. For the transition, notice that there are two cases.

    The first case is when you create a triangle with points $$$i \lt k \lt j$$$. You gained $$$a_i \cdot a_k \cdot a_j$$$ points, and you are left with unused points from $$$i + 1$$$ to $$$k - 1$$$ and from $$$k + 1$$$ to $$$j - 1$$$ respectively. Since we cannot draw triangles that cross each other, these two segments are isolated. Thus, the maximum points you can gain in this case is $$$a_i \cdot a_k \cdot a_j + dp_{i + 1, k - 1} + dp_{k + 1, j - 1}$$$.

    The second case is you split it into two segments $$$[i, k]$$$ and $$$[k + 1, j]$$$, where $$$i \lt k \lt j$$$, which is just $$$dp_{i, k} + dp_{k + 1, j}$$$.

    The final answer is $$$dp_{1, n}$$$. Since $$$i \lt k \lt j$$$, this results in $$$O(n^2)$$$ states and $$$O(n)$$$ transition, which is $$$O(n^3)$$$ total. With the constraint on $$$k$$$, try to see why these two cases cover all possible configurations.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

on E : random bullshit go

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Triangleforces :(((

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Today's contest was just me vs. geometry... and geometry won!

»
14 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

For E, I had the following algorithm:

  1. Start by setting i=1, j=2, k=3
  2. ask(i,j,k)
  3. Set fr as the frontman's response
  4. while(fr!=0) do :

    k = fr

    ask(i,j,k)

    Set fr as frontmans response

5.answer(i,j,k)

Can somebody explain the flaw behind this because I was getting wrong answer

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

Now I understand what u mean be the first two paragraphs and the drawing, I hope I understood before the contest to not join

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Was E more about fooling the system (test cases), or is there a way to definitely get an answer (with proof of how 75 queries will always suffice)?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Is there a deterministic solution for E?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what is the logic behind E?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

One of the contests of all time!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -36 Проголосовать: не нравится

Seriously, are contests being revised before being published for us to solve and if so how this contest was allowed isn't variety one of the criteria.....

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

For a website with a small number of users, i wonder why this websites loads very,very slowly during contest times even with good good internet connection. I spent also most 6 mins just to load the first problem and immediately after contest ends, the speed goes back to normal. And to think the problem setter decided to make the most stupid problems to compound my misery, making me regret why i even gave this contest in the first place.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What even is this statement in problem D :(

Please find the number of integer points inside or on the border of at least one circle.

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Oh man, this contest was harder than the usual Div. 3, especially C. I really liked D btw, I was stuck for some time until I realized I could sweep from the left.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    same, I thought on binary search for D but failed miserably. Then I brute force sweep from left and AC for about 20-30 minutes

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      hey could you please explain me the logic for D, for overlapping x for two circles? I tried to subtract the common points for two circles as i proceeded from left to right but then i realised i might be subtracting the same points twice for 3 circles which overlap and didnt know what to do further.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Simply avoid subtract, only plus with 2 pointers.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        If you are talking about the inclusion-exclusion principle, the limit of $$$n$$$ is way too large for that to work.

        Instead, imagine a vertical line sweeping from the far left to the far right on the x-axis. You can quickly calculate the number of integer points on that line that are contained in some circles. Since the sum of radii is bounded by $$$m$$$, the answer can be found in $$$O(m)$$$.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what's wrong in my recursive dp in Problem G 310149712

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

wtf was even the logic for e , just random bullshit guessing ??

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Naive random guessing failed for me. Instead, initialize with a random guess, if it works then you're done. Otherwise take the new point inside the triangle plus randomly pick 2 of your previous 3 points to carry forward to the next iteration.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve G

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, round is awesome

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

Oh, my dearest chrom chromate00 ater. I used to think we were of opposition.

But that was until this very day! I realized that I was only under a circumstance called “skill issue.”

Alas, I was eventually enamored by your brilliance, and unskilled my issue until I fell in love with the chrome that is ater... Zero zero.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In problem D, shouldn't sum of n overall test cases also not exceed 2e5? I was confused with this during the contest and wasted a lot of time thinking about it.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Thanks to the authors, for the fact that I may have become a specialist.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Great contest! Thanks to the writer(s)

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

i envy people that are calling these problems geometry because they clearly never suffered trying to solve an ICPC geometry problem...

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Season 2 when?

»
14 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится +89 Проголосовать: не нравится

I don't really think the round was too focused on geometry. Despite that all problems were geometry-themed, this round didn't really involve any problem of which the key technique/knowledge required was geometry. A, D, and E might be a bit geometric, but the geometry part isn't even the hardest part of the problem and should be trivial for anyone who tries these problems (not saying that the problems are easy, but the actual difficult part isn't geometry.)

To be honest, I find much more rounds being too much focused on bitwise operations by having like 3 problems around the similar category, and it feels like more than half of the rounds nowadays are heavily focused on math that is not geometry. It felt pretty good to see some geometries (at least mildly) once in a while. Also, this round actually tried to introduce variety in problems, each requiring a different skillset in different categories.

Believe it or not, my least favorite problem in this round was C because I'm so tired with all the XOR problems and I was hoping not to encounter them for a while, and I fatally struggled so much on it again (it took me more time to solve than D, E, and F.) But overall I really liked this round.

  • »
    »
    14 месяцев назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится -8 Проголосовать: не нравится

    For me, most hard part is geometry(especially on D) :( I'm going to middle school and i don't even found how to count the numbers of points in a circle. In this case how can i found the algorithm for D? I can't understand editorial too.

    btw C was easiest problem for me except for A :D

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
      Rev. 3  
      Проголосовать: нравится 0 Проголосовать: не нравится

      The only geometry knowledge you need for D is that whether a point is inside a circle is determined by the distance between the point and the center of the circle. The distance between $$$(x,y)$$$ and $$$(x',y')$$$ is $$$\sqrt{(x-x')^2+(y-y')^2}$$$, so you just need to check if this is less than or equal to $$$r_i$$$ (better to square both sides to avoid precision errors by using integers only). This information is already given in the statement as well.

      The rest of the solution is that for each circle you check every $$$x$$$s from $$$x_i-r_i$$$ to $$$x_i+r_i$$$ and find the largest $$$y$$$ that satisfies the inequation, which can be directly done by reordering the inequation or by binary search, and this process isn't much related to geometry.

      I guess the reason you felt this problem hard is not because you lacked of geometry knowledge, but because you failed to come up with the idea of bruteforcing every $$$x$$$, which makes the part of using the formula trivial with one of the coordinates fixed.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        i kinda understood what you mean but what does (x′,y′) coordinates mean?

        • »
          »
          »
          »
          »
          14 месяцев назад, скрыть # ^ |
          Rev. 2  
          Проголосовать: нравится 0 Проголосовать: не нравится

          It's just an arbitrary name given for the second point's coordinate in the general formula of the distance between two points. In this problem, you may assume that $$$x'=x_i$$$ and $$$y'=0$$$ for each circle, which leads to the requirement written in the statement.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Why is F so hard ?

Hard because of thinking ? No, hard because of understanding :)

»
14 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится -10 Проголосовать: не нравится

There should be variety in problems. It's not fair to create entire round on the same concept. It gets too much boring and this might cause fatigue for people who don't really enjoy geometry even though they can solve the problems and this can ruin their performance.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +9 Проголосовать: не нравится

    There are $$$14$$$ distinct tags over $$$7$$$ problems now, clearly you are not seeing the apparent diversity that people see...

    • »
      »
      »
      14 месяцев назад, скрыть # ^ |
      Rev. 5  
      Проголосовать: нравится 0 Проголосовать: не нравится

      I am just saying that everything is related to points and geometrical figures which becomes too much monotonous and boring especially for someone who is not much interested in geometry like me.I agree there are greedy, probability and bit manipulation kind of topics involved but I never saw any contest yet on cf which is entirely based on a single concept.Correct me if I am wrong on my last statement.

      • »
        »
        »
        »
        14 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится +1 Проголосовать: не нравится

        However, look at actual recent contests. Notice how you can enumerate what the tasks might look like, even before looking into the problemset. "You are given an array, do blah blah blah on it, then solve blah blah blah queries.", "You are given function blah blah blah, calculate the sum of function blah blah blah on all blah blah blah", etc. And almost every such moment, you can think of a tag in your mind, and almost every five tasks you will get it correctly. Don't you think this is weird? Do you think this is the real meaning of variety?

        Honestly, I do not get your point in variety. I could only read "I hate geometry" in your intentions.

        • »
          »
          »
          »
          »
          14 месяцев назад, скрыть # ^ |
          Rev. 2  
          Проголосовать: нравится +12 Проголосовать: не нравится

          Yeah I understand what you mean. Agree, thats actually how it happens. And yes my opinion might be based on my bias against geometry :(

          Anyways thanks for your clarification.

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +11 Проголосовать: не нравится

    There is something called Themed Contest !! The problems involved many other algorithms and tags; it was just that they all were embedded in a geometrical story. And even; if Geometry was used anywhere; it was hardly above the level of mid school maths !! And what bad is solving a Geometry Dash contest?? If you're good at Geometry, you will do well. And if you're not; such contests would motivate you towards learning Geometry !!

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why isn't there any system testing or ratings update?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Pretests were so weak. LMAO.

»
14 месяцев назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

,

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

Hello, so I got this message that my submission for D no. problem is similar to some random dudes submission who I don't even know. As far as I am concerned, I abode by the rules of codeforces and reached the solution my self while using AI for only direct translation to Bengali and Autocompletion tool Copilot and Codeium. Now all my submissions show skipped. What do I do and how do I proof that there were no cheating or plagiarism. Help please

  • »
    »
    14 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Okay so as per the instruction, I'll provide my thought process for my solution for the problem:

    I started things off by imagining the circles on the plane and quickly realized that since the center of each circle sits on the x-axis, tackling the problem one horizontal line (or “slice”) at a time makes it a lot easier. For every fixed y-value, I figured out the range of x-values that fit within each circle using the circle equation. This naturally led me to create intervals of valid x-coordinates.

    Then, since multiple circles could create overlapping intervals on the same y-line, I combined those intervals to ensure I didn’t count any point more than once. Since, each circle contributes intervals for each y in the range [-ri, ri]. I realized that different circles might contribute intervals at the same y-coordinate. So, I thought of using a dictionary (or defaultdict) to collect all intervals for every y-value across all circles.

    I worked on refining this method on my own through several iterations and tests.

    This was my overall thought process... Do I need to provide technical walkthrough too?

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How can one get rank 1 and 2 by cheating? Any other reasons for termination? chromate00

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

for this contest, I don't have access to my own computer, & I used OneCompiler site to run my codes, also I didn't know anything about their settings and privacy for showing codes to others , and I think that's why someone submit similar code to mine , about an hour after me

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

that was funny contest with nice problems, thank you :)