Sorry, no java code. But the programming is simple (unless you are having trouble with the interactive I/O - if that is the case then say so). This problem is more a puzzle to find the right strategy for picking numbers.
The problem works like this: You pick 100 different numbers between 1 and 10^9. Then the computer sends you 100 other numbers in that range. And you have to then submit a subset of these numbers whose sum is half of the sum of all the numbers. (The problem statement says N numbers, but in the test set details, it says N will be 100. It is important to check these details, because they can make a big difference in how you choose to write your program.) There is no guarantee the computer will pick numbers that give you a valid solution. You are only told the computer will pick numbers that make the sum of all the numbers even. And you should notice that you are not permitted to send the word IMPOSSIBLE if there is no valid solution (as some past problems have permitted). If you pick numbers poorly, and there is no valid solution, you just end up having to submit a wrong answer. Since it is interactive, rather than having fixed test sets, you should assume the computer is malicious, and will choose numbers that give no solution if you give it the chance. So you should pick good numbers. You should ensure that subsets of your numbers can sum to any number from 1 to 10^9. That way, after you get as close as possible to half the sum using the other numbers, you can use yours to make up the difference. One strategy, which I used, and which is described in the analysis, is to use binary. Start your set with 1, 2, 4, 8, ... 2^29. You can make any sum from 1 to 2^30-1 using these numbers, and since 2^30-1 is greater than 10^9, it covers the necessary numbers. That is only 30 numbers, so pick 70 other numbers without repeating any. I used the smallest numbers not yet used (3, 5, 6, 7, 9, ...). Given that, you can use a simple, "greedy" algorithm with the other numbers. Add each number to the list you are going to submit, if and only if it does not make the sum too big. If you reject any numbers in this way, since each can be at most 10^9, then you are within 10^9 of the target. If you don't reject any numbers, you will be within 2^30-1 of submitting ALL the numbers, and so rather closer to submitting half the sum. The remaining difference will always be a number you can construct with the binary numbers. After this, the program is simple. 1. Send your numbers - you can use the same set of numbers every time. 2. Read the numbers the computer chooses. 3. Sum all the numbers. 4. Take half the sum - this is your target for the sum of the numbers you submit. 5. Prepare two lists. Your binary numbers in one list, and the other 170 numbers - the ones the computer chose and the extra 70 numbers you picked which are not powers of 2 in the other. 5. Go through the "other" list. Add each number to the list you will submit if and only if doing so does not make the sum too large. 6. Find the difference between your target and the sum of what you have selected so far. 7. Write this in binary, and append to your list just the binary numbers which will make that sum. For instance, if you were short by 17, you would add 1 and 16 to what you collected. 8. And send the solution. On Sun, Apr 24, 2022 at 8:21 AM Aayushii Dassani <aaayushi...@gmail.com> wrote: > can someone help me understand the question clearly and with java code as > well. > only cpp and python is visible. > > -- > -- You received this message because you are subscribed to the Google > Groups Code Jam group. To post to this group, send email to > google-code@googlegroups.com. To unsubscribe from this group, send email > to google-code+unsubscr...@googlegroups.com. For more options, visit this > group at https://groups.google.com/d/forum/google-code?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/16aeb752-6e17-4fef-96c3-72b0ed3fc346n%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/16aeb752-6e17-4fef-96c3-72b0ed3fc346n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- -- You received this message because you are subscribed to the Google Groups Code Jam group. To post to this group, send email to google-code@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/google-code?hl=en --- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzhmgUHkCsHkdcGJrhwjYwBoYneP2CYsafVS-cD6gv6A2A%40mail.gmail.com.
