Round 1 will last 24 hours and start December 7, 2013 at 10:00 AM PT.

The top 500 people will advance to the Round 2. In addition, anyone that scores the same number of points as the person in 500th place will also advance to Round 2

• +69

 » 8 years ago, # | ← Rev. 2 →   +17 Where is the announcement? Like it was in qualificationUPD It was boring to debug "Labelmaker", until I got output PKUPERCUPTEAM
•  » » 8 years ago, # ^ |   +4 The link is posted. Good luck!
 » 8 years ago, # | ← Rev. 2 →   0 Why I can't get access to tasks round 1?This link don't work.
•  » » 8 years ago, # ^ |   +33 It should work, so sorry for the silly question: have you solved at least one problem in qualification round about 2 weeks ago?
•  » » » 8 years ago, # ^ |   0 No, I don't know, sorry.
 » 8 years ago, # |   -6 Can anyone explain me third case in "Coins Game". Of course if it isn't illegal.
•  » » 8 years ago, # ^ |   +7 I believe any discussion is illegal. Solution on specific test case can help you to solve problem.
•  » » 8 years ago, # ^ |   0 Considering it's a small case, you can solve it yourself, manually. Just write the possible arrangements and strategies on them on a paper, and try to see which is the best one.
•  » » » 8 years ago, # ^ |   0 Yeah you are right. I thought a little bit , then i found optimal arrangement.
 » 8 years ago, # | ← Rev. 2 →   0 Что должно выдавать в D(40) на тесте N = 20, K = 1, A[i] = 50 (для всех i = {0, ..., 19})? А еще спешу огорчить тех, у кого в B(20), на тесте 3 7 7, выдает 9:(
•  » » 8 years ago, # ^ | ← Rev. 4 →   -16 У меня 647.О, а как тогда B решать?
•  » » » 8 years ago, # ^ |   +18 У меня 643. Мне это уже не нравится)
•  » » » » 8 years ago, # ^ |   0 Вот теперь это уже не нравится мне :D
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   -8 А, фух, не ту задачу посмотрел, 643, всё ок.
•  » » » 8 years ago, # ^ |   +14 Case #1: 64351 53 58 59 61 65 67 71 73 77 79 83 89 97 101 103 107 109 113 127
•  » » 8 years ago, # ^ |   +16 643.
 » 8 years ago, # |   0 When will results be announced ?
 » 8 years ago, # |   +9 Can someone explain their solution to the 40pt question?
•  » » 8 years ago, # ^ |   +3 I tried dynamic programming with a state of dp[N]{set of primes used} = minimum cost.On its own that wasn't fast enough, but it was possible to prune the search significantly by calculating an upper bound on the answer with a simple greedy algorithm and rejecting anything which would lead to a cost greater than that.
•  » » » 8 years ago, # ^ |   -8 How many primes do you need in the worst case to generate the answer?It seems that very stupid upper bound is 36 (number of primes greater than 50) but then the number of states is huge.Did you use map for memoization?
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I tried all coefficients up to 500 and, yes, used a map. eduardische's comment looks like a better way to keep track of state, assuming it works.Code here (guaranteed to not be correct).
•  » » » » » 8 years ago, # ^ |   +3 20 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 answer = 19, cause you cant left 0, cause gcd(0,2) = 2 :)
•  » » » » » » 8 years ago, # ^ |   0 Should not this case be caught by the last example?
•  » » » » » » » 8 years ago, # ^ | ← Rev. 3 →   0 Yeap, seems like, but i checked my test on hex539 solution, and he has 18.But may be no, cause on last sample you have to keep one zero, but in this case you have to remove all of them.
•  » » » » » » » » 8 years ago, # ^ |   0 It's 18, because you need just 18 ones, one zero and one 2.
•  » » » » » » » » » 8 years ago, # ^ |   +16 Yeap, but gcd(0,2) = 2, and 2 > 1.
•  » » » » » » » » » 8 years ago, # ^ |   +8 Oh... whoops. Well, I wouldn't have points for that problem anyway, I just did a simple backtrack (I've got nothing to lose by trying :D).
•  » » » » » » » » 8 years ago, # ^ |   0 Ah I see, the last example is only there to ensure that noone misses the edge case (0, K, ..., K) and that is different from your test
•  » » » » » » 8 years ago, # ^ |   0 Thanks, I've updated my comment.Looks like there are several nasty edge cases. This solution could probably get around them by having an extra bit of state, [used_zero].
•  » » » » » » » 8 years ago, # ^ |   +5 The whole case "any number is zero" can be gotten rid of quite simply. If there's any zero in the solution, all other numbers must be K; otherwise, just increase all zeroes to ones.
•  » » » 8 years ago, # ^ |   +27 We can notice that it is only worth using primes >50 on its own, so we can have dp[N][mask][order of first unused prime >50]. This adds an extra dimension of N size but reduces the amount of primes to 15.
•  » » » » 8 years ago, # ^ |   +8 If you sort the ages and process them in the non-descending order then once you have used a big prime you won't stop and will use only big primes hence. So your last dimension seems redundant.
•  » » » » » 8 years ago, # ^ |   0 Not true. Maybe we can get somthing smaller than the first unused prime >50 later with combination of first 15 primes.
•  » » » » » » 8 years ago, # ^ |   +8 If it will help later then it will help "right now" as well so we can switch them: remember that the ages are non-descending.
•  » » » » » » » 8 years ago, # ^ |   0 Ok, indeed, thank you.
•  » » » 8 years ago, # ^ |   +3 I just implemented a brute force search with pruning and it was efficient enough. However, I didn't consider some special cases with zeros. :/
•  » » 8 years ago, # ^ | ← Rev. 3 →   +3 What I did was quite simple. Initially I hardcoded the first 64 primes and pre-calculated the bitmasks representing which primes were used in each of the possible numbers' prime factorisations. (overkill, I know)Afterwards I dealt with the simple case of all A[i] <= K (in this case, we make all members of the new array to be K, except for if there are any zeroes, one of them can become a zero). If this does not hold, I initially bounded the solution with using only K * P[i] as my new array, where P is an array of only primes.Now I performed a simple brute-force recursion. It takes parameters of the current sum, index, bitmask and number used). It starts a for loop from max(previousNumber + 1, A[i]/K). If the current number in the loop doesn't violate the bit mask already there, it is placed in the i-th position and we move on. I disable recursing into impossible solutions by enforcing that the elements of the new array must be in increasing order; hence, if I have just added the number X to my array and I have Y numbers left to place, then the sum is bounded below by prevSum + Y*X + Y*(Y+1)/2 (the case where the following numbers are: X+1, X+2, ..., X+Y). If this lower bound is greater than the already found minimum, we can safely stop recursing.This turned out to execute quite quickly on my machine (the time spent on a file with 1000 random test cases with N = 20 was negligible).Here's my code.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Hmm, did you consider cases like 4 1, 1 1 2 3, where you might need to select a 1 twice? The answer will be 0 for this case.
•  » » » » 8 years ago, # ^ |   0 Yeah. I handle the array members that are less than or equal to K separately from the others (as you can see from my code).
•  » » 8 years ago, # ^ |   0 Here is my solution based on backtracking, it corrected after considering the case 12.
 » 8 years ago, # |   0 А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...
•  » » 8 years ago, # ^ |   -20 Не долго!
 » 8 years ago, # |   +5 Scoreboard updated. Lots of B failed. (Mine too). Can anyone give a brief description of algorithm?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 If you can assign q = ceil(c / n) coins to each bucket, then you just do that and the answer is c. If you cannot, assign q to as many buckets as you can (to floor(k / q)), and distribute the remaining part (k % q) among the remaining buckets in any way. Then the strategy is to try to get q coins from each bucket. In the worst case you will try n — k / q buckets that don't have q coins first, so the answer is c + n — k / q.
•  » » » 8 years ago, # ^ |   0 Why is this construction optimal?
 » 8 years ago, # |   +6 Results are up. Everyone with 40p get through although it was close — the first 40p is only 492th.
•  » » 8 years ago, # ^ |   0 Does 40p going further?
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +8 Yes. People with 40 points advance. :DTotal 935 people advance.
•  » » 8 years ago, # ^ |   +16 Hope they have the same scoring system in the next round. Let's agree we will all solve problem A only.
•  » » » 8 years ago, # ^ |   +40 This suggestion does not go well with your avatar :P
 » 8 years ago, # |   +1 What is the answer for "4 5 5" in B and why?
•  » » 8 years ago, # ^ |   0 7 is enough and the distribution is 2 2 1 0 Now I get why those simple solutions work
 » 8 years ago, # | ← Rev. 2 →   0 Could anybody whose 40-pt is OK post the answer for this input: http://pastie.org/8538734 ?UPD. Oops, I forgot that the sources are available.