Kostroma's blog

By Kostroma, 2 years ago, translation, ,

•
• +66
•

 » 2 years ago, # |   +5 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.com/contest/752/submission/23309803
•  » » 2 years ago, # ^ |   +13 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.
•  » » » 2 years ago, # ^ |   +10 I've got it.Thank you!
•  » » 2 years ago, # ^ |   +8 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
•  » » » 2 years ago, # ^ |   +10 I've got it.Thanks a lot!
•  » » » 23 months ago, # ^ |   +5 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. 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??
•  » » » » 23 months ago, # ^ |   +3 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
•  » » 20 months ago, # ^ |   0 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?
•  » » » 20 months ago, # ^ |   0 Got it. Logical error in else part for palindromes.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 19 months ago, # ^ |   0 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.
 » 2 years ago, # | ← Rev. 2 →   +9 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.
•  » » 2 years ago, # ^ |   0 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
 » 2 years ago, # |   0 Hi I wanted to know will binary search work for problem E.If no can you provide a countercase.
•  » » 2 years ago, # ^ |   0 Actually many people solved it by binary searchsee my code
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Can you help me please to find a mistake in my code for problem E which using a binary search: 23347431
•  » » » » 2 years ago, # ^ |   0 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.
•  » » » » » 2 years ago, # ^ |   +2 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.
•  » » » 2 years ago, # ^ |   0 Dp[a[i]] shows how many children will have more or equal count of mandarins. Am I right ?
•  » » » » 2 years ago, # ^ |   0 Yes, and dp[i] = dp[i / 2] + dp[i / 2 + (i % 2)];
•  » » » 2 years ago, # ^ |   0 Yet again I notice that your codestyle and logic very beautiful and clear for me.
 » 2 years ago, # |   0 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.com/contest/752/submission/23353597or did I get something wrong?
•  » » 2 years ago, # ^ |   +3 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.
 » 23 months ago, # |   0 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 23 months ago, # ^ |   0 thanks i misunderstood the problem . i was minimizing the distance between the pairs
 » 17 months ago, # |   0 problem C , you can just iterate and count how many times you get a non-logical shortest path.