CodeJam Round 1A 2022
source link: http://codeforces.com/blog/entry/101738
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By mon0pole,
23 hours ago,
As I didn't find kostka's blog for this round, So posting this blog
Round Link
I was only able to solve first problem
Please share your approach for problem 2 and problem 3
Problem 2: first 30 numbers are 2020 to 229229, then 70 random trash numbers (I used 106106 to 106+69106+69 and added all those as the 70th number.)
When the judge gives you the B array, you try to minimize the difference between the two subsets that add to B (i.e. ignoring A) You do this by maintaining the difference of the two subset sums, and if the first sum is larger then insert the current element to the second; else insert into first. You can keep the difference under max(Bi)max(Bi).
Then you just use the 2020 to 229229 to make up for the difference (grade school math). Finally output the smaller-sum subset with the adjustments, and also output the sum of the first 69 trash numbers (i.e. the 70th trash). You're done!
-
elaborating on the last sentence: you need to find the sum that you are looking for, then greedily add numbers from array B until you are less than 109109 from the target sum. Say that you are kk away from the target
After that, you can use the binary representation of kk to write it as a sum of powers 20,21,...22920,21,...229, obtaining the desired sum.
-
Can you share your thought process on how you came up with the first 30 numbers being powers of two?
-
Well, I probably wanted the A array to be more dynamic and cover a wider range of numbers. Also I wanted to let the A array cover a list of adjacent integers. So I came up with the binary representation.
-
-
Same, but I didn't handle difference between two subsets. If sum of all numbers is SS then we just need to get S2S2 sum in first subset. We can get any number in range [0,230−1][0,230−1] using powers of two, so just take some numbers from trash and given array while desired sum is bigger than 230−1230−1.
23 hours ago, # |
Who else spent 1 hour on B and then realized NN is constant?
And why wouldn't they emphasize such a thing since the sample contains N=3N=3 !!!
23 hours ago, # |
Problem C is range DP. Let dpijdpij be the answer to the given problem if we only considered exercises ii through jj. Then, dpiidpii is simply twice the number of weights needed for exercise ii. We can compute dpijdpij for i<ji<j by first placing all weights that are included in all exercises ii through jj (let there be NN such weights), and then iterating over the next exercise kk after which only these NN weights remain (it can be shown that such a kk does exist, satisfying i≤k<ji≤k<j: try to prove it!). Then, we have dpij=minkdpik+dp(k+1)j−2Ndpij=minkdpik+dp(k+1)j−2N, subtracting 2N2N because we do not need to remove these NN weights after exercise kk or add them before exercise k+1k+1. Our answer is then dp1E.dp1E.
We can precompute the values of NN for each interval in O(E2W)O(E2W) time, and we can then handle our DP in O(E3)O(E3) time, giving an O(E2(E+W))O(E2(E+W)) solution, sufficient to pass easily.
A screencast of my third-place finish will be uploaded to my YouTube channel tomorrow.
For problem 3 I managed to pass test 1 using BFS, the node is a state composed of the current exercise I want to do and a string representing the current weights on the machine.
Edges go out like this:
With the current set of weights do as many exercises as you can (1 edge)
Remove the topmost weight if the string isn't empty (1 edge)
Add a new weight (at most 3 edges)
22 hours ago, # |
I wonder if anyone solved a problem using Punched Card Python...
22 hours ago, # |
Although I get a perfect score in the end, I am still astonished by the speed of the top contestants. How did they finish the contest in just 20 minutes? 20 minutes is just enough for me to finish first problem.
Also, I struggle for the third problem for almost 2 hours. I tried greedy at first, failed and failed again, struggle for an hour, then I found I need divide and conquer with memorization. I can imagine that if first two problems have more difficulty, I will not able to finish third problem. I am wondering if I can pass round 2.
My suggestion for Code jam is that, if you are under 2100, never try the large test set directly except for the very easy problem. Try to brute force and pass small test set first, then you can use your brute force code to get the correct answer for arbitrary small input, and this can help you examine your formal code to avoid unnecessary punishment.
Another suggestion is, learn how to use the test tools to test your code quickly in interactive problems, it is really helpful and can save you a lot of time in the contest. Download both local testing tools and interactive runner, and read the comments of interactive runner carefully, you will now how to test your code.
21 hour(s) ago, # |
Can someone explain to me why this is getting TLE submission
Anyone managed to solve problem C (weightlifting) in python without TLE for test set 2?
13 hours ago, # |
In problem 2, I reached the observation of powers of 2 quickly. But my main goal was to use the binary representation of the difference and use powers of 2 accordingly, but was stuck at the unused powers (they cannot be known in advance). I eventually found a bit complicated way to accommodate for this but unfortunately ran out of time.
Later, I knew from the editorial how this can be simplified using the observation that any odd number can be constructed using all powers of 2 (by putting some powers with positive signs and others with negative signs), e.g., 0 0 0 0 1 0 0 1 is equivalent to +1 -1 -1 -1 -1 +1 -1 -1.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK