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

Автор Barsic, история, 8 лет назад, По-русски

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Barsic (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Can anyone explain his solution for the third problem "Kas"?

Thank you.

  • »
    »
    8 лет назад, # ^ |
    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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      Where's the proof?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +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.