Разбор Codeforces Round 389 (Div.2)

Блог пользователя Kostroma

Автор Kostroma, 9 лет назад, По-русски

Tutorial is loading...

Разбор задач Технокубок 2017 - Отборочный Раунд 3

Разбор задач Codeforces Round 389 (Div. 2, рейтинговый, по мотивам Технокубок 2017 - Отборочный Раунд 3)

edirorial, технокубок, разбор

Kostroma
9 лет назад
29

Комментарии (28)

Показать архивные | Написать комментарий?

Marco_L_T

9 лет назад, скрыть # |

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://mirror.codeforces.com/contest/752/submission/23309803

→ Ответить

zscoder

9 лет назад, скрыть # ^ |

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

→ Ответить

Marco_L_T

9 лет назад, скрыть # ^ |

+10

I've got it.Thank you!

→ Ответить

-Morass-

9 лет назад, скрыть # ^ |

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

→ Ответить

Marco_L_T

9 лет назад, скрыть # ^ |

+10

I've got it.Thanks a lot!

→ Ответить

petil777

9 лет назад, скрыть # ^ |

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://mirror.codeforces.com/contest/752/submission/24697497 http://mirror.codeforces.com/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??

→ Ответить

-Morass-

9 лет назад, скрыть # ^ |

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

→ Ответить

punetharomil

9 лет назад, скрыть # ^ |

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?

→ Ответить

punetharomil

9 лет назад, скрыть # ^ |

Got it. Logical error in else part for palindromes.

→ Ответить

murtaza2102

9 лет назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить

punetharomil

9 лет назад, скрыть # ^ |

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.

→ Ответить

equocredite

9 лет назад, скрыть # |

← Rev. 2 →

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.

→ Ответить

Envyte

9 лет назад, скрыть # ^ |

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

→ Ответить

marcose18

9 лет назад, скрыть # |

Hi I wanted to know why can't binary search work for problem E.Binary search for the maximum joy.

→ Ответить

marcose18

9 лет назад, скрыть # |

Hi I wanted to know will binary search work for problem E.If no can you provide a countercase.

→ Ответить

Tiny

9 лет назад, скрыть # ^ |

Actually many people solved it by binary search
see my code

→ Ответить

IBetIWillBePurpleIn2019

9 лет назад, скрыть # ^ |

← Rev. 2 →

Can you help me please to find a mistake in my code for problem E which using a binary search: 23347431

→ Ответить

nyan101

9 лет назад, скрыть # ^ |

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.

→ Ответить

IBetIWillBePurpleIn2019

9 лет назад, скрыть # ^ |

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.

→ Ответить

nuradil

9 лет назад, скрыть # ^ |

Dp[a[i]] shows how many children will have more or equal count of mandarins. Am I right ?

→ Ответить

ironsoul

9 лет назад, скрыть # ^ |

Yes, and dp[i] = dp[i / 2] + dp[i / 2 + (i % 2)];

→ Ответить

pyloolex

9 лет назад, скрыть # ^ |

Yet again I notice that your codestyle and logic very beautiful and clear for me.

→ Ответить

nyan101

9 лет назад, скрыть # |

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://mirror.codeforces.com/contest/752/submission/23353597

or did I get something wrong?

→ Ответить

KAN

9 лет назад, скрыть # ^ |

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.

→ Ответить

tonyironstark

9 лет назад, скрыть # |

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.

→ Ответить

Kostroma

9 лет назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить