but your k1*x1 does not match in case 1, 22*2 != 43, 15*3 != 43 and 7*7 != 43. Main condition of the problem is ki*xi > sum(xi). You assumed ki*xi to be 43 but your calculations show otherwise.

The multiplication function increases much faster than addition, using 43 as a sample input is flawed checking, 1e9 is a much larger number than 43 and will be much larger than any xi unless ki == 1 in which case there is no solution.

You need to think of a test case where your sum == ki*xi and ki*xi > sum(xi). forgoing one condition to prove another is not the right way. I used LCM btw and not 1e9 but I myself still cannot find anything wrong with 1e9 solution considering the given constraints. It would be great if you could point out the error in the math but as of your comment using sum = 43 is a mathematically incorrect example.

1e9 --> simply if this does not work for max number of coins then it will never work, Probability of the condition working increases with increase in number of coins as Multiplication function rises faster than addition.

LCM --> just use basic algebra on ki*xi > Sum(xi), you eventually reach 1 > Sum(1/ki). Common thing between 1/ki and LCM is that in both cases you ignore common factors or take their frequency as 1.

I can only explain both mathematically because I am used to doing everything this way, maybe writing it out will help you, write the equation down and use a rough graph in 1e9 case if you are comfortable with basic algebra and drawing rough graphs, hope this helps.

Ohh I wish I had skipped B to attempt C first, Bit Manipulation gives me a headache every time. Hope we get more such math related contests.

Thanks for a great contest, maybe I am biased but more math related problems helped me solve 3 (when I usually solve 1 or 2). D looked like fun too. Too bad I can't write basic code, xD.

I work in mathematics related field, trust me the number of times I have read incorrect "number of balls in a bag" in a probability example is probably infinite.

I didn't even think of binary search, I just found the Lowest Common Multiple and it worked. Sum should be < LCM if not "no solution".

IMO "B" was much harder than "C", C was quite easy to pick up from test cases as well as there were not any cases where the most basic logic or LCM might not work. Maybe that's just me but I am pretty bad at anything related to bit manipulation.

And for the cheating part, it has been going on for years, I have seen people cheat from yt shorts and have 1800+ ratings. It's quite common at this point, it doesn't even matter people have been doing this for atleast 3-4 years (as far as I know). If you scour through Yt for video explanations of problems you weren't able to solve you will find a lot of solutions posted during the contest runtime.

I tried difference (Greedy) too, in quite different ways, making array of differences, modifying original array and difference array on each iteration, counting max difference and keep on deleting from the sum. But there is one thing greedy doesn't account for ie repetition in similar differences. Example --> n = 4 k = 2, a = [4, 8, 5, 1] the differences are 4, 3, 4. You chose the first 4 to change, new array is [4, 4, 5, 1] next you choose last 4. final array --> [4, 4, 1, 1], sum = 10 Now in case you choose last 4 to change --> [4, 8, 1, 1] now you choose the difference 7 which gives --> [4, 1, 1, 1], sum = 7.

I haven't practiced DP but as far as I can see from solutions, people tend to be doing similar thing using DP ie a 2D array to keep track of all changes. (I might be wrong on the DP logic since idk how to use DP). But the problem in greedy you faced is same as mine and I presume many more got stuck here.