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.
Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).
Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).
Does anyone know I's solution? The video actually describes A's solution.
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)
During the contest, it was said that the problem I needs simplex method, so I guess you got the problem right.
Hmm, then the four hardest tasks (H, I, J, M) were only about implementation...
Yes, that is sad that no problem posed a real algorithmic challenge :| (like G or K year ago).
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.
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...
ok I misread it in the same way... now the reduction is completely obvious.
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?
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
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?
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."
Can you share your code? Thank in advanced!
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?
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.
Cool, thanks!
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.
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?
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...
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?
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 :-
Try to think about reverse of decreasing process (starts from end).
I think it's because the last b is of no use.
Problem I link is wrong, its https://www.youtube.com/watch?v=3rLiyfvxVr4
Solution sketches by judges http://www.csc.kth.se/~austrin/icpc/finals2016solutions.pdf