Want help with a question.

Question

I understand the question, but not able to get the answer they gave.. A simpler explaination would be appreciated! Thanx in advance

Given below is a sample problem:
Given n numbers such that their sum is not divisible by 4, remove k numbers such that after every removal, the sum of remaining numbers is not divisible by 4. Find the maximal sum of n-k remaining numbers.

Solution:
Divide the initial n numbers into 4 separate arrays corresponding to the 4 different remainders they leave when divided by 4. Now, sort them. Lets call these arrays a0, a1, a2, a3. Now, if say the sum of n numbers is divisible by 4.
f(k, a0, a1, a2, a3) = max {f(k-1, a0, a1+1,a2,a3), f(k-1,a0,a1,a2+1,a3), f(k-1,a0,a1,a2,a3+1) }
If the sum upon dividing with 4 gives a remainder of 1, we would have considered the arrays a0, a2 and a3.

Test case: n = 10 {44, 12, 45, 23, 22, 34, 47, 37, 50, 31}, Sum = 345

Answers:
k = 1, 333
k = 2, 311
k = 3, 2791
k = 4, 257
k = 5, 223
k = 6, 186
k = 7, 142
k = 8, 97
k = 9, 50
k = 10, 0

Answer 1

KrOW the question, solution, test case and the outputs aren't mine, they were on a website so the solution is their's. I haven't made any code using that algorithm. In their solution they have a func `f`. I don't know what's that and why they have subtracted 1 from k and added 1 in a1.

Answer 2

32 doesn't need to be in the set. When k = 2 we are selecting 2 elements from the given array (the number of ways we can do this is 10C2 = 10!/[(10-2)!*2!] = 45.), removing them from the original array, (hence we get 45 different arrays) and then selecting that array which is NOT divisible by 4 and who's sum is Max as compared to other 44 arrays.

This was just to get a clearer idea of the problem. I tested with other arrays and found that the difference of the outputs is not necessarily in the given array. I'm not sure tho.
Anyway, the original purpose of this post was to understand their approach to this problem..

Answer 3

KrOW thanx for replying again! Yes I've copied everything correctly. Did you succeed in the first two outputs?

Answer 4

Yes sure.
https://m.techfest.org/CoDecode/competition
In the "Format" section

Answer 5

KrOW so I made a code with my approach. And the output for k=3 is 279, but they have written "2791", an extra 1 is present. Apart from that everything looks correct.
Here's my code:
https://code.sololearn.com/cuccVX8Lz56T/?ref=app

Answer 6

I understood the question but not able to get their solution :/

Answer 7

Zuke exactly. I don't know what's happening there... Their solution is so confusing. You might wanna read our replies above ^

Answer 8

Also donno what f is

Answer 9

Zuke I got the answer (https://code.sololearn.com/cuccVX8Lz56T/?ref=app) but the algorithm I made is different than in the solution I posted. I want the explanation of the answer in the original post.. What they have done is incomprehensible to me /:
and I delet discord so no discord anymore

Answer 10

Hey, KrOW!
So I mailed the site's people telling the mistake at k=3, and they updated their site (https://m.techfest.org/CoDecode/competition) so it's now 279 instead of 2791.

So the answers are

k = 1, 333
k = 2, 311
k = 3, 279
k = 4, 257
k = 5, 223
k = 6, 186
k = 7, 142
k = 8, 97
k = 9, 50
k = 10, 0

Answer 11

Can you post your code so we can better understand your algorithm?

Answer 12

ok... i don understanded why answer when k=3 is 2791... Its all copied correctly?

Answer 13

Maybe i have understanded what problem want but can you post source problem link?

Answer 14

For me answer sample its wrong... at k=3 answer would be 288
(311-23=288) and this match with answer at k=4 (288-31=257)

EDIT: i have not thinked that this break "not-divisible by 4" rule then its wrong. Anyway i continue to not understand sample answer at k=3

Answer 15

yash Then subtractions are not "cumulative" between succesive 'k'.... Anyway understand approch REQUIRE understand the problem 😉

Answer 16

Hello, the question looks awesome! What I don't get is how are you adding a one to the arrays? is it "a1 + [1]. . ."?

Answer 17

The most confusing part is that it has to stay not divisible by 4 throughout every removal :/

Will you be on Discord if I find the answer?

Answer 18

that was a little selfish, if 'we' find the answer...*

Answer 19

Sorry but at k=2 in your code answer is 311 while at k=3 answer is 279. Now, 311-279=32 BUT 32 NOT belong to n set (which is {44, 12, 45, 23, 22, 34, 47, 37, 50, 31}) then you cannot subtract it... Or i have not understand at all that contest, or solution reported its wrong... For me answer is this at sample:

Sum: 345
k=1 ... -12 => 333
k=2 ... -22 => 311
k=3 ... -34 => 277
k=4 ... -23 => 254
k=5 ... -31 => 223
k=6 ... -37 => 186
k=7 ... -44 => 142
k=8 ... -45 => 97
k=9 ... -47 => 50
k=10 ... -50 => 0