Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### MedoN11's blog

By MedoN11, history, 8 years ago,

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.

• +88

| Write comment?
 » 8 years ago, # |   0 Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).
 » 8 years ago, # |   0 Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).
 » 8 years ago, # |   +6 Does anyone know I's solution? The video actually describes A's solution.
•  » » 8 years ago, # ^ |   +8 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)
•  » » » 8 years ago, # ^ |   0 During the contest, it was said that the problem I needs simplex method, so I guess you got the problem right.
•  » » » » 8 years ago, # ^ |   +1 Hmm, then the four hardest tasks (H, I, J, M) were only about implementation...
•  » » » » » 8 years ago, # ^ |   +5 Yes, that is sad that no problem posed a real algorithmic challenge :| (like G or K year ago).
•  » » » » » » 8 years ago, # ^ |   +11 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.
•  » » » » » » » 8 years ago, # ^ |   +28 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...
•  » » » » » » » » 8 years ago, # ^ |   0 ok I misread it in the same way... now the reduction is completely obvious.
•  » » » » » » » » » 8 years ago, # ^ |   +27 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?
•  » » » » » » » » » 8 years ago, # ^ |   0 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
•  » » » » » » » » » 8 years ago, # ^ |   +20 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?
•  » » » » » » » » » 8 years ago, # ^ |   +55 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."
•  » » » 8 years ago, # ^ |   0 Can you share your code? Thank in advanced!
 » 8 years ago, # | ← Rev. 2 →   +11 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?
•  » » 8 years ago, # ^ |   +11 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.
•  » » » 8 years ago, # ^ |   +10 Cool, thanks!
•  » » » 8 years ago, # ^ |   +16 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.
•  » » » » 8 years ago, # ^ |   0 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?
•  » » » » » 8 years ago, # ^ |   0 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...
 » 8 years ago, # | ← Rev. 3 →   +5 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 5To: 1 2 2 6 4If we sort them as per the solution we get:From: 1 2 3 7 5To: 2 2 6 1 4Using it we get swap storage required(answer) as 5. But if we takeFrom: 1 2 3 5 7To: 2 2 6 4 1in this order, we get answer as 4. Can somebody explain?
•  » » 8 years ago, # ^ |   +5 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#include using namespace std; const int N = 1e6 + 6; int n, cnt_good, cnt_bad; pair < long long, long long > good[N]; pair < long long, long long > bad[N]; long long ans, space; inline void add_good(int i){ long long delta = (good[i].second - good[i].first); if(ans + space < good[i].first){ ans += (good[i].first - (ans + space)); } space += delta; } inline void add_bad(int i){ long long delta = (bad[i].second - bad[i].first); if(ans + space < bad[i].first){ ans += (bad[i].first - (ans + space)); } space += delta; } inline void solve(){ for(int i = 1; i <= cnt_good; i++) add_good(i); for(int i = 1; i <= cnt_bad; i++) add_bad(i); printf("%lldn", ans); } inline bool cmp_good(pair < int, int > a, pair < int, int > b){ if(a.first == b.first) return (a.second > b.second); return (a.first < b.first); } inline bool cmp_bad(pair < int, int > a, pair < int, int > b){ if(a.second == b.second) return (a.first < b.first); return (a.second > b.second); } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ long long x, y; scanf("%lld %lld", &x, &y); if(x <= y){ ++cnt_good; good[cnt_good].first = x; good[cnt_good].second = y; } else{ ++cnt_bad; bad[cnt_bad].first = x; bad[cnt_bad].second = y; } } sort(good + 1, good + 1 + cnt_good, cmp_good); sort(bad + 1, bad + 1 + cnt_bad, cmp_bad); solve(); } 
•  » » » 8 years ago, # ^ |   0 Try to think about reverse of decreasing process (starts from end).
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 I think it's because the last b is of no use.
 » 8 years ago, # |   +1 Problem I link is wrong, its https://www.youtube.com/watch?v=3rLiyfvxVr4
 » 8 years ago, # |   +17 Solution sketches by judges http://www.csc.kth.se/~austrin/icpc/finals2016solutions.pdf