### Barsic's blog

By Barsic, history, 7 years ago, translation,

Hello everyone.

COCI 2016/2017 CONTEST #4 already in a process.

I suggest to discuss the problems here, after the contest.

Sorry for my bad English. And good luck on the contest. :)

The contest is finished. Results here.

• +53

 » 7 years ago, # |   +3 Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)
 » 7 years ago, # |   +11 Can anyone explain his solution for the third problem "Kas"?Thank you.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +26 This is harhrayr's solution.let dpN, diff — the maximum amount we can give to the first person, if we give him diff more than we give to the second person. Note that diff can be negative For every number, we can give it to the first person, the second person, or noone. So, dpN, diff = max(dpN - 1, diff, CN + dpN - 1, diff - CN, dpN - 1, diff + CN). The first option corresponds to giving the banknote to noone, the second option is giving it to the first person, and the third option is giving it to the second person. Then the answer is dpN, 0
 » 7 years ago, # | ← Rev. 2 →   +8 Can someone explain his/her solution to 4th problem? I wrote a greedy solution but it was worth only 60 points :(
•  » » 7 years ago, # ^ | ← Rev. 3 →   -7 For the 4th problem, I first scaled all the numbers up to integers then for each number I find all factors of that number that would be valid.Next, I do a bitmask dp with those factors. It seems as if this wouldn't run in time. However, because so many factors overlap and because only a limited number of factors could be valid, we do not hit that many states. In the case where we have a ton of valid factors, nearly all of those will just hit the same number and that greatly betters our runtime.-EDIT- Informal Proof: A large factor will only change 1 or 2 bits by satisfying only one or two numbers where a smaller factor will satisfy a ton of numbers because it must hit all those in the range [a, b].Furthermore, many factors are divisors of other factors. When we choose a factor, any factor that it divides will thus never be chosen later on because it will be useless. This greatly limits the number of states we hit and will allow us to have a reasonable runtime.Of course, the proof for the actual upperbound is probably quite complicated and in contest I simply submitted on the intuition alone because the solution is very short and only took a few minutes to write.
•  » » » 7 years ago, # ^ |   +18 Where's the proof?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   -24 I have yet to come up with a formal proof and have only the intuition that the runtime will not cause a TLE.
•  » » » » » 7 years ago, # ^ |   +11 I still have trouble understanding your solution. Could you try to explain your intuition.
•  » » » » » » 7 years ago, # ^ |   +6 A large factor will only change 1 or 2 bits by satisfying only one or two numbers where a smaller factor will satisfy a ton of numbers because it must hit all those in the range [a, b].Furthermore, many factors are divisors of other factors. When we choose a factor, any factor that it divides will thus never be chosen later on because it will be useless.This greatly limits the number of states we hit and will allow us to have a reasonable runtime. Of course, the proof for the actual upperbound is probably quite complicated and in contest I simply submitted on the intuition alone because the solution is very short and only took a few minutes to write.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 3 →   +11 Changing one or two bits doesn't matter, it still branches heavily
•  » » » » » » » 7 years ago, # ^ |   0
 » 7 years ago, # |   +3 In fifth one, how it is possible 6 length sequence on test 1?
•  » » 7 years ago, # ^ |   +3 The sequence is khzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 1st string) vkhzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 11th string) ckhzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 7th string) ockhzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 5th string) aockhzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 2nd string) haockhzyubiqkujupffyozvoxutbndrjxlkuixaipycgngpdtnnbblytqomnaazryn (the 15th string). The sequence don't need to be a subsequence.
 » 7 years ago, # |   +3 Anyone got error on problem E that is only abs( myresult — offical result) == 1 for last 4 test cases? I got 250,they have 251,I have 168 they have 169,also is there anyone who solved D to explain it?Judging by how fast they are on coci we can't expect solutions in under a month.