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

Автор IceHydra, 19 месяцев назад, По-русски

Привет всем!

ne_justlm, itz_pabloo и я хотели бы видеть вас как участников Codeforces Round 1006 (Div. 3), который состоится во 25.02.2025 17:35 (Московское время).

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов (мы очень надеемся, что в течение нее упадет не очень много решений).

Как делается очередной анонс:

  • здесь начинается копипаст,

тут ваш текст, icpc правила и т.п.

  • здесь кончается копипаст.

У вас будет 2 часа и 15 минут на то, чтобы решить 7 задач. Штраф за неверную посылку будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, вы сможете выбрать тип участия(rated/unrated).

Мы хотели бы поблагодарить MikeMirzayanov за платформы Codeforces и Polygon, а также Vladosiya за неимоверно крутую координацию подготовки раунда.

Так же огромное спасибо мы бы хотели сказать Kirill_Maglysh за его огромную помощь в создании этого раунда.

Также, спасибо нашим тестировщикам:

ОБНОВА: ПОЯВИЛСЯ РАЗБОР

Editorial

  • Проголосовать: нравится
  • +242
  • Проголосовать: не нравится

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

yayyy first comment! (only wish that the contest was over the weekend :( )

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

Excited! hope for +pos delta.

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

As a tester I can say that I am a tester

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

Where is cry? We want cry sirs

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

Nice contest sir

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

As a tester I tested the first Phystech Lyceum (our school) round. I found some problems interesting, so I recommend participating!

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

My first time testing a contest. Problems are interesting. Please participate.

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

As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.

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

Hoping for +del and wishing everyone +del

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

As a tester I can say that it was my first testing and all problems were interesting.

Good luck and positive delta to everyone!

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

time to recycle this meme lol

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

I hope I dont fumble this contest and reach expert

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

7 problèmes à résoudre en 2h15, avec une pénalité de 10 minutes pour chaque erreur. Si t’as déjà rêvé de rager devant un bug à la dernière seconde, c’est le moment parfait.

Mon objectif ? Réussir au moins un problème, histoire de ne pas pleurer en relisant mon code après coup. Bonus si j'évite de tomber dans un piège bien vicieux.

Que le karma des AC soit avec moi."

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

    hhhhh, enfin quelqu’un qui comprend la vraie douleur du competitive programming ! Entre les erreurs bêtes, les tests cachés et les cas tordus, ce round promet d’être un grand moment de réflexion… ou de désespoir.

    Mais bon, tant qu’on ne finit pas avec un score de zéro, c’est une victoire. Bonne chance, que ton code compile du premier coup et que les WA t’oublient !

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

Recently, the use of reasoning LLM models has impacted CF rounds, as more submissions are getting AC than usual due to increased AI-assisted problem-solving. This raises concerns about rating inflation and the integrity of contests. Implementing defensive measures against it is necessary, but not an easy task. Let's see how things unfold.

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

fun fact :

the photo will change depending on what language you are choosing in cf

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

it would be cool if we did div 3 and div 4 more often for beginners, including me

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

I have a question. Do we get paid for preparing contests on Codeforces? If so, then how much for each division?

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

Tester categorisation is really great and funny.

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

I hope ne_justlm added a promblem about stari_bog and gamblers (I hope google translate translated the text correctly)

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

As friend of all creators, I am sad cuz there is no komaru in the photo :(((

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

hopefully i touch Lever in this contest :)

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

ГООООООООООООООЛ

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

Ну раз такая пьянка, то не грех и написать див впервые за 4 месяца :D

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

i hope everyone get positive delta

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

I accidentally registered unrated. Can I undo it and register again rated?

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

I wonder if i can reach pupil this contest

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

I'm gonna absolutely destroy this context. Just wrote myself a new template file.

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

hope to get +1 this time

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

I wish I could control my dopamine not to participate in these div-3/div4 contests and dropping my rating by a big amount.

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

I wish all the best to all the contestants either you are newcomer or professional hope the rate of all of you get increased super high hope you learn something useful hope you dont get wrong answers or anyother problems hope you get the accepted easily <3

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

Longest problem title I've ever seen on Codeforces.

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

Div3 is cooked. GPT has killed all questions.

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

Biggest Negative Delta incoming! T_T

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

ezzzzzzzz

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

problem F 's main idea

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

Incredible contest! Maybe on the easier side but the problems had a very nice pace and a slow ramp up in difficulty. Maybe one of my favorite contests ever.

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

What is the pattern in F?

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

little secret: Diff picture for Eng and Rus post

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

Stop making problems with so many math calculations, I could've easily solved G if I didn't have overflow but ofc i couldn't find it coz it's so much writing to do

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

Fun one, I got all but the last one. Thought I had the math but didn't have it 100% and didn't have the time. Hope everyone did well.

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

E is so tricky, still couldn't figure out why my solution not working.

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

    The problem is a roundabout way of saying number of pairs where Manhattan distance is the same as regular distance. Or in other words, for every pair of staves that share one X or Y coordinate.

    For a given x or y, the number of pairs is sum from 0 to (number of staves on that X/Y minus 1). For instance, if there's 2 staves with x = 3, then on x = 3 there's 1 pair (sum from 1 to 1 is 1). If there were 6 staves, there'd be 1 + 2 + 3 + 4 + 5 = 15 pairs. You see?

    Very easy to make the needed amount of pairs with 500 staves because of how it grows. Sum of all numbers 1 to n is about half n squared, 500 squared is ginormous so 500 is more than enough staves to fit the problem requirements no matter what level spell.

    Trick is to just make sure you keep them separate. Pick a y coordinate, stack staves on that row going up by 1 x every time until adding an extra one would take you over number of pairs. Then move up a row (change y), but don't reset x to not add any extra pairs. This solution makes all pairs have the same row, NEVER the same column so no two staves have the same x. (In my actual solution I reverse X and Y here but same thing). Works no matter what, just have to iterate through staves and move up by one, simple addition.

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

how to C?

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

Nice contest! I liked problem F

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

Is this round easier than usual? I think it is my first time to solve E (forget about not solving D)

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

Fumbled on C again. I've over complicated stuffs :(

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

The relief after finally solving E! (next time will solve in time haha) Didn't quite get D, I assumed it's something related to segment tree so skipped. Any hints?

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

    I thought so at first but look carefully at the constrains

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

    in D , n<=2000 shifting left means you will take one element to the back and nothing else will change , no lets see how this will affect inversions all the elements that are bigger than lets X will add + inversions , all elements that are smaller than X will subtract inversions. so you just needed to check how numbers between ith element to jth element will affect inversion change. you can check my code

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

    For D, the operation is basically shifting one element to the right some number of times. Every time it passes over a larger number the number of inversions INCREASES by 1, a smaller number causes it to decrease. Trick is the input size is actually small enough to just brute force it from there. So you just go through each index, count from one after til the end number of biggers and smallers. At any index here the minimized inversions is the number of smallers minus number of biggers. Keep track of max every time, O(n^2) answer fits the time constraints.

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

Worst contest of all time F was formula chat gpt free version without using reason model was able to figure it out. What's the point of keeping such problem.

If problem were made to solve by the gpt then keep good non adhoc problems. Most of the genuine contenstants would be absoutely fine with it.

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

I got failed in G just because of forgotting to mod :(.

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

This was more like a Div. 4 round

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

i tried nlogn for F but TLE whats the solution?

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

I think 2072E - Do You Love Your Hero and His Two-Hit Multi-Target Attacks? refers to Do You Love Your Mom and His Two-Hit Multi-Target Attacks?, ans 2072G - I've Been Flipping Numbers for 300 Years and Calculated the Sum refers to I've Been Killing Slimes for 300 Years and Maxed Out My Level. Any other refernces?

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

How can I approach Problem G? Any topic need to know to solve this problem?

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

How can I approach Problem G? Any topic need to know to solve this problem?

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

Racist contest... Cancelled for racism -_- (problem B moment)

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

Good contest! Nice problem set! Nice ad-hocs! Everything was cool just not the

Spoiler

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

What is wrong in my logic of E

p1,p2 calculated as highest p1*(p1-1) <= k , similar logic for finding p2.

Place p1 points along X axis and then place p2 points along Y axis starting from 1, i.e, (1,0) and (0,1) respectively. Now number of pairs = p1C2 + p2C2.

Now place remaining k-(p1C2 + p2C2) pairs as points itself in the 4th quadrant, so they contribute to k pairs. Is there any flaw in this or can someone give a mathematical proof for E

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

    You're overthinking it. As a tip, you have max 500 staves, and you don't need to minimize the number of staves at all. Put all the staves on DIFFERENT x coordinates so they never share a column. For each staves on row R, the number of pairs is sum from 1 to (R — 1). So with 5 staves on y = 0, number of pairs is 1 + 2 + 3 + 4 = 10. Keep adding staves til adding one would take you over the necessary pairs, then move up a row to restart back to 0. Keep doing this until you have all the pairs. 500 staves is way more than enough to do this, and any X or Y works as long as you increment when necessary.

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

      yep got your solution, I debugged my code by handling answer whenever it goes > 500, I thought my solution always gave ans < 500, wasn't able to come up with a formal proof of it during the contest.

      So your solution gives the minimum number of points we need to have right coz mine doesn't do that, I just constructed it

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

How do I get within time limit for G? I tried using one equation for everything between n and k, then calculating digits of n in each base k and adding their worth with multiplication, division and mod to the result. I got correct answers but time limit on test 3. I thought this was a harmonic series or something?

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

Wow what a contest approx. half of the first page standings people cheated.

hackersheela — Global Rank 3

Delwar — Global Rank 1

Beserker69 — Global Rank 4

and many more examples like these are there.

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

I think we need to review the way the questions are given because problem G just needs to give the questions to deepseek and AC

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

Can anyone help me today's G

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

Can anyone help me in today's G

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

F Involves crazy observation, But the biggest beauty about that question is that you can solve it by just finding this pattern and doing a recursion.

Pattern

Solution

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

ever since when there's so many people solving such hard problems every contest :'). I guess i'm lacking behind so much :(

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

how to become a tester? wanna test some prob first hand !!

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

I don't get it why my solution is failing on samples. The MEX of my output in test-8 is also 5 and the jury's MEX is also 5. So where am i going wrong then ?

307885645

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

Please go after cheaters in full swing, I can't believe this many solves on F of Div 3. How come does everybody know Lucas theorem, clearly evident use of ChatGPT/Deepseek AIs in contest.

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

    exactly. i never saw this many people solving such problems :') (and apparently, there's YT channels and Telegram channels that provide the solutions, wow)

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

    " I can't believe this many solves on F of Div 3"

    And I can't believe the authors decided to keep a CSES problem with next to no tweaking for F. Even LeetCode doesn't do it these days. Any one who had solved Xor Pyramids before would cheese through yesterday's F and those who hadn't even if high rated would struggle figuring it out. Though I happened to be on the befitting end, I feel it isn't very fair to keep CSES problems in an official round since it's the most popular sheet out there.

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

Can anyone explain the solution of G ??

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

    for k <= sqrt(n), compute digit by digit for sqrt(n) < k <= n, rev(n, k) = n % k * k + n // k = n — n // k * k + n // k, we can partitions k by the value of (n // k) and compute each partition in O(1) for k > n, rev(n, k) always equal to n

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

one of my answer got accepted yesterday , but right now it is showing in queue it it normal or any glitch here??

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

In problem G, when calculating n * (n + 1) / 2 and n * (n + 1) * (2n + 1) / 6, I used fast power of 1/2 and 1/6 and got TLE

If I pre — calculate 1/2 and 1/6 and use them like integers, I got full solve :( :( Poor me :(

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

Hello! Why i'm getting wrong result in check #2 in problem A, while test results and check #1 are right?

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

Editorial?

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

.