Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:20:34
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:20:34
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 06:14:26 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Is hash possible to solve the D Problem? I don't know whether a conflict happened in the hash process or there is a bug in my code. Here is my code: http://codeforces.net/contest/752/submission/23309803
I haven't read the rest of your code but I think if your hash mods are (1007, 5009) then it doesn't look very safe (as in collision is likely to occur). However it might also be the rest of your code that is causing the WA. Just pointing out that the hash modulos aren't big enough.
I've got it.Thank you!
Good day to you...
I totally agree with zscoder — as you have possibility to hash, you have almost "unlimited" possibilities of hash size (obv best modulo is somewhere near boundary of int so you can do all operations easily) [unless you need direct array access — but here you can use map]
What I wanted to add is, that you can make it "double — hash" so the collision probability will be MINIMAL:
Here, see the "rh" function. [but it might be slightly an overkill]
Good Luck & Have Nice Day
I've got it.Thanks a lot!
Hi. I used double hash but got wrong answer. After just changing method from using hash to just putting string into map, I got accepted.
http://codeforces.net/contest/752/submission/24697497 http://codeforces.net/contest/752/submission/24699032
Above is with hash, and below is just using map. Without it, everything is same. When I used hash, I used (100001, 100003), which are big enough I thought. To solve this problem by using hash, what should I do more?? Or, did I use hash method improperly??
Good day to you,
as you might see, after adding MODULUS, it got accepted (if I copied right solution)
This — imho — means, that test 47 was anti-natural modulo (i.e. ~2^64)
Good Luck & Have Nice Day
26998325 27005624 Ive used the same logic as most of the accepted codes. I even tried changing from hash to map. Still im getting WA on test case 8. Can you identify where the logic is going wrong?
Got it. Logical error in else part for palindromes.
I am also getting WA on TC 8. Can u tell me what is the error? I am getting the same output as your's.
Yes, the error was that if at any point you get something like abc -10 and cba 5, its not necessary that you couple these both. You discard the negative one and consider cba 5 as a standalone string that is available. Similarly if it were aba instead of abc, then you actually discard the negative one and consider 1 more already palindromic string in the pool that should be taken into consideration.
There's also a soltuion for E using binary search. My mistake was writing recurrent DP instead of iterative to count in how many parts of size greater or equal to mid we can divide a number. The latter passes TL, the former does not.
I had the same solution and also got TLE at system tests. However it still works if you sort the array first to break the loop asap
Hi I wanted to know why can't binary search work for problem E.Binary search for the maximum joy.
Hi I wanted to know will binary search work for problem E.If no can you provide a countercase.
Actually many people solved it by binary search
see my code
Can you help me please to find a mistake in my code for problem E which using a binary search: 23347431
consider you have only one tangerine, with size 15. how many parts you can get with size 5?
in your code = 15/5 = 3 parts but by the procedure, 15 -> 7, 8 7 -> cannot divide 8 -> cannt divide therefore, the answer should be 2, instead of 3.
You are not right because I add to answer a cnt[a[i]/m] where m is a minimum amount of parts of tangerine which every pupil should get. In cnt[i] I store a max power of 2 which is not great than i. In your example a[i] = 15, m = 5, a[i] / m = 3, cnt[3] = 2. But I found a mistake in my solution. I considered that we can't get more than cnt[a[i]/m] things with at least m parts of tangerine. But there is a counter test: a[i] = 7, m = 2. So cnt[a[i]/m] = 2. But let's divide 7: 7 -> [4, 3] -> [2, 2, 2, 1]. As we can see, there are 3 things with at least 2 parts of tangerine and so my solution is incorrect.
Dp[a[i]]shows how many children will have more or equal count of mandarins. Am I right ?Yes, and dp[i] = dp[i / 2] + dp[i / 2 + (i % 2)];
Yet again I notice that your codestyle and logic very beautiful and clear for me.
It seems the solution about E is not O(n+A) solution.. I implemented the algorithm written in this article and got counterexample(which makes TLE).
I think the main reason is that we can divide a tangerine multiple times(divide the divided part again), so division can happen more than n times.
here is my code : http://codeforces.net/contest/752/submission/23353597
or did I get something wrong?
You should divide all the tangerines of the same size at once. It can be easily seen that there is no profit in dividing only some part of them.
for the problem F it is up to us to divide the teams into pairs. so why can't there exist a pair which is solely in the sub-tree of this chosen vertex v. such pair may give smaller distance than the pairs chosen above. is there any proof available for this statement.
In this problem we want to divide teams into pairs in such a way that the number of cities in which the teams live is minimized. In the editorial we show that one city is always enough.
problem C , you can just iterate and count how many times you get a non-logical shortest path.
Did problem D: Santa Claus and Palindrome using DP(slightly easier approach compared to editorial), have a look at my code.