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

By Shayan

Before stream
03:23:39

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

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

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

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

8 | orz | 146 |

10 | BledDest | 145 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2024 15:36:21 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)Can anyone explain his solution for the third problem "Kas"?

Thank you.

This is harhrayr's solution.

let

dp_{N, diff}— the maximum amount we can give to the first person, if we give himdiffmore than we give to the second person. Note thatdiffcan be negativeFor every number, we can give it to the first person, the second person, or noone.

So,

dp_{N, diff}=max(dp_{N - 1, diff},C_{N}+dp_{N - 1, diff - CN},dp_{N - 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

dp_{N}, 0Can someone explain his/her solution to 4th problem? I wrote a greedy solution but it was worth only 60 points :(

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.

Where's the proof?

I have yet to come up with a formal proof and have only the intuition that the runtime will not cause a TLE.

I still have trouble understanding your solution. Could you try to explain your intuition.

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.

Changing one or two bits doesn't matter, it still branches heavily

https://en.wikipedia.org/wiki/Hand-waving

In fifth one, how it is possible 6 length sequence on test 1?

The sequence is

The sequence don't need to be a subsequence.

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.