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

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

Hello, Codeforces!

NemanjaSo2005 and I are glad to invite you to Codeforces Round 1019 (Div. 2), which will start on Apr/21/2025 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.

All problems are invented and prepared by NemanjaSo2005 and me.

We would like to thank:

The score distribution is $$$500 - 1000 - 1500 - 2000 - 2750 - 3000$$$.

We hope that you will participate and enjoy the round!

UPD: We are aware of people cheating on problem F. We are looking into it and are going to make sure to ban as many of them as we can!

UPD 2: Editorial

UPD 3: Congratulations to the winners!

All participants:

  1. maspy

  2. Nachia

  3. kotatsugame

  4. abc864197532

  5. Little_Sheep_Yawn

Rated only:

  1. HS90R

  2. oreg0na1

  3. bssss_a

  4. _.Ali._

  5. miumah

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

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

As a participant I would expect the problem statements are also short like the announcement, GLHF

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

As a tester, this round has cool problems, and I found one of them especially nice.

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

Blagoj wtf strong

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

Blagoj orz

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

As a tester, I had fun testing and I hope you feel the same participating ) Good luck!

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

omg epic Blagoj NemanjaSo2005 crossover orz

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

as a tester that contributed basically nothing, Blagoj NemanjaSo2005 orz

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

As a participant, I hope that in this contest I'll solve two problems quickly.

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

as a participant, I hope that this isn't another Neowise Labs contest for me :)

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

Contest announcements should be on the front page right? I wonder why this one is not there, even when it's a rated contest.

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

I wrote question D in my dream!

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

ABCD speedforces

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

    But I was blocked by human-machine verification when I was trying to submit B,and it took me about 20 minutes.Otherwise my rank could rise to about 500,and I won't go back to Expert today.QAQ

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

As a 1409-point newbie, I don't want to drop down to Pupil, please...

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

I want to know how some people submit their solution within 30 sec of starting of the contest? can -any one explain please ?

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

can i reach green?????

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

1k pass D and 150 pass F, THE CRAZYEST LLM CHEATING ROUND, I will get -100 delta soon :(

UPD: I test chatgpt o4-mini(free) after the round, and it solve F in only 50 seconds!!!

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

huge -ve delta incoming....plz kill me god -_-

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

ImplementForces CheatForces

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

I had fun solving C and D

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

Until now, 147 have solved F, and 129 of them are rated. I suggest that Div2 can be changed to 2100-rated and above, so that it reflects our actual level.

Seriously, E is a very simple question relative to F. I don't think banning everyone who solved F but didn’t solve E would be inaccurate.

They didn’t even try to hide it – that's what pisses me off the most.

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

    I didn't look into status page to check submissions: I saw disbalanced stats on F in overall stats and opened it as a next one. Based on scoring I thought they should be relatively similar. Even keeping in mind that someone is doing gpt-submissions, it still made sense for me to read it first: if the task is solvable by llm, maybe the statement is clearer than in E, and this is important for problems with close scoring.

    I havent solved F but it was a close call. So I believe this statement I don't think banning everyone who solved F but didn’t solve E would be inaccurate. is a bit too much: some people's strategy definitely was affected by standings.

    However I agree that the situation is a ridiculous one.

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

      I think that is why F probably has more legit solves than E. I can surely see F being easier than E, but not by like 500 rating as it is predicted.

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

      You guys are right. Maybe because I prefer construction questions, I quickly found out how to do E but I had no idea about F. It is true that someone may followed the scoreboard and did F first (that actually happened to me)

      I think those who solved F but not E need to be taken action: 1. Grey name 2. Lots of GPT-style comments in the code 3. Didn't even solve D (or C)

      It's possible that CF will be the next leetcode, where GPT dominates the contests. Hope to see some action.

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

ClarificationForces

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

A<<B<<<<<<<<<C

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

got stuck at C. How to solve C ?

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

oh no .... problem B was good case work and I messed up.

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

What's wrong with problem F?

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

I enjoyed F. Tried multiple different approaches until I thought of the right one

Edit: Why am I downvoted to hell

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

Cooked in C

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

c was overkill

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

How to solve C? I spent 1.5 hrs for debuging my solution for C.

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

Problems are: Ridiculous, staged, and without ideas

If you cant ask questions, dont hold a contest!

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

Wondering why my D solution(316582962) keep getting WA on 2, I've spent almost 1h on finding the reason.

rip for my -40 delta, im getting back to expert...

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

    Try this:

    1 
    6 
    1 2 1 2 1 -1
    

    I think this is wrong: (o && x!=v[i][o-1]+1)

    After 1 finished, you check if 2 is connected. You should use linked list.

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

    After looking at it for a bit, it seems our solutions use the same basic idea. However, it seems you're missing some casework.

    Firstly, in your for, you look for an index $$$i$$$ such that $$$cur_{i - 1} + 1 \lt cur_i$$$ between your indices as the reorientation point for the sum (right, cause we want to form a structure akin to the following: "\/" or "/"). But, what if the values between $$$cur_{i - 1}$$$ and $$$cur_{i}$$$ are all less that the current value that we're checking? In that case, you reorient yourself at the wrong point (as one of the values in that iteration could become either a local minima or a local maxima). Therefore, you need to find a mechanism of selecting that index $$$i$$$ such that the values between $$$cur_{i - 1}$$$ and $$$cur_{i}$$$ hold with the previously stated condition.

    Secondly, I think you aren't handling the case when we shouldn't reorient ourselves at any point properly. Anyways, I think if you manage to rework that previous case (the solution to that part isn't as bad as it sounds) you will be able to find all additional janky cases.

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

how to solve B plz anyone share the approach...

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

Lots of grey got AC in F...

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

solving A, B : Is this div 3 or what!

solving C: now, I get it :(

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

Just have a small comment on D, I liked how the input stated that a[i] <= logn, because I had comment on last round that D didn't state that n will be odd always.

D today could have said that a[i] <= n, and then all the testcases will not exceed logn (because it is impossible to be > logn), but for me I see that contestants should not have any assumptions on the input so thank you for stating the actual values in testcases

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

i thought F was a well known problem

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

After I hard working and solve problem D and find out that problem E is hard to implement. I notice that I can gain some score in the round. However, the predictor told me there are so many guys better than me.

Why? It is because that zombies walk from graveyard in the Easter? (Easter = 复活节 in Chinese)

Find cheaters on the post: https://codeforces.me/blog/entry/142150

Thank you?

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

I just bombed problem C.

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

I hope that NemanjaSo2005 could ban cheaters on F as soon as possible.

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

As a tester, we are aware that today (just like in any recent round) a lot of people have used LLMs, which is against the rules. It is the reason behind the inflated number of solves on the late problems.

NemanjaSo2005 and Blagoj know about this issue. They were working hard on finding and reporting these cheaters the whole round. Even now, instead of taking a break after months of working on the round, they are working on the situation. The cheaters will get removed soon, but the priorities right now are publishing editorial and system testing.

Some people are blaming the authors for things that are out of control. Let's focus on the positive aspects of the round instead, because after all, Codeforces is just a cool hobby we have. If you enjoyed the contest, consider supporting the authors. You can comment about the problems you've liked, what you've achieved today, or even just upvote the blog. It may take just few seconds for you, but it means a lot to the authors who spent months making the round as good as possible for you, the Codeforces community.

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

Is pragma really that powerful? I have heard that pragma can usually speed up performance up to 2x or 3x but in my situation is a whole 20x

First code (TLE)

Second code with pragma (AC, 62ms)

Both code are exactly the same, except for the first line

How is this possible?

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

    oh wow !! is there any reading material to understand what is this sorcery.

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

    I'm guessing that with -O3, the compiler pulls a[i - 1] != a[i] out of the inner loop, changing the time complexity from $$$O(n^2)$$$ to $$$O(n)$$$.

    If anything I'm surprised that it doesn't do this optimization at -O2; that expression is pretty obviously loop-invariant so if it fails once you can just break out of the inner loop immediately.

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

I was a bit surprised by both C and D.

For C, I thought the solution could just be implemented with just two pointers and a couple of counters. And although maybe that solution could work, after staring at it for way too long, I figured that some more interesting properties (well, convert array into 1s and -1s, get prefix sum and suffix sum, and etc) would be necessary (which was in fact the case and thus produced a very clean solution).

Then for D, I instead got scared and thought that today was my bonedead day. Then, I saw the necessary observation, implemented it, got WA on the first test case, realized I needed to just flip the sums with relation to the fixed value (-1), and voila.

So overall, I quite enjoyed the problems (A through D)

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

D was nice, i implemented a toposort solution (wasted alot of time). then realized a very simple solution.

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

Thanks to younesg, we now know that OpenAI's claims about their model o3 having a rating of 2700 are false. It's clear to everyone that he's using LLMs to cheat (even in today's round), yet his performance is still far from GM level (He was ranked 2nd once lol, but that was only because the problems were standard)

I'm honestly surprised he hasn't been banned yet, even though he's been caught cheating in multiple rounds and many of his submissions were skipped.

I used to enjoy watching him waste 2 hours every contest benchmarking different LLMs, but now that we know o3 is nowhere near GM level (thanks to him again), he's not really useful anymore. So at this point, he might as well just get banned.

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

    lol

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

    o3 got nerfed now. But yes, it still has too much of a varied performance (for example, it sometimes fails on 1600 rated problems, and sometimes can do 3000 rated problems (when they're standard or involve implementing some data structure or something)). Another point of note is that o3-mini has gotten GM performance before, so we cannot judge the skill of LLMs based on only one contest, we need to take the average. In the last contest, o3 got around IGM performance (ABCDEH), due to already existing problem H, so it can sometimes get much better results than GM performance also.

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

      Yes, I do agree. But when I say someone has an IGM level, it's more of a point of view from a human perspective, not just about the rating itself. Getting WAs on test 1, getting hacked because of using unordered_map, and often failing on easy problems—this doesn't look like IGM level to me, even if it managed to achieve the IGM rating it still not and IGM.

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

OMG, first time among the top 5! Happy! Still I've got no idea about F which disappoints me.

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

Only thing is to give plag to rated participants who solved F but not E

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

I like today's problem F, thanks for the great problem :)

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

Really difficult but interesting problems. Thanks for the round

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

can anyone explain why it says -2 here in problem B but it was actually accepted

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

C is easier than B, case work in B was really tough, wasted more than an hour on B

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

Can anyone hack my solution for C since I believe that it has a worst case complexity of O(n^2). 316589874

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

A good news and a bad news for me: solved D 3min after contest.

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

Any idea how to approach poblem B ?

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

for C i didn't do anything fancy. didn't convert to 1/-1, didn't use two pointers, partial/pref/suffix sums.

i just checked if a subarray was possible from the beginning and then from the end:

if both of them were possible : YES both of them not possible : NO

one possible :

check if a middle array is possible : YES ? NO

did i get lucky with testcases or something??

my submission

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

What the hell, AI in the top 5? 316553220

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

I am so worried about the impact of AI on online competitions...

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

My Solution for Problem E (Almost Completed During the Contest, What a Pity)

Step1: Assume a[s]+a[t]=k, perform operations to make a[1]+a[n]=k.

a[1] ... a[s] ... a[t] ... a[n] -> a[1] ... a[1] ... k-a[1] ... a[n] -> k-a[n] ... a[1] ... a[n] ... a[n]

Step2: Arbitrarily swap a[x],a[y]

a[1] ... a[x] ... a[y] ... a[n] -> k-a[y] ... a[x] ... a[y] ... a[y] -> k-a[x] ... a[x] ... a[x] ... a[y] -> k-a[y] ... a[y] ... a[x] ... a[y]

AC Code: 316605252

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

we don't want that much powerful cheating detector, most cheaters are obvious for now, just get them

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

hello my fellow competitive programmers, this morning i was looking for some youtube videos to understand and upsolve the problems which i could not solve in 1019 Div 2 contest, then suddenly i saw this youtube channel. this man has uploaded all the solutions till problem F excluding problem E, solved all of them, and i am damn sure he has cheated, also he runs a telegram channel which is mentioned in his youtube channel where he uploads the source code of all the problems, and he has just registered some hours ago, he is — 777dimasik777. and even if he has not cheated, whats the need to upload solutions on youtube and telegram during the contest. such people ruin our community and this platform. please, someone take strict action against such cheaters, so this platform is free from them.

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

Good evening everyone, This is my first ever comment on Codeforces and I had hoped it had been under better circumstances. I had recently received a system mail saying that my solution for problem D 316573346 had a lot of similarity from another user's Pratik__9284 submission 316588192. I was shocked by this claim as I had not participated in any form of cheating or sharing my code online. On looking through this person's profile I noticed some astonishing patterns which suggested this is not a mere coincidence. This person has gone from being a Newbie to a Candidate Master in mere 3 contests. I know it may be possible but it is highly unlikely that this person has gone from achieving a 12,953 rank a month ago to having global rank 7 on yesterday's contest.

I don't know exactly how this person got to access my code (Maybe from the lock & hack system) but I hope someone looks into it. I feel pretty bad since I don't support this unethical action which ruins the fun for other hardworking contestants and the problem setters (Blagoj and NemanjaSo2005) who contributed so much to bring us these new ideas.

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

https://leetcode.cn/problems/queue-reconstruction-by-height/description/ https://leetcode.cn/problems/group-the-people-given-the-group-size-they-belong-to/description/

I used the relevant parts of the above content as a reference.316584505 I don't think this is a violation. Maybe it's just a coincidence or a result of the leakage caused by using the public web-based online compiler. I read the code from the other party[submission:316548435] in the email and found that there are significant differences in naming styles and detail habits. This is not a violation of the rules. I hope to have the relevant handling revoked, and I will participate in the next competition in a more secure environment. ~~~~~ The following boards are derived from the two websites and personal summaries below /* vector<vector> groupThePeople(vector& groupSizes) { unordered_map<int, vector> map; for (int i = 0; i < groupSizes.size(); ++i) { map[groupSizes[i]].push_back(i); } vector<vector> res; for (auto& entry : map) { vector& group = entry.second; for (int i = 0; i < group.size(); i += entry.first) { res.push_back(vector(group.begin() + i, group.begin() + i + entry.first)); } } return res; }

int left = 1, right = n; for (int group : groups) { if (group % 2 == 1) { // 奇数组分配较大数值 for (int pos : groupPositions[group]) { elements[pos] = right--; } } else { // 偶数组分配较小数值 for (int pos : groupPositions[group]) { elements[pos] = left++; } } }

set available; for (int i = 1; i <= n; ++i) available.insert(i); // 处理某个位置后移除 available.erase(pos); // 查找连续区间 auto it = available.upper_bound(pos);

// 处理完所有组后分配特殊位置 elements[specialPos] = left;

bool cmp(const vector& a, const vector& b) { return a[1] < b[1]; } int intervalScheduling(vector<vector>& intervals) { sort(intervals.begin(), intervals.end(), cmp); int res = 0, end = -1; for (auto& interval : intervals) { if (interval[0] > end) { res++; end = interval[1]; } } return res; }

vector sortArrayByParity(vector& nums) { int left = 0, right = nums.size() — 1; while (left < right) { if (nums[left] % 2 > nums[right] % 2) { swap(nums[left], nums[right]); } if (nums[left] % 2 == 0) left++; if (nums[right] % 2 == 1) right--; } return nums; } */ ~~~~~

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

so many cheater in this round

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

After the cheaters are caught and removed, will rating be adjusted for all participants? For example my profile says my rank is X, but standings say X — Y (Assuming a good amount of cheaters are removed so far). Wondering if this change in rank also possibly means some +delta. Is there an estimate for how long this takes? (I know you guys are working hard, really appreciate it).

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

bssss_a cheater is on 3rd position,wow

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

The rank on my rating board is different from the real one.