[contest:1048] was decided to be unrated because of a major issue in Div.2 D / Div.1 B. The statement missed an important condition (operation 2 can only be performed once), which resulted in the solution being incorrect on the following countercase.
1
3 1
3 4 1 2
1 4
Because of this, several top participants were unable to solve the problem, which was why we decided to make the round unrated.
The problem was originally used as a B, which only had a single query, and at that point, the statement and brute force were both correct. When we decided to change it to a D, I thought that the solution is the same without the condition of "operation 2 can only be performed once", so I removed it to make the statement cleaner. The brute force solution for D was a $$$O(n^3)$$$ check for $$$a_i \gt a_j \gt a_k$$$ since we already tested that in B, but did not realise that the condition might have changed after removing the condition. Hence, we did not manage to catch the mistake when stress testing the modified D.
I admit that this is fully my fault, and I take full responsibility for this issue. I hope that the announcement blog for round 1048 will stop being downvoted, and all of you are free to downvote my blog instead. The authors worked very hard on this round, and it was fully my fault for suggesting the wrong change, and not checking the new brute force and stress tests properly before the round was scheduled. I am very sorry for disappointing everyone, and I will be more careful in the future to ensure that this does not happen again.
Okay
Line 2 should be
4 1.all the try in vain
please try to avoid last moment changes. no problem.
[Deleted]
This's the best achievement ive ever had, it’s a pity to hear that
my best performance in d2 got in vain
same bro
Yeah，the decision of "unrated" made me really disappointed.
Did you not have an exponential bruteforce?
We had an exponential brute force for the original simpler version of the problem, which was meant to be a B. We did not have an exponential bruteforce for D later on as we assumed that it was correct based on our previous stress testing on B, but we forgot that the statement was slightly modified which resulted in the mistake. This was due to my carelessness, and I will take full responsibility for it.
Is it not required to have full written proof together with bruteforce? Why is an assumption involved? I'm so confused on problemsetting process.
The chance of back to GM has been rained. What should I do?
Catch the next opportunity, i believe you can have bring your best on next competition
I think it's funny how many Div1 people assumed 3 2 1 was a sufficient condition and did a proof by AC. I only caught the 3 4 1 2 case because I had a bug in my 3 2 1 code.
did anyone find a correct solution for the original problem?
wth, why u are always in blue
Both last goodbye round and this round told us a lesson: always write the purest brute force solution.
In this round, I think the preparation of problem is not up to the standards because, as you said, you used the conclusion of $$$a_i \gt a_j \gt a_k$$$, which at least used some observations and is not the purest brute force. However, the purest brute force which works in $$$O(n!\cdot n^2)$$$ can run under $$$n\le 6$$$, thus will avoid the issue.
*always use the purest brute force solution that you wrote
So how to prove the conclusion for the d2D/d2B? (Just need to check $$$a_i \gt a_j \gt a_k$$$)
I'm curious about it.
Remove all inversions between a_i, a_j and a_j. Now they're adjacent and you can use the operation to remove 3 inversions in one operation. That proves that if a_i > a_j > a_k then there's a way to use less operations.
To prove that it's necessary, you have to look into how the inversions change when you do the second operation. It turns out that it always removes at most 1 inversion unless it's 3 in a row perfectly non-sorted (which removes 3 inversions).
We just decrease the number of inversions by 1 with each operation 1. Then if we can only use operation 2 once, then only if there exists $$$a_i \gt a_j \gt a_k$$$ can we decrease the number of inversions by 3 with operation 2 once, besides we cannot decrease it by more than 1 in other cases.
Normal distribution chart meme.jpg
ones solved this problem quickly like me could create condition out of nothing
I'm just wondering why this problem was discovered near the end of the contest (2.5h)
the fun thing is all AC solutions(including my) was actually incorrect[] it says a lot about society> most of us not actually make proofs for our solutions{}
waiting for that future bro.
This was my first ever E solve sadge
Me too,bro.But it was all in vain. I'm very angry now.
so depressed as you.
I think its an ok problem with this statement too.
The array is perfect if and only if there is no $$$[3, 2, 1]$$$ and $$$[3, 4, 1, 2]$$$ type subarray.
What is the best way to find 3 4 1 2 subarrays? I couldn't think of a good way to maintain them. Some sort of keeping track of max3 max4 min1?
Seems possible with scanning + simple min-segtree. Credit: toam's "correct" solution
Is it possible without segtrees?
I also struggled finding it (>1h30m of the contest). But it turns out it's trivial via walking on segtree (you can even do it only with sparse tables).
Ie, you find the first element greater than a_i to the right of i, a_j. Then you find the first element smaller than a_i to the right of j, a_k. Finally you find the first element smaller than a_i to the right of k, a_t.
I handle this subbarray like [big, big, small, small] (if that subsequence is not $$$[3, 4, 1, 2]$$$ there is a $$$[3, 2, 1]$$$ subarray).
Initially all elements are small, and I flip them one by one. In each change there are only 2 options to check. It's solvable with sets in $$$O(n*logn)$$$
Here is my (probably correct) solution: 337653213.
Clever idea
use segment treeto save the nearly 1,2, and find 3 for every 4, then save the position of 2 on 3, when query a segment [L, R], return the maximum value and check if less than L.
3412 would be just 4 consecutive elements or there would be 321 if they're not consecutive
UPD: Claim is wrong, counter test = [4,1,5,2,3]
What do you mean by 3 4 1 2 type subarray. Does it mean that subarray becomes sorted after (1,3),(2,4) swaps ?
can you check it for array 5 2 3 4 1. we can sort it using 3 op2 but it would require 7 op1. so the array is not perfect.
Pls correct if i am wrong
Your array has a 3 long decreasing subsequence. $$$5, 3, 1$$$
Ohh my bad, i thought of subarray and not subsequence. Thankyou
I mean, you did specifically get told $$$[3,2,1]$$$ and $$$[3,4,1,2]$$$ type subarray, so that's just not a you error.
I guess the constraint would be the lack of $$$[3,2,1]$$$ and $$$[3,4,1,2]$$$ type subsequences instead.
Yes, it should be subsequences instead of subarray
Well could you please explain how to prove this? I have spent a year trying to prove this conclusion during the contest, but failed.
how did you come to the conclusion that these are the only 2 cases that needs to be checked?? how is only checking these 2 conditions will be enough? dont just give a statement and disapperar, dont leave us hanging here..
“Let me return the favor: here’s a theorem, no proof attached.”
1 + 2 + 3 + 4... upto infinity = -1/12, and no it's not something i made up, it really is -1/12You see now how frustating it is for non gm people like me to be able to read your comments and not understand anything.
It's all right guys mistakes happen . If this round would have stayed rated most probably I would also have a positive delta yet we must understand that sometimes people do make mistakes.
:(
Its okay Buddy! we are humans we make errors!
It's okay. Thank you for noticing and correcting your mistake.
So the condition is valid if you can use it only once?
1st time solve A,B, C in div 2. Within 1 hour 5 minutes. Bad luck
wasted three hours
It's a waste only if you did not attempt the problems
make it rated for the people that increase because they spend 3 hours and unrated for the people that decrease and we understand that we are human and we can make mistake and thanks for your efforts ^_^
Maybe you can try to change test cases instead of making the round unrated
It is a very unfortunate situation, though I think no-stress-test is very justifiable in this case, and it is just a consequence of actual issue, which is reckless change in statement. I wonder if it is possible to automatize catching mistakes in statements like this one using LLMs now: I mean, prompt LLM with problem statement, and ask to implement bruteforce, and check if it is correct on small-tests-generator, and if it is not, raise a red flag to setter/coordinator to investigate, obviously if LLM is trash, there are gonna be many false red flags, and it will be very tiring to distinguish them from actual issues with statements, but I think we are already in a time where LLMs are able to implement bruteforce solutions to 99% of problems without a trouble (if not now, then surely in couple of years), and if its not capable of doing that, it is most likely an issue with statement being unclear/incorrect
can't blame author on this one cause i got same intuition
Okay ,got rank 126 and expected a huge rating delta and found this round unrated. Thank you.
p.s. I'm not blaming the author,I knew it's not easy to write a perfect contest,but still it's a bit disappointing for myself
What a pity of a great contest.
What responsibility do you have to bear? Just one apology? One apology would have wasted the time of so many people. My entire day's mood was ruined because of your one-size-fits-all approach.
Actually I think this doesn't affect much... But I still didn't solve it because I guessed the conclusion wrong
How dare you are. We cant expect like such a big platform.Like codeForces.
no worries!
But it's okay. don't worry much.Sorry for the harsh comment earlier. I mean if I was to write a contest, It would have took me days to write one. P.S. I only solved one problem !
days????? it can take months to write a contest, even for teams of multiple masters/grandmasters working together... and you think a singular gray can write a contest in days?
I said if I was to not that I can. So I meant that if I was in the place of them creating it , then . Also , by days I meant 100-300 days.
I'm sorry if I came off as rude, but to me, it seems like you are underestimating how much work goes into making a round. I personally find this a little bit offensive, so I'd like to clear the misconceptions.
In some cases, it can take 100-300 days for a GM to come up with a single good Div1 problem, let alone an entire contest. Please do not think of contest-writing as easy. A lot of work goes into it, and we should be grateful to the authors.
Yeah, that's fair — I agree, writing a full contest, especially for Div1, is a huge task and takes a lot of time and effort. I definitely respect the authors and all the work they put in. My earlier message wasn’t meant to downplay that. Just wanted to clear that up . ^_^
hey bro.i like ur div3,I didn’t think I will meet u here,this world is so small.