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

# | User | Rating |
---|---|---|

1 | tourist | 3821 |

2 | Benq | 3744 |

3 | ksun48 | 3559 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3531 |

6 | Um_nik | 3488 |

7 | maroonrk | 3423 |

8 | Petr | 3379 |

9 | sunset | 3337 |

10 | ecnerwala | 3335 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 173 |

8 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/29/2021 22:48:15 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Where is the announcement? Like it was in qualification

UPDIt was boring to debug "Labelmaker", until I got outputPKUPERCUPTEAMThe link is posted. Good luck!

Why I can't get access to tasks round 1?

This link don't work.

It should work, so sorry for the silly question: have you solved at least one problem in qualification round about 2 weeks ago?

No, I don't know, sorry.

Can anyone explain me third case in "Coins Game". Of course if it isn't illegal.

I believe any discussion is illegal. Solution on specific test case can help you to solve problem.

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.

Yeah you are right. I thought a little bit , then i found optimal arrangement.

Что должно выдавать в D(40) на тесте N = 20, K = 1, A[i] = 50 (для всех i = {0, ..., 19})? А еще спешу огорчить тех, у кого в B(20), на тесте 3 7 7, выдает 9:(

У меня 647.

О, а как тогда B решать?

У меня 643. Мне это уже не нравится)

Вот теперь это уже не нравится мне :D

А, фух, не ту задачу посмотрел, 643, всё ок.

Case #1: 643

51 53 58 59 61 65 67 71 73 77 79 83 89 97 101 103 107 109 113 127

643.

When will results be announced ?

Can someone explain their solution to the 40pt question?

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.

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?

I tried all coefficients up to 500 and, yes, used a map<vector,int>. eduardische's comment looks like a better way to keep track of state, assuming it works.

Code here (guaranteed to not be correct).

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 :)

Should not this case be caught by the last example?

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.

It's 18, because you need just 18 ones, one zero and one 2.

Yeap, but gcd(0,2) = 2, and 2 > 1.

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).

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

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].

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.

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.

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.

Not true. Maybe we can get somthing smaller than the first unused prime >50 later with combination of first 15 primes.

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.

Ok, indeed, thank you.

I just implemented a brute force search with pruning and it was efficient enough. However, I didn't consider some special cases with zeros. :/

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.

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.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).

Here is my solution based on backtracking, it corrected after considering the case 12.

А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...

Не долго!

Scoreboard updated. Lots of B failed. (Mine too). Can anyone give a brief description of algorithm?

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.

Why is this construction optimal?

Results are up. Everyone with 40p get through although it was close — the first 40p is only 492th.

Does 40p going further?

Yes. People with 40 points advance. :D

Total 935 people advance.

Hope they have the same scoring system in the next round.

Let's agree we will all solve problem A only.

This suggestion does not go well with your avatar :P

What is the answer for "4 5 5" in B and why?

7 is enough and the distribution is 2 2 1 0 Now I get why those simple solutions work

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.