Video Solutions to WF 2016 Problems posted.

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:46:21
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

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.

MedoN11
9 years ago
28

Comments (27)

Show archived | Write comment?

MedoN11

9 years ago, # |

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

→ Reply

MedoN11

9 years ago, # |

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

→ Reply

rng_58

9 years ago, # |

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

→ Reply

Rafbill

9 years ago, # ^ |

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

CodeForceps

9 years ago, # ^ |

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

→ Reply

rng_58

9 years ago, # ^ |

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

→ Reply

Swistakk

9 years ago, # ^ |

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

→ Reply

rng_58

9 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.

→ Reply

Swistakk

9 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...

→ Reply

rng_58

9 years ago, # ^ |

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

→ Reply

rng_58

9 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?

→ Reply

cgy4ever

9 years ago, # ^ |

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

Swistakk

9 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?

→ Reply

Um_nik

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."

→ Reply

chemthan

8 years ago, # ^ |

Can you share your code? Thank in advanced!

→ Reply

Fcdkbear

9 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?

→ Reply

Lewin

9 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.

→ Reply

Fcdkbear

9 years ago, # ^ |

+10

Cool, thanks!

→ Reply

mnaeraxr

9 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.

→ Reply

Mohammad_Ali

9 years ago, # ^ |

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

jcg

8 years ago, # ^ |

Using Pollard-Rho for factorize the whole number is slow, you can go to $\text{[math]}$ 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

solution_hacker

9 years ago, # |

← Rev. 3 →

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

animeshf

9 years ago, # ^ |

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 <bits/stdc++.h>
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();
}

→ Reply