Haha but you're an LGM... XD

no(

Doubt that the scores will be updated before the next match.

No. It won't be rated for you.

Checkout the magic option at your profile page. You can change your color from there (I am not an LGM :3). This feature gets activated around each new year. Maybe they are not experts, they just changed their color :3

yes (A wrong submission adds to your time penalty).

No! This mean that your penalty is increasing by 10.

At last the fishy thing was Task-C. Weak pretests and some solutions don't make sense

You're definitely misleading people with that photo...

"For example, let the initial positions be x=[1,2,4,4]. The final ones then can be [1,3,3,4], [0,2,3,3], [2,2,5,5], [2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones."

You could infer it from the statement.

I think E was a lot easier than D in Implementation. Though getting the idea was the main thing.

Yes I was also geting WA on tc 4 with my without DP approach I dont know what is wrong

try these cases:

5
2 3 3 3 4

ans: 1 5

9
1 1 2 3 4 6 7 8 9

ans: 3 9

Greedy problem using a priority queue (min heap) and a flag checker.

you can keep minimum distances in the queue

For example, n = 2, m = 3, x1= 1, x2 = 5 Then initially, you need to push (0, 1) and (0, 5) // (dist, position) and set(1) = visited and set(5) = visited

If -pq,top.first != 0, then add this position to your answer array. and check whether you can insert position+1 and position-1 with your checker. If position+1 is possible, then push(-(dist+1), position+1)

until you gather m position

dp i maintained 3 states, first calculate frequency array for input from 0 to n+1 and if it is greater than 4 make it 3 States are as follow: 1) idx : index of location or houses 2) x : number of friends previous location is asking to me 3) y : number of friends i will give to next location

Greedy af

Yes. I managed to solve it using something like bfs. Submission : LINK

Yup, you can have a look at this — https://mirror.codeforces.com/contest/1283/submission/67841418

I would say it is half-similar :) Btw I cannot understand how didn't I remembered this problem, lol.

Except for the fact that we couldn't go from 1 to 0 in the old problem

this happened with me in E , i solved very late and forgot to memoize the dp.Till then i memoize it time was over :(

Try this:

3
1 1 3

output should be 1 3

Max can be computed by sorting the array and greedily shifting elements as left as possible to maximise the houses occupied. My logic is going wrong on min (So I don't know)

Looks like a good round is going to be unrated :(

WHAT????

Hacked it, thanks

5
5 0 4 0 0 is what I used

I also have the same doubt, eg 5 4 0 0 1 2 ans- 5 1 2 3 4 is also getting accepted

it is clearly stated that you have to fill unknown values(zeroes)..

I had the same issue!

https://mirror.codeforces.com/contest/1283/submission/67820013. Here you can see my first implementation using unordered_set. This submission received TLE on test case 6.

https://mirror.codeforces.com/contest/1283/submission/67838787. AC submission. In this submission I only changed the unordered_set to set.

Initially, I thought that this discrepancy was due to unordered_set having a very large constant factor, but the strange thing is that it seems that in general, unordered_set performs better than set for this implementation. For example, in test cases 3, 4, and 5 (which all have very big n), the unordered_set implementation has about 1.5 to 2.5 improvement over set in runtime. It seems that test case 6 is an outlier where unordered_set performs at least 5x slower than set.

I didn't know that unordered_set could be exploited. Is there a different reason that this may be happening?

umap uses an inbuilt hash function to map the values and as you all know that hashes are collision prone hence that TLE you got.umap is O(1) as long as it doesn't face collisions but as collision increase its complexity turns O(n), it's basic knowledge.

Yeah, because unordered_map can have a lot of collisions because it's implemented as a hash table...

Rated!

It appears the person who you linked got hacked. Did anyone else get affected by this error?

If not, even if there was an error in the checker, nobody really got affected. I don't think the round should be unrated in this case.

I think you should make it unrated for only affected people, so every one wil be satisfied :D

Will hacked solutions be rejudged?

Rated!! It isn't the checker's fault if people randomly submit without testing sample cases.

vovuh you are a lucky guy! The round is rated!

Only 15 official participants have been affected noticeably by the issue in the problem C checker: I reviewed all the verdicts after the final testing and found such submissions that failed on the examples (but didn't fail on them while the contest). Only 9 of them have non-positive rating changes. So I excluded all of them from the official participants. They are:

• jainbishay
• emoseW
• coderr20
• dedpoolman
• akash_baghel
• neew_B
• avi_cr7
• iamprayush
• chuka231

Miracles happen! Happy New Year!

Well I think there is some problem in judge that is leading to all those hacks

3 0 0 1

I think it's wrong to change a value that's not 0.

The probability that a random permutation is a derangement is approximately $$$1/e$$$, and that is dense enough for randomised solutions to work.

You can maintain two sets:

The one which are bad positions set (i.e Index = unfilled element in array) and the other good positions set(i.e are missing from array but no problem as their value != unfilled_position in array)

Now, you just need to handle the bad positions set first.

I did it in the following way, there can be various other ways.

for example, if my array was 3, 4, 6 of bad positions. I would circularly assign positions, example a[3] = 4, a[4] = 6, a[6] = 3;

and for the remaining 0's positions, you can assign as you wish from good_position set.

Here is my submission — https://mirror.codeforces.com/contest/1283/submission/67828215

I listed all the ones who did not give gift and all the ones who did not receive gift. sorted these 2 lists.

compare a[i] and b[i] 

if equal:

swap a[i] and a[i+1]
5
2 1 0 0 0

a=[3,4,5]
b=[3,4,5]
i=0
a becomes [4,3,5]
i=1 
a stays the same
i=2
a becomes [5,3,4]

Let s be the set of people who didn't give their gifts yet. Let t be the set of people who didn't receive their gifts yet.

For every person in s, assign to him any person (different from him) in t. Note that this is possible for all people in s except the last one (If we assign greedily). However, it's guaranteed that at most 1 person will be assigned to himself. Assume this person p exists. To fix this issue, choose any person (!= p) in s (This is guaranteed since it's given that the size of s is at least 2) and swap his answer with the answer of p. Done :)

Already found my mistake. :"D

issue resolved -> https://mirror.codeforces.com/blog/entry/72541?#comment-568531

old version cannot become equal to zero and no more than n. but this not, max result can greater than with n + 1

https://mirror.codeforces.com/contest/1203/submission/67844337 this code solved both problems , just change variable prev initial value

Stop crying for that now . Lets see what vovuh ans mike decide .

2
1 3

I think your solution will fail on this

4
1 2 4 5

well i was stuck on max so i used your idea and got AC. here is what I did for min:

sort array and remove duplicates in array

last = -2
for( i=1;i<array.size();i++) 
    if x[i]-last >1 :
        x[i] += 1
        last = x[i]
    
    else:
        if x[i] - last ==1:
            x[i]-=1
            last = x[i]

then you count all unique numbers

Update : Done ! Code : https://mirror.codeforces.com/contest/1283/submission/67847724

Special Thanks to stefdasca and tribute_to_Ukraine_2022 for providing valuable inputs whether related to test cases or the code/approach itself !

I think stefdasca's idea to find min is really really simple ; both to think and prove ; those benefitting from this discussion should really look into his code https://mirror.codeforces.com/contest/1283/submission/67847914

https://mirror.codeforces.com/blog/entry/72541?#comment-568517