MedoN11's blog

Video Solutions to WF 2016 Problems posted.
By MedoN11, history, 9 years ago, In English

Incase any of you would like to view the solutions, they are posted here on YT with discussions. I found this when navigating my YT so thought I'd share on CF.

Problem L : https://www.youtube.com/watch?v=LJtR7bFC8MU

Problem G : https://www.youtube.com/watch?v=-Y9xM_7gVGI

Problem F : https://www.youtube.com/watch?v=MlSByiE2yVU

Problem C : https://www.youtube.com/watch?v=FvppunbosmU

Problem K : https://www.youtube.com/watch?v=sLdzLvAqXxg

Problem D : https://www.youtube.com/watch?v=VP835B2Xb68

Problem B : https://www.youtube.com/watch?v=4xyhMgQnS88

Problem I : https://www.youtube.com/watch?v=3rLiyfvxVr4

Problem A : https://www.youtube.com/watch?v=ls5kkQlQJMA

Problem J : https://www.youtube.com/watch?v=LjXDfSby-G0

Problem E : https://www.youtube.com/watch?v=6-ijK43EkE0

Rest will be updated as they go up.

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

Comments Comments (27)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).

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

Does anyone know I's solution? The video actually describes A's solution.

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

    It is probably not the intended solution, but it is solvable by solving (at most) 200 linear programming problems with 100 variables and 400 constraints.

    It is accepted in 2.2s by icpc.kattis.com with the Simplex algorithm from the stanford acm icpc book. (pivot needs to be rewritten to ignore zero rows/cols)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      During the contest, it was said that the problem I needs simplex method, so I guess you got the problem right.

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

        Hmm, then the four hardest tasks (H, I, J, M) were only about implementation...

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

          Yes, that is sad that no problem posed a real algorithmic challenge :| (like G or K year ago).

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

            Well, I've just noticed that the reduction to LP is not straightforward, which is quite rare for LP tasks.

            Anyway I liked B, F, and K.

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

              OMG!! In this problem the routes we consider are minimum-DISTANCE route, not minimum delivery time which are different, because traversal time is dependent on type of ground! All the difficulty in this problem is in careful reading statement. That was the last problem I hoped that demands deeper insight, now I dislike this problemset even more...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                ok I misread it in the same way... now the reduction is completely obvious.

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

                  In case the WF judges are reading this... Why did you choose this task for WF? Did you really think that it was a good idea to decide the WF champion by whether the team has pre-written LP codes?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Last year they used a task that requires FFT for the first time.

                  We can image after few years the champion will be decided by the ability of compress all kind of complicated algorithm into 25 pages. :P

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

                  FFT -> LP

                  FFT definitely belongs to the "classical must-have" in library and I believe that fact it has not appeared before on finals is rather result of a fact that prob. that among 100-200 random problems (let's exclude prehistorical finals) at least one requires FFT is not very close to one, not because of it being highly advanced or anything. Moreover problems using FFT often prove to be really interesting and demanding very nice ideas and this LP problem was literally screaming "HEY I AM OBVIOUS LP!!" (after getting the statement right, which was a very hard exercise). This is literally without a doubt worst problem ever on finals (excluding broken ones) taking into account how it could have affected results (fortunately it didn't). How is that possible that any judge thought it is a good idea to put that into problemset?

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

                  In my opinion, the worst with this problem is that judges cannot prove that their solution is polynomial. Really? It's like 'We will make a strange problem which can be obivously reduced to an LP with huge limitations, but it's hard to come up with good tests because you cannot just make an LP you want. So we have made some random testdata, our solution works fast."

                  → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share your code? Thank in advanced!

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

Am I correct, that in problem E it is suggested to iterate 100000 times over the age, that we are going to get, and inside this — iterate 100000 times over the base, that we use (in case, when binary search fails to find the exact answer)? How to prove, that such solutions fits in TL? How to prove its correctness?

I also didn't get Petr's solution. Can anyone explain it in more details?

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

    I think this is the intended solution.

    Iterate over the resulting age that we are going to get, and binary search to get as close as we can to y (if it matches, then we can stop). If we iterate until we have 3-4 digits in our resulting ages, this covers all bases that are at least about 10^5-10^6.

    Now, iterate from base 10 to base 10^6 (in a separate loop). Check if the base b representation of y satisfies the condition, and take the max base that satisfies this.

    The intuition is, iterating through bases is too slow, and iterating through age is too slow, but you can do some sort of meet in the middle.

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

      Cool, thanks!

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

      Different approach for this problem: Check small set of potential correct bases(and pick the largest) Only need to check divisors of y, y — 1, y — 2, y — 3, ... y — 8, y — 9. Those are the only numbers we need to check because they guaranteed that the last digit of y in base b is <= 10.

      Also used fast factorization method to handle 10^18 integers.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This was actually the solution I came up with earlier. I did not think of testing small bases and small representations.

        I used Pollard-Rho for factorization, combined with Miller-Rabin for primality checking, with a sieve to speed up small cases.

        I'm getting TLE on test case 15 on Kattis. How did you implement your fast factorization?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Using Pollard-Rho for factorize the whole number is slow, you can go to dividing, the resulting number is a prime or the product of two primes, use miller-rabing to test for primality, and in the other case use pollar-rho to get one of the prime factors of the number...

          → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

How is sorting drives whose space decreases in decreasing order of their initial space correct for L?

Suppose drives were:

From: 7 2 1 3 5

To: 1 2 2 6 4

If we sort them as per the solution we get:

From: 1 2 3 7 5

To: 2 2 6 1 4

Using it we get swap storage required(answer) as 5. But if we take

From: 1 2 3 5 7

To: 2 2 6 4 1

in this order, we get answer as 4. Can somebody explain?

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

    AFAIK, for the bad items (where b[i] < a[i]), you sort them in descending order of b[i] before processing them greedily. The video tutorial suggests sorting in descending order of a[i], but that clearly doesn't work :/

    Can someone prove why sorting by b[i] in descending order works?

    This code somehow passes :-

    Solution
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try to think about reverse of decreasing process (starts from end).

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

      I think it's because the last b is of no use.

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

Problem I link is wrong, its https://www.youtube.com/watch?v=3rLiyfvxVr4

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

Solution sketches by judges http://www.csc.kth.se/~austrin/icpc/finals2016solutions.pdf

→ Reply