Endagorion's blog

By Endagorion, history, 2 years ago, translation, ,

Cheers everyone.

Today, on June 13 at 10:00 MSK the third and final qualification round of Yandex.Algorithm 2016 tournament will take place. I am the author of all tasks in this round. I wish to thank Ivan Gassa Kazmenko, Oleg snarknews Khristenko, and espically Aleksey Chmel_Tolstiy Tolstikov and Maxim Zlobober Akhmedov for their immense contribution to problems preparation. I also thank Yandex employees who were involved in testing this round.

Best of luck!

UPD: the round is complete! Congratulations to Um_nik, who was the only one to solve all problems!

You can find the elimination standings here. Congratulations to 25 best participants!

Editorial here

•
• +76
•

 » 2 years ago, # |   0 Auto comment: topic has been translated by Endagorion (original revision, translated revision, compare)
 » 2 years ago, # |   0 How to solve Problem B — BMO and Garland?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 Iterate for left turned on lamp. add 2^(min(k - 1, len of suffix)) to answerUPD: and also add 1 for case when there's no lamps at all
•  » » » 2 years ago, # ^ |   +1 I've got WA 11 using this approach, and all the contest spent testing :(
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 2^(k-1)%m != ((2^k)%m)/2. It my WA 11. Very stupid bug :(
•  » » 2 years ago, # ^ |   0 Formula: (n - k + 2) * 2k - 1. But actually I have no idea how to prove it, just found it by bruteforcing.
•  » » » 2 years ago, # ^ |   +8 fix '1' in the left suffix : full segments : (n-k+1) * 2^(k-1) not full segments: sum from 0 to (k — 2) 2 ^i and just zeroes — it's 1 more, not full segments and just zeroes gave 2^(k-1).
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +3 Wow, that's pretty clear. Thank you so much.UPD: Thank you all the guys below for explanation.
•  » » » 2 years ago, # ^ |   0 Well, I first thought it would be like (n - k) * 2k, that is, (n - k) positions to fix a window of size k and 2k possibilities for each window. However, this has over-counting.But, we can fix ones at the end of each window padded with zeroes on left and right of the window, and then place anything in between. Dunno how to put that in a formula though.
•  » » » 2 years ago, # ^ |   0 fix any segment and set leftmost and rightmost lamp. If set has length l, then count of possible variants is 2l - 2. For fixed l count of segments is n - l + 1. And then answer is sum for l = 2 to k of 2l - 2 * (n - l + 1). And need to add n + 1 (for l = 0 and 1). Simplifiing formula gives us your formula.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Say you fix the first K long segment at the beginning. Now you have 2^k possible ways. Every time you move your segment one along, you should not count all the combinations where the lamp that just left your segment was turned off, as they are also valid in the new segment, but already counted. That is 2^(k-1), so for the new segment that is one to the left we add (2^k)-(2^(k-1)) = 2^(k-1) to our answer. We do this n-k times, as this is how many times we can move the segment. So answer is, as you said, 2^k + (n-k)*2^(k-1) = (n-k+2)*2^(k-1)EDIT: I guess I was the last of a million people to all post within 1 minute ;)
•  » » » 2 years ago, # ^ |   -6 First add all possible for the first k lamps. res = 2^kNow say the right most turned on lamp is i > k. Iterate over all n >= i > k.You will notice for each such i, answer is 2^(k-1), since you have fixed i-th lamp.Hence formula is: 2^k + (n-k)2^(k-1)
•  » » 2 years ago, # ^ |   0 Iterate l over range [0..k]. Consider all possilble segments of length l with leftmost and rightmost bits set to 1. For every position, there are 2max{0, l - 2} possible segments, making (n - l + 1)·2max{0, l - 2} possibilities for each possible l (except when l is 0 when there is only one possibility: a string consisting of all zeros).
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Most intuitive for me was the following:Imagine all numbers from 1 to n. For n equals 5 it is going to be:00000000010001000011....11111If k =3, then there are exactly 2^k numbers with three digits, we count them in. There are 2^k numbers with exactly four digits, but we are intersted only in those which end '0', like:010100110001110So there are 2^k / 2 = 2^(k-1)Then we look at numbers with exactly five digits, there are 2^(k+1) of them. But we are interested only in those which end by 00, there are 2^(k+1) / 2^2 = 2^(k-1) of them.And so on. So the final calculation will be 2^k + 2^(k-1) + 2 ^ (k-1) + 2 ^ (k-1) + ... + 2 ^ (k-1) repeated (n-k) times.
 » 2 years ago, # | ← Rev. 2 →   +41 any idea how to fix WA3 in C?
•  » » 2 years ago, # ^ |   +10 I think the scenario in that case is that after losing to some vampire i, we will lose to a vampire j < i few times and build up the strength to beat i later.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +29 Thanks Spoiler
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 +1, what can be wrong? my code#include using namespace std; #define FOR(i,a,b) for(int i = (a); i <= (b); ++i) #define FORD(i,a,b) for(int i = (a); i >= (b); --i) #define RI(i,n) FOR(i,1,(n)) #define REP(i,n) FOR(i,0,(n)-1) #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) #define mp make_pair #define pb push_back #define st first #define nd second #define sz(w) (int) w.size() typedef vector vi; typedef long long ll; typedef long double ld; typedef pair pii; const int inf = 1e9 + 5; const int nax = 1e6 + 5; int main() { int n; ll start; scanf("%d%lld", &n, &start); ll so_far = 0; ll ans = n; RI(i, n) { ll str, gain, loss; scanf("%lld%lld%lld", &str, &gain, &loss); if(start + so_far > str) { so_far += gain; } else { if(so_far - loss <= 0) { puts("-1"); return 0; } ll diff = so_far - loss; // start + so_far + x*diff > str ll tmp = str - so_far - start; assert(diff > 0); assert(tmp >= 0); // x * diff > tmp ll x = tmp / diff + 1; ans += x * i; start += x * diff; //so_far += x * diff; so_far += gain; } } printf("%lldn", ans); return 0; } EDIT: Yeah, I assumed that the defeated prefix never decreases.
•  » » » 2 years ago, # ^ |   0 On a different note, how do you post collapsing blocks in comments? I tried the two options available (block, inline) both does not collapse the code.
•  » » » » 2 years ago, # ^ |   +24 Try spoiler. I used below (but without dots).<.spoiler summary="description">.~~~~~code is block, block is in spoiler~~~~~<./spoiler>
•  » » 2 years ago, # ^ |   +15 I thought the number of fights in one "run" never decreases when I had WA 3.
•  » » 2 years ago, # ^ |   +44 Very tricky. It is possible that you return to the original position with fewer points and still the answer is not -1.
•  » » 2 years ago, # ^ |   +11 3 4 0 5 0 8 0 0 9 0 7 answer: 8
•  » » 2 years ago, # ^ |   +8 Spent 13 wrong submissions on this (which effectively disqualified me), but finally got it right.The point is that sometimes it pays of decrease the starting value of M, while my original algorithm terminated when such a situation occurs.
•  » » » 2 years ago, # ^ |   +10 And on the 13th day the forces of code went to their forum and said unto each other: "Why can't we solve a baby problem? What's wrong with us?" And they answered: "Behold, thine logic has given way to thine vanity."
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 My solutions failed on such case: 3 2 0 7 0 8 0 0 10 0 100Answer should be 8.UPD: Its wrong sample, correct one in comments below
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 How to fix this case? I had a greedy-ish algorithm to go to max point where we can and then increase value to such that it greater than what is needed there. For finding max point where we can reach I used suffix minimum BIT. I am not sure how to fix my idea to accommodate for this case as it would keep on running in prefixes. Can it not be fixed using my current idea? Code#include #include #include #include #include using namespace std; typedef long long int lli; const lli inf = 170705091707050917; lli n, m; vector A, B, C, BIT; void upd(lli idx, lli v) { while(idx <= n) { BIT[idx] = min(v, BIT[idx]); idx += (idx&-idx); } } lli qry(lli idx) { lli res = inf; while(idx > 0) { res = min(res, BIT[idx]); idx -= (idx&-idx); } return res; } int main(void) { scanf("%lld%lld", &n, &m); A.clear(); A.resize(n+1); B.clear(); B.resize(n+1); C.clear(); C.resize(n+1); BIT.clear(); BIT.resize(n+1, inf); for(lli i = 1;i <= n;i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]); for(lli i = 1;i <= n;i++) B[i] += B[i-1]; vector> pref(n+1); for(lli i = 1;i <= n;i++) { if(!i) pref[i].first = A[i]+B[i-1]; pref[i].second = i; } sort(pref.begin(), pref.end()); for(lli i = n;i > 0;i--) { upd(n-i+1, pref[i].second); //cout << pref[i].second << "n"; } //cout << "startn"; lli cur, add, ptval, res = 0, iter = 0; while(true) { cur = qry(n-lli(lower_bound(pref.begin(), pref.end(), pair(m, 0))-pref.begin())+2); //cout << cur << "n"; if(cur == n && m > A[n]-B[n-1]) { printf("%lldn", res); return 0; } add = B[cur-1]-C[cur]; if(iter > 1e7) { printf("-1n"); return 0; } else { ptval = A[cur]; res += cur*(ceil(double(ptval+1-m)/add)); m += (ceil(double(ptval+1-m)/add)); m = max(m, 0ll); } //cout << m << " " << cur << " " << add << " " << ptval << "n"; iter++; } } 
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 are you sure it's 8? I got AC now but my solution still thinks it's -1
•  » » » » 2 years ago, # ^ |   0 Correct answer is -1. When we lose the third battle the strength become 0, and we can not win first battle.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Oh, sorry, my bad.Correct one should be: 3 2 0 7 0 8 0 0 10 0 8
 » 2 years ago, # | ← Rev. 2 →   0 When will the final standings (three rounds combined) be released?UPD: It's out!
 » 2 years ago, # |   +88 Yandex rounds have really good quality. C, D and E were nice problems, thanks Endagorion.Though, D was much easier than C and E.
 » 2 years ago, # |   +3 How to solve Problem D?
•  » » 2 years ago, # ^ |   +10 Check what is in . Then, with binary search find on the right the first cell of different type. Then, the same on the left.In binary search you should check X + 1, X + 2, X + 4, X + 8, ... till you find the first different type. Then standard algorithm.
•  » » » 2 years ago, # ^ |   +18 X = 0 is just fine too
•  » » 2 years ago, # ^ |   +21 Let's find minimal k such that cells 0 and 2k have different colors (iterate k). I state that cells 0 and 2k are in consecutive segments (ease to prove, try yourself). Using binary search find the leftmost cell in 2k-s segment. Now repeat that starting from that cell instead of starting from 0. We have found starts of two consecutive segments. It is queries (and complexity).
 » 2 years ago, # |   +1 from Provision: final round — July 28-29, 2016from Schedule: 28-29 Jun 2016Could someone clarify? Also, will there be someone from Yandex willing to help with visas?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +13 It's JuLy, thanks for the note. We'll get in touch this week
 » 2 years ago, # |   +17 A common reason for blind submissions: Submit near the end of the contest and no time to debug if the code is wrong.
 » 2 years ago, # |   +13 How to solve C?
 » 2 years ago, # |   +8 Does anybody know where I should write my address on yandex? I am in first 500 competitors, but I can't find field for address and they can't send me a t-shirt :D. Thanks
•  » » 2 years ago, # ^ |   +22 We'll get in touch everyone in TOP-512 this week.
•  » » » 2 years ago, # ^ |   -108 This is not a TOP-512. This is the list of 512 people who can afford themselves to take part at least in two rounds.
•  » » » » 2 years ago, # ^ |   +38 Better than year ago :)
•  » » » » 2 years ago, # ^ |   +77 Even red still need to participate in competitions to win.
 » 2 years ago, # |   +34 Some important information for non-Russian-speaking people:"The Organiser shall not reimburse the Finalists’ costs of transfer from the place of residence of the Finalist to the final round" "Finalists can participate in the final round at the final round venue or online."Are you planning to attend the onsite finals?
 » 2 years ago, # |   +6 What about #513 who has the same penalty with #512 :) ? Can he receive T-shirt ?
•  » » 2 years ago, # ^ |   +20 he is cheater[2k])
•  » » 2 years ago, # ^ |   +28 Sure. We'll send the T-shirt.
 » 2 years ago, # |   -17 Love the blind submissions. Encourage people to code more carefully and not to depend on the testing system to check their codes. And the reward for the brave people is very worthy — Much fewer penalties time!
 » 2 years ago, # |   -52 Let's settle this once and for all. Amazing World of Gumball >> Adventure Time :))).
 » 2 years ago, # |   +7 Have everyone received the notification mail about the T-shirt? My friends received it yesterday, but I haven't yet. So I am really worried that they lost my email...
•  » » 2 years ago, # ^ |   +11 I haven't received it yet either.
•  » » 2 years ago, # ^ |   +1 Please fill feedback form. You can find the link in the bottom left corner of the contest page.
•  » » » 2 years ago, # ^ |   +3 Please give me advice on T-shirt.I will be in Russia in August, so thinking to put Russian address in the form instead of Cayman Islands. Do you think it is realistic to receive T-Shirt to address in St. Petersburg by August 26th? Otherwise I'll stick with Cayman Islands address.
•  » » » » 2 years ago, # ^ |   +10 August 26'th is perfectly realistic date for St.Petersburg. Fill in Yandex office address and my name, if you want a personal office tour with your shirt =)
•  » » 2 years ago, # ^ |   +3 I've surprisingly found mine in a spam folder.
•  » » » 2 years ago, # ^ |   +3 Mine too, but I provided @mail.ru address, so I can understand why :)
•  » » » » 2 years ago, # ^ |   +3 The same thing to me)
•  » » » » 2 years ago, # ^ |   0 Where did you provide your email? I can't remember if I did that.
•  » » » » » 2 years ago, # ^ |   0 If you are not sure, please fill the feedback form on the contest page.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Well, I'm #513 who has the same penalty with #512. As you said before, I am able to receive a T-shirt.However, I haven't receive any mails from Yandex, even when I filled the feedback form on the contest page. So could you consider my problem? Thank you so much!
•  » » » » » » » 2 years ago, # ^ |   0 Of course you get the tshirt too! Sent you an email about now.
•  » » 23 months ago, # ^ |   0 T-shirts are coming. A courier delivered it to me today. What is strange, I had to fill in my passport number in his papers, he said it's required when the package is insured.
•  » » » 23 months ago, # ^ |   0 Can you please elaborate on that on support@contest.yandex.ru
•  » » » » 23 months ago, # ^ |   +25 Can someone explain design of t-shirt ? xD
•  » » » » » 23 months ago, # ^ |   0 It's look like a curled armadillo.
•  » » » » » 23 months ago, # ^ |   0 Can you share a photo :p?
•  » » » » » » 23 months ago, # ^ |   0
•  » » » » 23 months ago, # ^ |   0 Is it OK if a contestant from my city (Izhevsk) has received a t-shirt 4 days ago, but I still haven't?