I thought Olympiad in Informatics Conference

Looking forward to it.

I just hope everyone gets to learn something and improve their problem solving skills, positive delta would follow!!

Done :)

Fun fact: sszcdjr is homosexual:)

are you cyan at english too?

it is said that the easy version is different with the hard version at all

like 1786A1 - Non-alternating Deck (easy version) and 1786A2 - Alternating Deck (hard version)

Instead of just changing data scale and constraints

like 1856E1 - PermuTree (easy version) and 1856E2 - PermuTree (hard version)

Solving A in 00:00 and 10 unsuccessful hacking attempt ending :P

Meaow!

Love sszcdjr

Nice !

But there are no interactive problems,so forget it.

Sdandy for

September Fools' Day !

You're unrated contestant in last div3

We authors are in UTC+8, and it will be 22:35 for us if the round starts at the usual time. We want to go to bed earlier :)

or maybe it's (no numerical prize in V)OICon(tét)

I thought the round is today my bad.

this is same as what i've figured out :lol:

It happened.

222776617

For me too.

Thought i had D1 in 5 min but after getting 2WA realized i was wrong. Really nice contest!

what's so brilliant about it?

what was div 2d?

How to solve it?

For each element you need to give some power of 2 to someone and also take some power of 2 from someone and for each element not equal to the average of the whole array this give take pair is unique. Also if the sum of all elements of the array is not divisible by it's size then answer doesn't exist.

Let S = sum(a), then obviously we need each element to be S/n. For each element find its difference from the target value. Using the constraints (ie everyone must give and get a power of 2), find exactly how much one must give and get (this is the hard part). Then check if each give has a corresponding get.

Each person needs to gain or lose some amount of candles to reach the average. So $$$a_i - avg = 2^x - 2^y$$$. It turns out that if $$$a_i - avg$$$ is not $$$0$$$, then it is either impossible or there is exactly one way to choose $$$x$$$ and $$$y$$$.

Another hint: Since we use powers of two, think about the binary representations.

Once you compute $$$x$$$ and $$$y$$$ for each person, the answer can be found by considering the set of all $$$x$$$ and the set of all $$$y$$$.

there's at most only a way to make a number that's different from avg equal to avg. Let delta = v[i]-avg. Abs(delta) must be in form "0...01...10..0" and you can just add the first bit before the one part and subtract the last 1 bit (if abs flips the sign you have to flip which bit to add and which to subtract). If delta is 0 you can ignore it, and if it isn't in the case i mentioned, just answer "NO".

Now just count all the bits added and subtracted. If this is even for each bit, then answer "YES". (My code 222771034)

The idea for D2 was to just consider the case when abs(delta) = "0...010....0". In this case you can just give/get that one bit. I'm not sure why my code fails though

My version (propably there are much easier ways):

1. if Sum(a)%n!=0 answer NO. let d be Sum(a)/n

2. Calculate all numbers 2^x-2^y from -10^9 to 10^9 and memorise what x and y are for each of them (with exception of 0 there are only one option for each number). Let's call this numbers "good"

3. Check that d-a[i] is a good number for all i, otherwise answer NO

4. let's call people who need to receive candies before give candies "poor". everyone who is not poor is "rich".

5. let's create four arrays of sets: poor/rich people who need to receive/give 2^x candies. (if someone already have d candies, we always can deal with them). Check that |poorReceive[x]| + |richReceive[x]| = |poorGive[x]| + |richGive[x]|, otherwise answer NO.

6. If there are no poor people, answer YES

7. for each x for each poor in poorReceive[x] if richGive[x] isn't empty remove one rich from richGiveEmpty, remove current poor from poorReceive[x] and add them to richGive[y] (2^y is the amount that this poor need to give).

8. if we did'n change anything in step 7, answer NO. Else, return to 6.

We will not repeat steps 6-8 too many times because there can't be more than ~30 people in each cycle without people who already have d candies.

Div2D once again yeeted my hopes and dreams of becoming CM.

I didn't participate and I might be lying like a bitch with this answer but I think it's ans=min(n+1, m) and if m=1 then ans=0. Think about how you can create a pattern when n+1>=m, and therefore get ans=m. Also if n+1<m you can create a similar pattern but you can get ans to be at most n+1.

Your solution is the fastest :) Do you have a test with TLE?

i handled k<=1 and max(a,b)<=k case separately maybe try to look into that case tho i'm not sure that it'll affect something in ur code or not.

This was my first approach which gave WA. So you are good

this was not it

I checked the balance after breaking the difference of element — avg into two powers of 2(as a swap goes both ways). Any number which is a difference of 2 powers of 2 must have exactly one string of '1s' in its binary representation (we can check using binary subtraction). In other words, 2 ^ (high-bit + 1) — 2 ^ low-bit should be equal to the difference between element and average. Here we are referring to the low-bit and high-bit of the difference. At the end, the balance should be 0 for all bits for a valid arrangement.

Sorry bro, it's true that the score is quite tight and we should have made the score distribution larger for Div1 :(

deserve the downvotes ngl

I know why I got TLE.

I used while ((1 << d) - 1 < n) d++; without longlong so it would loop infinitely.

The first example shows you what to do with 1 avg person (you can just put them into any chain of transfers as they just pass any received candies straight on).

avg can just connect two people. instead of a giving to b, a gives to c, which is avg and c gives to b

Edit: damn i'm always late for comments today

According to rules, anything apart from AC and compilation error runs into a penalty. Compilation error I'm not sure but AC won't result in penalty.

Sorry, we didn't expect D to be that hard :( Some testers thought it was suitable :(