Barsic's blog

COCI 2016/2017 Round 4
By Barsic, history, 8 years ago, translation, In English

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.

  • Vote: I like it
  • +53
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

Thank you.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it -7 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Where's the proof?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it -24 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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.

            → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply