#### Hello, Codeforces!

IzhtskiyTimofey, qualdoom and I are glad to invite everyone to participate in Codeforces Round 846 (Div. 2), which will take place in Jan/25/2023 17:35 (Moscow time).

This round will be rated for the participants with rating **lower than 0x834 (i.e. 2100)**. Participants with a higher rating can take part in the round unofficially.

You will have **7 tasks** and **2 hours** to solve them.

One of the problems will be **interactive**. Make sure to read this blog and familiarize yourself with these types of problems before the round!

I want to sincerely thank everyone who provided invaluable help in preparing the round and made it many times better:

74TrAkToR for

~~rejection of 10+ tasks~~an idea for a problem, help in preparing the round and excellent coordination!KAN for upgrading the quality of statements.

blobugh, maomao90, maks_matiupatenko, loggerr, vdv09, alex.kudryashov, FynjyBath, alexey.shchepin, Alcabel, induk_v_tsiane, Siberian, polosatic, FedShat and tryharder for testing the round and useful feedback!

MikeMirzayanov for Codeforces and Polygon platforms!

**You**for participating in this round.

This is our first official round on Codeforces. We sincerely hope to your participation. We hope that you will like the proposed tasks!

The score will be announced closer to the start of the round.

We wish you good luck and have a good time! See you in the round!

**UPD:** Scoring distribution: $$$500-1000-1250-1500-1750-2000-2500$$$

**UPD:** Round is unrated. We're sorry — it's our fault.

**UPD:** Tutorial and comment about task C Once again, we apologize for the inconvenience caused.

It clashes with codechef starters 75 https://www.codechef.com/START75?itm_medium=hpbanner_1&itm_campaign=START75. Is it possible to change the time ? Thanks

You should be knowing that Codeforces >>>>>> Codechef.

Codechef tasks can be pretty good too, at least the ones at the end. Well, clashes are inevitable so just upsolve the contest you decide to skip.

their plagiarism checker is extremely bad... their community support is really bad...

I was plagiarised for one contest, in which I solved zero problem, and tried to solve one problem 16 times,,, and still I was plagiarised...

How can you plagiarise someone, who solved zero problems and tried to solve the problem 16 times !!!!!!...

if you copy code from someone, why wouldn't u get it right ???

https://discuss.codechef.com/t/successful-plagiarism/104943/2

UPDATE : I received response from codechef moderator regarding the plagiarism. According to them, I had solved 2 problems in contest and got plagiarised on 3rd problem.

Yup, it always have been Sir. Looking forward to it. will upsolve last 3 questions of codechef (they are worth it though).

Oh no that is an outdated statement. These days codechef problems are really really good.

Well, Codechef postponed it, but now they shouldn't have.

As a tester, the tasks are quite interesting and the statements are clear.

What a joke is this round ? Unrated....

Why

Ccant be solved in given constraints? What's the problem??Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

Maybe there is, u will get a lot of money if you find one

my code is giving 12 answer for this what should be the answer ?

the answer is 13.

input is wrong n = you have given 9 times 1 , i got it now

Sorry about my shit testing(((

Git gud LOL, no harm intended!

It feels weird how this issue wasn't caught by so many people during the setting and testing phase.

i am happy because if this round was rated i would get minus :D

same, i barely made it to 1300 last round

how many questions you solved on this round for now

one completely, but i got stuck on some edge case on second one, not even trying now.

if this contest rated,@huanghaoxiang will get 1400+ rating!

HOw u had only solved A

Probably also c before it got deleted

As a clown**

Tester is me

Tester is me

Participant is me!

best testers

As a tester I can say that I am a tester

Young talent

Yeah

What did you test?

clashing with codechef, it would be great if timing is changed

Maybe codechef can adjust the timing too

I hope you know its codeforces who's helding on unusual time(saturday,thursday, etc), codechef's schedule is fixed

I hope now everybody got the answer Unrated round!! Thanks to the downvotes btw https://codeforces.com/blog/entry/111828?#comment-995528

BRUH MOMENTCome from Real ID :eyes:

😢

On a side note tomorrow's problem are great and well tested :D We hope you participate

Yeah sure 😄 😄

*Clashing with codeforces . You mean right ?? Codechef should change the timing.

I Think it's Bitmask Round , I hope it is a misconception

I hope it is not (I like those type of problems)

almost OrangeForces lol

Codeforces round is not clashing with codechef round. Codechef is clashing with codeforces.

absolutely right.

Meanwhile Codeforces LoversHaha. Light Hearted Neme. Loved it Sir.

Love from India Sir.

I didn't get the joke the first time, sorry.

I take my words back ;(

DISAPPOINTED

omg orange round

Hoping to solve till D in this round.

wish every contester good luck and happy rating++ !

"One of the problems will be interactive."I think it will be "D".

Masters' Round!

Will the rating update of this round before educational #142?

Update: Now the rating has been updated.

What should I do To become Specialist

Practice ..

yes I will Thanks :)

hope i can solve problem C，so that i can change a color 。 i dont like green

this didn't age well

Fortunately, I solved C in the last thirty minutes, but there was some wrong with C。IS i solve C？（cry）

IS THAT A JOJO REFERENCE??????!!!!!!!!!!11!1!1!1!1!1!1!

No, you're watching too much anime.

bruv, the whole world is a jojo reference

Unrated?

yea

I too rushed to see the blog after the announcement.

unranted* they even made a mistake in the spelling TT. no offense

Why will this round be unrated?

The solution of the Problem C which was solved by the author is wrong.

I was off to a great start, and then they make the round unrated :)))))

so C is unsolvable or what?

Idk man, I just used a simple greedy which did pass the protests, but greedy algorithms are hard to prove

Greedy is wrong.

Consider following example: 102 people like dish 1, 104 people like dish 2.

Tables are: 51, 51, 26, 26, 26, 26

Pretests must be weak as shit lmao

I think even setters must have thought greedy was right

It's not that the pretests are weak (the round wouldn't have been made unrated if that was the reason), but the problem setters probably didn't realize that the greedy solution is actually incorrect.

is the answer not 179?

The answer should be 206, right? I think that's what my solution would give?

If your strategy is to assign biggest group of people to biggest table then this approach fails on this test:

1 9 3 1 1 1 1 1 2 2 2 2 4 3 2

answer is 8? edit. got it, 9

It is 9.

Assign 1's to the tables of size 3 and 2, 2's to table of size 4.

My strategy was assigning the smallest that fits the table. That would still work?

1

11 3

1 1 1 1 1 1 2 2 2 2 2

5 3 3

11

Explain your algorithm more deeply since I have misunderstood smth.

Maintain a (multi)set with the group sizes. For each table (sorted in descending order), find the smallest group that has at least that size, and put on the table, and adjust the group size in the set. If none exist, put the largest among the set.

EDIT: I didn't prove correctness, but I tried to anticipate the problem with the direct greedy approach

your solution fails on this test case: 1 10 4 1 1 1 1 1 1 2 2 2 2 3 3 2 2

answer should be 10

1

11 4

1 1 1 1 1 1 2 2 2 2 2

5 3 2 1

Ans: 11

Yes, you're right; I get 9

My code worked too. It gave me result 11

Hello sir, can u tell me ur greedy algorithm?

How about no?

Why not? Round is unrated.

Because its incorrect

Same

Unrated??.. First time solved 3 questions in 40mins

"Unranted"

what an absolute bruh moment

Oh, I think there will be plenty of rants actually...

quite ironic indeed

Solved A+B+C in 26mins , thought I would finally become a specialist :")

But turns out the round is unrated. Sad :(

Anyways, Nice problems , thanks to the authors <3 !

Hello sir can u tell me ur solution for C? I am curious and ur help will be greatly appreciated. Thank you.

It's greedy approach. But will fail on certain testcases. so yeah..... No solution exits in given constraints.

Sad that round will be unrated. Anyway, I enjoyed solving problems, especially D

I was getting some positive delta (110+) after a long time. and now it's unrated. was it really necessary to make it unrated?

Edit:- ohh c is not solvable that's why it became unrated!

Yes, since problem C is unsolvable. The problem setters thought that a greedy approach would solve C but it turns out that greedy doesn't always work. During the contest they realized that C is actually unsolvable within the constraints.

And no, it wouldn't be enough to just not count C towards the ratings, because different people spent different amounts of time on C and it just wouldn't be fair.

What is "can't be solved under given constraints"?? Last I saw, 2752+ correct submissions are there on C

same question?!

Yeah I'm kinda confused since I thought C was kind of easy. Maybe the test cases are weak?

Hello sir, can u pls tell me your solution for C? It will be greatly appreciated. Thank you.

Though the round is unrated it would be great if this is discussed after contest, ig?

did you use greedy approach ??

can you solve for this,,, lets say..

25 people wants to eat dish 1. 15 people wants to eat dish 2.

tables are 15 , 13 , 12 .

greedy wont work here... I was stuck here... also, I got stuck in B somehow... got 3 wrong subs..

is the answer not 38? table 15 dish 1 -> 15 satisfied table 13 dish 2 -> 13 satisfied table 12 dish 1 -> 10 satisfied

Answer is 40.

Everyone who wants to eat dish 2 sits at table 1.

The rest of the people (people who like dish 1) split themselves between table 2 and table 3. Therefore, there are no dissatisfied customers.

why the greedy wont work here? isn't the answer 15 + 13 + 10 = 38?

Answer is 40 ...

we will make 25 dish-1 people sit on 12 + 13 table...

and 15 people from dish-2 on table 15 ...

idk man, maybe pretests are well below the constraints.

Maybe they mean that the

mistakecannot be solved within the time constraints of this competition, as the mistake would need be corrected in just a few minutes.This might make some sense

Nevermind, this comment explains why the greedy (which I at least did) doesn't work.

I suppose they mean the actual testcases, not the pretests (which are not comprehensive).

I skipped C, solved D, and after 5 minutes round became unrated. Not cool.

same

The way it was going was almost sure of becoming CM today and it became unrated

+1

+1

+1

+1

kinda sus

almost 3k people solved a unsolvable problem :/ how? misread? :/

Maybe they used greedy approach, but it was actually wrong.

the round is unranted, not unrated guys.

What does that mean?

that means round is unranted

I hope I get positive ranting delta

nothing here

The problem maker have their faults, but you're not expected to be so rude.

how is problem C not solvable

because it cant be solved using a greedy algorithm. If you have used greedy algo, try this : 7 people want dish "1", and 5 people want dish "2" and we are given 3 tables with accommodation 5, 4 and 3

SPOILER : the solution is 12 guests can be made happy and not 10

Garam krke thanda kr diya -_- .

Lol

Here We Go, After Solving ABC Under 30 mins, the round is unrated. WoW.

I feel you, this was my best performance in a long time and the round becomes unrated

The only reason u solved c is because the problem is wrong

Can u tell me solution for C? It will be greatly appreciated. Thank you.

TestcaseN=17 M=5 Guests : 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 Seats : 4 4 3 3 3

Greedy Answer(Probably Yours Too)16

Something BetterI wanted to know what the greedy solution actually was, cos the greedy solution that I came up with was something I already knew didn't work. So i was wondering what greedy solution others came up with and thought worked but actually didn't

maintain a priority queue and sort b in reverse, and then greedily pop the maximum element from the pq and and assign them to the maximum table currently available, if not all of them fit in that table then add num_of_people — size_of_table to the priority queue and repeat the process. But this fails on so many test cases so yeah

Oh right. That was actually the first greedy solution that I thought of as well. Kinda weird that so many ppl just assumed that it would work when it doesn't.

How is problem C unsolvable ?

Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

Oh! I understand now. My code (greedy) is giving output for this as 12.

But, ideally, it should be 13.

Can anyone explain why Problem C can not be solved?

I think the intended solution was a greedy algo, but it appears, that there are some tests, where it doesn't work

Maybe the intended solution of C is not fully correct and maybe exist some counter case of this solution which makes problem more complicated than supposed to.

Unrated. Thank you so much.

Why even this single comment can receive downvote I can't understand

Why unrated? Sad. I think constraints are ok

Codechef round was postponed for an unrated round.

Who would have thought the sequel would be as good as the original https://codeforces.com/blog/entry/103170 https://codeforces.com/blog/entry/103108

18 coders could not find this before and what were the testers doing. what a waste of time:(

BIG SPOILER !!!!!!...

It is Not... Trust me its not.

Is it ranted?

*unranted

I first time passed pretests in D problem (hopefully AC) in contest , At least there is something to be happy.

same with me first time i did a d problem in contest

What does "unranted" mean?Unrated?

it means whatever happens please don't rant about it

How did so many people get AC in C?

Only pretests are run during the contest and the solutions probably would've failed when run against the proper testcases.

how did the testers code pass then

The judge's code probably used the same greedy algorithm everyone else used. They didn't realize that it is actually incorrect before the contest.

The test data is too weak and the testers used the wrong method to produce the test data.

can we make it the first contest then where editorial is updated before the contest ends.

+165 Delta and it's all gone. Thanks for the great round !

It say's

unranted, what does that mean?!No rate updates for the official participants. You can find your rate history in the graph in your profile.

Can someone explain what they mean by that problem C is unsolvable in given constraints?

my rank would've increased this round :(

This is just sad.

Bye Bye +125. Top 500 performance.

what extension are you using?

https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn?hl=en

Congratulations for not being a guessforces Andy and thanks for adding me to the friends list lol

Thanks. :)

Me too :(

muda muda muda muda muda muda muda muda

bye bye +100 (real)

I was wondering that how come C be 1250 worth of points but seem impossible to me. I am dumb but not that that dumb(hopefully).

It had an easy-to-think-of greed solution, but now it seems to be a wrong one. The correct solution may be the Knapsack problem, but it cannot achieve the required time complexity.

How did so many people falsely solve C? I stared at it for like 20mins and had no idea, but seeing that many people solving it so fast, I started to doubt myself. I tried some stupid greedy ideas but all failed on paper.

Easy hacking greedy passed the pretests.

Given it was only 1250 points, proof by AC is easier to try than a real proof or looking for a counter example :P

Can you please explain what is the issue with the constraints?

exactly what I thought lol

Speedcoding just does that to you

I guess this really says something about how many people "solve" problems by simply guessing a reasonable-looking greedy.

B was guessable too

I am still not sure, how to solve

problem Boptimally...It's ideal to split the array into 2 subarrays.

darn it... I am so dumb :(

I mean maybe, but the point is that C is literally unsolvable — so anyone who actually proves their solutions wouldn't have solved it.

I think the problem is that everybody writing was trying to get AC — and the greedy prrof is somewhat easy to think up really fast. None of the testers really struggled on the task, except me.

The issue should have been caught by me — when we were "testing", I did not manage to solve C (it was B then) in contest, and I submitted like 7 wrong (all greedy) solutions to it. Then, when I was asking the author about the solution, I was told that it is "a simple greedy". Then, I decided to believe him and did not upsolve that task. I should have caught it.

So I think that the CF system of less points with more time will always incentivize this sort of "half-done" proofs.

I proved B before solving it. But when I came to C I just guessed some unproved greedy approach and got WA for silly mistake then I started doubting this approach and couldn't come with another one.

My problem solving skill is slowly goes from random guesses to prove-first approach or even partially-proved approach after watching many streams from tourist, um_nik, and many other legends.

Is this a common thing among highly experienced users when it comes to simpler problems (say div 1 A-C)?

If you go to the "status" page and look at all C AC's, the fact that most of them are 15ms should point at a sub-quadratic solution

I see many people solved C !!

why c is unsolvable!?

why the round unrated?◑﹏◐

Seems that greedy solution of C is not correct

Testcase for problem c that dosent work whit the greedy 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 And there is no solution that will solve this type of testcases that can fit in the constrains

+114 ...and then its unrated

Testcase for problem c that dosen't work whit the greedy metohd 1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5

Great!

don't do it unrated pls

Not Happy with the contest making today :(

This contest is a disgrace to the Joestar Bloodline!

What was the problem with C?

did you use greedy approach ??

can you solve for this,,, lets say..

25 people wants to eat dish 1. 15 people wants to eat dish 2.

tables are 15 , 13 , 12 .

greedy approch will fail,, for 25 dish guests we can pick 12 + 13 = 25 , and 15 for rest.

I see. How did I not see that lol? Speedcoding I guess. What would be a good dp formulation for this assuming bounds are low enough?

after solving A , I tried solving C... couldn't solve that...

it is basically knapsack problem with 'K' sacks given to us...

where 'K' is number of distinct elements given in array.

Is the answer 12 ? I mean its working fine on my local environment. can someone hack my solution please I am feeling to much smart for getting my solution accepted.

u put the 9 ones at the three 3 ppl tables and the 4 guys at the table of 5 and the answer is 13

What the fuck?

The solution is $$$8$$$, not $$$9$$$?

It is 9, author's solution is wrong.

Maybe the standard code also used the wrong greedy method and fails on this.

C looked so hard to me with given constraints. Looked like a multiple knapsack problem. The knapsacks are your guests that like dish $$$i$$$ and the items are the tables. In this version you can keep feeding a full knapsack but gain no score. I tried greedy strategy on papers, they all had edge cases. Couldn't find a dp. Best algo I found was like $$$O(m^{\sqrt{n}})$$$. I really wonder what happened there :)

the dp i came up with was something like dp[i][j]->max satisfied customers considering till ith type and till j seats. so dp[i+1][j]=max(dp[i+1][j],dp[i][k=0 to j] + min(count[i+1],summation till k)) ps:i did sort the tables though

I'm not sure what you mean with "count[i+1]" and "summation till k". Have you tried your solution with the counterexemples to many greedy approaches that were given in the comment ?

Only if the contest makers had a stand for stopping time like ZA WARUDO

Notice that it is

unrantedinstead ofunrated. Does it mean that this round still needs to be rated?UPD:Now this round has becomeunrated. It is really a frustrating round.In an interactive problem, TLE means i am taking more operation than the available operations ?

Read the interaction instructions carefully: "If your program performs more than 30 operations for one test case, subtracts a number x greater than n, or makes an incorrect request, then response to the request will be -1, after receiving such response, your program must exit immediately to receive the Wrong Answer verdict. Otherwise, you can get any other verdict."

why this round is unrated??

sorry to hear that it's unrated..

and a wrong example for many solution including mine:

the answer is 7 instead of 6.

What is that extension bro?

Do you mean why the answer should be 7?

let the room be $$$c_1, c_2, c_3$$$ , then we can match $$$c_1 \rightarrow 2*3$$$, $$$c_2 \rightarrow 1*2$$$ and $$$c_3$$$ the same.

If you use a greedy like me, the match would be $$$c_1 \rightarrow 1*3$$$, which is obviously wrong ;_;

Carrot

sorry, i misunderstood...

it's Carrot, also CF predictor is another good choice.

I'm curious how these testers test this round?

lmao

Bye bye my hopes and chances to become pupil...

Funny that a large portion of the top 100 participants didn't even attempt C because they knew it to be impossible

Trash Russian Round.

There has been 2 times in the past year when CF rounds and CC starters rounds are planned to clash with each other. One of it was postponed both times, and in both occasions, the round that is not postponed became unrated [Lol]

Why the announcement says

Unfortunately, the round will be

unranted. We apologize, we made a mistake in problem C and it cannot be solved within the given constraints.instead of "unrated"?

Unrantedis not unrated, so it's still rated.Well, Unra'n'ted.

So, does the std solve this problem with greedy algorithm? lmao.

answer:

`7`

Could have attended the Codechef contest instead. Whatever ...

That actually has been shifted to tomorrow ,so can be attended .

Good news, thanks!

How to prove B?

If g divides a and b, it divides a + b. That implies [there was typo mistake] gcd(a + b, c) >= gcd(a, b, c), which means that if you have some partition you wouldn't get worse solution if you delete some intervals.

Let's say your optimal answer has k partitions, whose gcd is 'x'. We can merge the first k-1 partitions and the gcd will either increase or stay the same.

Suppose that k >= 3 in optimal answer. Let d be the answer for testcase. Then you can combine some two neighboring segments in one segment and get a solution no worse than the previous one. It's because if d | a and d | b then d | (a+b) and you got answer for k — 1. So in optimal answer k = 2 and you get your solution

you only need to split array into 2, If you get some gcd 'x' by splitting more than once, then you can club all untill there are 2 subarrays because each subarray is multiple of 'x' and sum of them will also be multiple of 'x'.

Why not just remove problem C and extend the round by 15-30 mins rather than declare it unrated?

because some people have spent time on this problem, and some people haven't

Guys go easy on the Downvote Button

Mistakes were made

To all the people that solved C, How did you fakesolved it? I'm interested in the "expected solution".

Greedy. Didn't even realize it was wrong lol

As a contestant it is highly expected to come up fast with a wrong solution by intuition especially with greedy. But as a round tester a plenty of time is there to test the problems thoroughly. Such kind of mistakes wastes time of others.

I completely agree.

Such a frustrating moment solved 3 problems in 30 mins and then what??UNRATED. Good Bye +170

considering solution of B is cringe and everyone typed it without any proof i guess its fair

The proof is simple though. If $$$gcd(a,b,c) = k$$$ then $$$gcd(a + b, c) \geq k$$$ since $$$ k \mid (a + b)$$$.

Hi @AndreyPavlov & fellow setters and testers

Questions are great, mistakes happen! I really enjoyed the questions and logic used. Doesnt matter if round is unrated but I really enjoyed the questions. Thanks for the contest. Much love <3

Indeed. The problems(except for C) are very interesting.

For C,

`1 7 3 1 1 1 2 2 2 2 2 2 3`

Actual answer is 7 with optimal selection`type 1 table 3`

`type 2 table 1, 2`

But Greedy gives 6`type 2 table 3`

`type 1 table 1, 2`

one person with type 2 is not satisfiedVolveré y seré millones

respect. GOA T

Those who solved C what was your approach?

Greedy

I wonder why coordinator and many testers didn't even realize this problem.

Imagine Masters not recognizing NP-Hard problem when they see one.

when masters see NP-Hard problems they say: no problem.

Is C unsolvable? We could just add stronger tests and re-judge all submissions. It is solvable surely because the first AC solutions were by GMs. Would like to know more about the reason behind taking such a big decision, skipping other alternatives like re-judging solutions.

It can be proved to be unsolvable in polynomial time by reduction to 3-partition. The grandmasters who solved it were wrong.

topg for a reason

Can you please elaborate a little?

to prove that a problem is NP-hard you can consider another problem known to be NP-hard, 3-partition in the comment by Everule, and then show a relation such that if this problem is solvable then 3-partition is solving.

this means that this problems is atleast as hard as 3-partition which we do not believe to be solvable in polynomial time.

everule is topG because he never guesses and anyone who never guesses is topG

I see thank you. :)

In C, sum of all numbers is bounded so you can't really make a reduction.

3-partition is only NP-hard in number of elements, not when the sum if bounded

Prolly, I didn’t look into the reduction, was just explaining what the process is

You mean the other way around, reducing 3-partition to this problem?

And even then it doesn't imply unsolvability in polynomial time (probably)

I may have messed up the direction of reduction, because I don't have experience in theoretical CS, but solving this problem in polynomial time breaks the fact that 3-partition is strongly NP-complete. i.e., That even if the integers are bounded by polynomial in $$$n$$$, which it is, the problem is still not solvable in polynomial time.

Let us pick a set $$$S$$$ of with sum and size divisible by $$$3$$$ to 3-partition. We bound every element in $$$S$$$ to $$$sum(S) \times \frac{3}{4n}$$$ and $$$sum(S) \times \frac{3}{2n}$$$. This is also strongly NP-complete. Now we make $$$n/3$$$ groups of people, each consisting of $$$sum(S) \times \frac{3}{n}$$$ people, and tables consisting of the sizes of $$$S$$$. The optimal solution to this is a 3-partition if it exists. Notice that any solution with all must be a 3-partition due to the bounds on set sizes of $$$S$$$.

I just say that if P = NP then you can solve NP-complete problems in polynomial time

That's not polynomial solution, that's pseudo polynomial solution, as the total sum, T, is bounded.

I believe 3-partition can be solved in $$$O(NT^3)$$$ (which is pseudo polynomial) with a 3D DP, similar to double knapsack.

3-partition is strongly np-hard, so probably you can't even solve it in poly-time when the input is given in unary (base 1).

it looks like you are confusing dividing a set into 3 subsets with dividing an array into triplets

edit: oops, looks like it was everule who confused them. you're right that the reduction everule posted is solvable in pseudopolynomial time.

Yeah I was wrong, splitting an array into 3 sets with the same sum isn't the same as splitting it into triplets...

I wonder if it's a first proven NP-hard problem on Codeforces

Yeah, I've fixed the reduction, I messed up while looking for it.

3-partition can't actually be solved in pseudopolynomial time (assuming P != NP). And it's probably a different problem then you're thinking.

The problem is: given an integer B, and a set of $$$3n$$$ integers, partition the set into n groups, such that sum in each group is equal to $$$B$$$.

This problem is strongly NP-complete, so even if the numerical values in the input are encoded in unary (so a value of $$$A$$$, takes $$$A$$$ bits to encode), it is still NP-complete. The reduction from 3-partition to problem C is as follows:

Given arbitrary instance of 3-partition, where numbers are encoded in unary. Then make $$$n \times B$$$ guests, divided into n groups of equal $$$a_i$$$, each of size $$$B$$$. The set of $$$3n$$$ integers S, just make that into $$$c_i$$$'s. Now you can show that answer to problem C for this input is $$$n \times B$$$ iff the instance of 3-partition was solvable, Almost... One problem we face is that inside one bucket there can be more or less than exactly 3 elements. To fix this, we can add a sufficiently big enough number to each number in the set S, and add three times that number to B. This enforces that not too many numbers can end up in one bucket.

And it's a polynomial time reduction, because $$$n \times B$$$ is polynomial in the input size, (and even if you increase by that sufficiently big number, you can still choose that as polynomially as big as the input).

Jeroen there is another cool result, that makes the constraint on triplets quite easy in the wikipedia article

I find it so funny to see many people complaining about the round going unrated saying: "I solved three problems" when they literally fakesolved one of them.

Some of them solved A, B, D. So their complain is genuine.