Автор majk, 2 недели назад, ,

Hungry for yet another contest? On Sunday, October 7, 2018 at 17:05 UTC the Lyft Level 5 Challenge will start with the Round 1! This is a combined round having 7 problems and lasting 2 hours, and it will be rated.

The top 100 participants of this round will win a Lyft Level 5 Challenge t-shirt. The top 30 contestants located in the San Francisco Bay area will be invited to the Final Round.

In the Final Round the top three onsite contestants will fight for the cash prizes:

• First place: $2000 • Second place:$1000
• Third place: \$500

Interested in an internship or a job at Lyft?

Many thanks to:

I'll be on the community Discord server shortly after the contest to discuss the problems.

UPDATE 1: The scoring distribution will be 500-1000-1500-2250-2750-3250-4000.

UPDATE 2: The contest is over and there is an editorial.

UPDATE 3: Congratulations to the winners:

•
• +352
•

 » 2 недели назад, # |   -78 But, is it rated?
•  » » 13 дней назад, # ^ |   -22 Maybe you can have a look at the first paragraph :D
•  » » » 13 дней назад, # ^ |   +69 Maybe you can have a look at the tags :D The last tag is obviously the reason he posted that.
•  » » » » 13 дней назад, # ^ | ← Rev. 2 →   +33 Well some people didn't get that :p
•  » » » » » 11 дней назад, # ^ |   -12 IT WON'T BE RATED!!! --------> https://www.youtube.com/watch?v=gehfVhX7Spk
•  » » » » 13 дней назад, # ^ |   +30 Seems I didn't realize that it's a joke(
 » 2 недели назад, # |   0 Clashes with the last 15 minutes of Liverpool vs Man city, sorry but watching and supporting Mo Salah is my choice :D
•  » » 2 недели назад, # ^ | ← Rev. 2 →   +95 I've spoken with him and he said he would not play football because match clashes with contest ;D
•  » » » 2 недели назад, # ^ |   +38 Maybe Mo wants to participate and win a T-shirt :)
•  » » » » 12 дней назад, # ^ |   +48 Guess we could call his solutions... Mo's algorithm.
•  » » 2 недели назад, # ^ |   -45 While the world cup takes place in Russia. I do not see any comment on football. Not relevant, but I like Messi :)
 » 13 дней назад, # |   +1 On the other Lyft Level 5 challenge blog, it still says the elimination round has 5 problems. Could you change that please?
•  » » 13 дней назад, # ^ |   +12 Thank you, fixed
 » 13 дней назад, # |   -32 Look at the tags!! One of them is "dont ask if rated" LOL XDXDXD!!!!
 » 13 дней назад, # |   -9 Its time is very unfriendly to Chinese players.
•  » » 13 дней назад, # ^ |   +117 Blame Trump
•  » » 12 дней назад, # ^ |   +3 Isn't 1 AM a nice time since it's late enough that it definitely won't conflict with anything but it's also not too late to stay up for? That's how I feel about 1 AM contests, anyway.
•  » » » 12 дней назад, # ^ |   +6 I see you don't have a job/class you have to be at 9 am on Monday ;)
•  » » » » 12 дней назад, # ^ |   +3 Oh I have class, I just don't go if I don't wake up in time :P
•  » » » 12 дней назад, # ^ |   +13 Found the American.
 » 13 дней назад, # |   +58 So about the internship/jobs will you take look at the cf profiles or just consider the contest results ?
•  » » 12 дней назад, # ^ |   +68 That moment when you are confused whether to risk international master or not
 » 13 дней назад, # |   +73 [Many thanks to] Alice and Bob for playing a crucial role in some of the statements How come no one ever thanks Vasya for his help in problem statements :(
•  » » 12 дней назад, # ^ |   +3 Cuz he is green.
 » 13 дней назад, # |   +101 is it rated? can it bring inspiration or disappointment to us?
 » 13 дней назад, # |   +32 majk your last contest also was about alice and bob, do you have any fantasy?
 » 12 дней назад, # |   -40 Is It RaTeD ?
•  » » 12 дней назад, # ^ |   +49 swap(Is,It)
•  » » » 12 дней назад, # ^ |   +22 It Is RaTeD?
 » 12 дней назад, # | ← Rev. 2 →   0 It seems that I can register whenever I want until the contest ends.So, is it a ACM-like contest?If yes, is it of extended-ACM style (with hacking phase after the contest ends) ?Sorry for my unnatural English.
•  » » 12 дней назад, # ^ |   +2 As it has point distribution so i hope it will be like normal codeforcses rounds
 » 12 дней назад, # |   +18 It is a CuSi Round for Chinese.
 » 12 дней назад, # | ← Rev. 2 →   -20 Set the start 15 min later plz! :'(( Liverpool vs ManCity! :((
•  » » 12 дней назад, # ^ |   -7 Never mind, WreckingBall has solved the problem! ;D
•  » » » 12 дней назад, # ^ |   -7 The game whitout Mo is perfect to! :(
•  » » » » 12 дней назад, # ^ |   0 My last hope crashed );
 » 12 дней назад, # |   -25 I wish everyone success !
•  » » 12 дней назад, # ^ |   -27 Or maybe I wish myself contribution !?
•  » » » 12 дней назад, # ^ |   -30 Maybe !
•  » » » 12 дней назад, # ^ |   0 I see some bitter irony in all this downvotes.
 » 12 дней назад, # |   -56 ?DETAR TI SI
 » 12 дней назад, # | ← Rev. 2 →   -11 Hope, It will be an awesome round for both div1 and div2 users. :)
•  » » 12 дней назад, # ^ |   +8 Before getting job, i need some positive rating !
 » 12 дней назад, # | ← Rev. 3 →   -31 :(
•  » » 12 дней назад, # ^ |   0 And also downvoting whoever say it...
 » 12 дней назад, # |   0 Clashes with Liverpool vs Manchester city :-/
 » 12 дней назад, # |   +10 I dont wanna die without a tshirt.
 » 12 дней назад, # |   +1 I just wonder that why there's no explanation about interactive problems in the announcement, some kind of information I mean.
 » 12 дней назад, # |   0 Contest over in an hour.never done interaction problem before..It would have been better if there was just one.
 » 12 дней назад, # |   +3 When tourist is there.. no one has to worry that a question will go unsolved..:)
 » 12 дней назад, # |   0 Sorry for silly ques..Can someone share his approach for Problem C.. I used DFS but got TLE in TC 6..
•  » » 12 дней назад, # ^ |   +2 Maybe you didn't go from the biggest number to the smallest...
•  » » » 12 дней назад, # ^ |   0 I did go from biggest number to smallest. Code
•  » » » » 12 дней назад, # ^ |   0 I just can't see you code on Codeforces before the end of the systesting...
•  » » » » » 12 дней назад, # ^ |   +1 Made redundant recursive calls and hence it caused TLE. Now I get AC! >_<
•  » » » » » » 12 дней назад, # ^ |   0 Oh, thanks! I've just find out that the order doesn't matter.
 » 12 дней назад, # |   +29 How to solve D? Couldn't get AC with Pollard Rho.
•  » » 12 дней назад, # ^ |   +15 Given a number x there's 4 probabilities for iteither x = p^2 or x = p^3 or x = p^4 or x = pq where both p and q are primesso if x has a root,then you can know the primes easily without any struggle,the only problem is pqyou can just try taking the gcd of x with other numbers in the array,if all gcd == 1 or x then p and q are primes number that appears for the first time
•  » » » 12 дней назад, # ^ |   0 same approach, but verdicts WA, any corner case?
•  » » 12 дней назад, # ^ | ← Rev. 2 →   +3 I have solved it using Shanks's square forms factorization which will give you any divisor of n, x such that 1
•  » » 12 дней назад, # ^ |   +8 I solved with Fermat factorization (ofc after eliminating p^2, p^3, p^4 and small prime numbers)
 » 12 дней назад, # |   +5 what are you supposed to do with D if it is a large semiprime
•  » » 12 дней назад, # ^ | ← Rev. 3 →   -8 I used this method:http://www.naturalnumbers.org/Qfactor3.htmlUPD : Got TLE :/ Nevermind
•  » » 12 дней назад, # ^ |   +65 Compute gcd between every pair of elements to get some candidates for primes. If those don't divide some not-prime-power number in the input, assume that it consists of two unique primes.
•  » » » 12 дней назад, # ^ |   0 thought about this, didn't notice n was 500. phew!
•  » » » 12 дней назад, # ^ |   0 I didn't got your solution. Can you please explain a little bit...
•  » » » » 12 дней назад, # ^ |   +2 See my code or read the editorial.
•  » » 12 дней назад, # ^ |   +4 You can find the two prime factors x = p * q by gcd with every other number. If that is not possible (the prime factors don't appear in the other numbers, or it only appears in numbers that are equal to the first one) then the prime factors p and q appear in the product the same number of times as x appears in the array.
•  » » 12 дней назад, # ^ | ← Rev. 2 →   0 Assuming you have only semiprimes remaining, you could try factoring some of them by calculating GCD of every pair.EDIT: Too late :P
 » 12 дней назад, # |   0 Why doesn't Codeforces has __int128? :'( I had problem D if it wasn't because of it
 » 12 дней назад, # |   0 Solution for D?
•  » » 12 дней назад, # ^ | ← Rev. 3 →   +6 There can be four cases in total: The number has 3 divisors, therefore the number is square of some prime. The number has 5 divisors, therefore the number is 4th power of some prime. The number has 4 divisors, the number might be cube of some prime. The number has 4 divisors, the number might be product of two distinct primes. 1,2,3 can be done easily. 4 can be done by this link: http://www.naturalnumbers.org/Qfactor3.html
•  » » » 12 дней назад, # ^ |   0 thanks +1
•  » » » 12 дней назад, # ^ | ← Rev. 3 →   0 You wrote "4. The number has 4 divisors..."I think you meant 2EDIT: Nvm i read incorrectly
•  » » » » 12 дней назад, # ^ |   +5 Hmm, the number has between 3 and 5 divisors. I think you might be mistaken somewhere.
 » 12 дней назад, # | ← Rev. 3 →   -12 Can anyone explain me how to take input in D? I mean what the fuck is going on there? I kept getting idleness time exceeded, Can anyone tell me why that problem was interactive?
•  » » 12 дней назад, # ^ |   -8 A number that has 3, 4 or 5 divisor should be a p1*p2, p1^2, p1^3 or p1^4, where p1 and p2 are primes. To know what are the primes that multiply two different numbers, take the gcd of each two different numbers in input that is not a power.
•  » » » 12 дней назад, # ^ | ← Rev. 13 →   0 Bro, i am not asking the solution, i am asking about the input format.here's my solution: http://codeforces.com/contest/1033/submission/43971194 Tell me why is this giving idleness time exceeded?
•  » » » » 12 дней назад, # ^ |   0 You need to flush the output using fflush(stdout) or cout.flush() in C++;. Anyways you'll fail pretest 1.
•  » » 12 дней назад, # ^ |   0 You have to flush the output
•  » » » 12 дней назад, # ^ |   0 Yeah, i used endl for that.
 » 12 дней назад, # |   +5 Does anyone know why I might have gotten TLE on problem C pretest 6?
 » 12 дней назад, # |   0 I forgot to input n in problem A and spent 1 hour to find the mistake... I need to sleep more often...
 » 12 дней назад, # |   +5 what a contest.Mathematics rocks.
 » 12 дней назад, # |   -14 What if the king is being checked in the initial postion in problem A?
•  » » 12 дней назад, # ^ |   0 The statement guarantees it's not.
•  » » » 12 дней назад, # ^ |   -8 Where?
•  » » 12 дней назад, # ^ |   0 It is guaranteed that Bob's king is currently not in check and the target location is not in check either.
•  » » » 12 дней назад, # ^ |   +6 nvm im stupid
 » 12 дней назад, # | ← Rev. 3 →   0 What is wrong with this thinking in D?First if a number has 5 divisors it has to be p^4 formif a number has 3 divisors it has to be p^2 formif a number has 4 divisors, we have 2 cases: p^3 or p*qall other but p*q can be checked easily. for p*q part we can first process all other numbers and have a map of divisors and its count. Then for all numbers not processed (p*q form) we can check only the divisors which have occurred in previous numbers. Else we dont care about the divisors and just say the count of some divisor would be 1. then the number of divisors would be multiplication of (number of occurrence + 1) for each prime numberEdit Nevermind. for the p*q case I considered that all the numbers cannot share a common prime which is obviously a stupid mistake.
•  » » 12 дней назад, # ^ |   +3 There might be some p * q number with the same values, or at least share the same prime divisor(s).
•  » » » 12 дней назад, # ^ |   0 Thanks. realized it later.
•  » » 12 дней назад, # ^ |   0 If I understand this correctly, it fails if your input is p2, pq, because you ignore the p2 when you process pq even though they share a factor in p.
•  » » 12 дней назад, # ^ |   +3 A number of p*q form may have a common factor with another number of p*q form, which changes calculations a bit! Thus, we need to look into this too, by pairwise checking of any common factors. Even after this some number goes unprocessed, ( we were unable to factorise this p*q form number), it means it consists of 2 entirely different primes.
 » 12 дней назад, # |   0 In E my approach was to start with n bipartite graphs, binary search for last graph to find a graph such that there are edges between these 2 and then merge them if there exists a valid way. But i cant think how to find an odd cycle if we get to know that there is no valid merging of the 2 bipartite graphs??
 » 12 дней назад, # |   -14 Problem D solution can be found here
•  » » 12 дней назад, # ^ |   -9 Why copied problems.who knows it will just copy paste
•  » » » 12 дней назад, # ^ |   +20 I see very little in common between these two problems, it is pretty much like saying "Here is wiki article about problem D".
•  » » » » 12 дней назад, # ^ |   +2 ohh i just wrote it because link leads to a code
•  » » » » 12 дней назад, # ^ | ← Rev. 2 →   -19 -
 » 12 дней назад, # |   0 How to Solve C??
•  » » 12 дней назад, # ^ |   -18 Just simple DFS
•  » » » 12 дней назад, # ^ |   +3 I am stupid
•  » » » » 12 дней назад, # ^ |   -54 Yes, you should stop doing CP.
•  » » 12 дней назад, # ^ |   0 You start from the greatest element and mark that Bob wins that because Alice cannot go to a greater element for sure. Then go to the next smaller number let it be num, let its position be i. You should look at i-num, i-2*num .. i+num, i+2*num. if there is any case where Bob wins in any of those numbers that means Alice can win because Alice will go there and it will be Bobs turn and we know that if Alice starts there Bob could win so if Bob starts Alice can win. If there isnt any such position you mark it as Bob wins. You keep doing this.
•  » » 12 дней назад, # ^ |   0 For every i-th, check i - a[i], i - a[i] * 2, ..., i - a[i] * k > 0, AND i + a[i], i + 2*a[i], .... , i + a[i] * l <= n. Total: n/a[i] iteration. sum of all iterations: sum(n/a[i],i=1..n) = sum(n/i, i = 1..n) ~ O(n*log(n))
•  » » » 12 дней назад, # ^ |   0 But those values must be pre-calculated to check that right? How to do that?
•  » » » » 12 дней назад, # ^ |   +2 Recursive dp.
•  » » » » 12 дней назад, # ^ |   +1 const int bob = 2; const int alice = 1; int dp[1<<18]; ... memset(dp, 0, sizeof(dp)); for( i = 1; i <= n; ++i) dp_rec(i); .... void dp_rec(i){ if (dp[i])return; // already calculated. dp[i] = alice; // we assume alice will win. for(int p = i - a[i]; p > 0; p-= a[i]) if (a[p] > a[i]){ dp_rec(p); if(dp[p]==bob) return; } for(int p = i + a[i]; p <= n; p += a[i]) if(a[p] > a[i]) { dp_rec(p); if(dp[p] == bob) return ; // if on p - BOB win, for i-th position alice win. } dp[i] = bob; } 
•  » » » » » 12 дней назад, # ^ |   +5 yeah! thanks.My bad! I kept thinking there must be some simpler solution than memoized dp during the contest , considering it a C problem :((((
 » 12 дней назад, # |   0 In D, I have maintained a hash map of primes to their frequency. First check if it is in the form of p^4, p^3 or p^2. If so update the prime in the hash map and make it 1 in the array. then iterate through the array and find how many numbers are equal to current number, let it be counter. make those elements 1. Take gcd with next elements and when gcd is > 1. let gcd be g, so the current number will have two primes g and number/g. iterate the rest of the array and find how many times g and number/g occurs as divisors, divide the numbers by g or number/g according to which one divides them. Update hash map with cnt+their frequency. For all primes in the hash map iterate the array and see if they divide anything and make those elements in the array 1 and update the map. Finally iterate the array multiply the ans by 2 if there is any elements > 1.If this is the approach I will be sad because I used int instead of long long at some place and got a wrong answer..
 » 12 дней назад, # | ← Rev. 2 →   +1 My solution for D:Notice that to have 3, 4, or 5 divisors, the number must be in the form p2, p3, p4 or pq, for primes p, q. It is easy to check if it's one of the first three cases, in which case we can store a map of primes to the number of times they exist in the total product.If we encounter a number of the form pq, then we gcd with all the previous elements to find a possible prime factor. If we find a prime factor, we then know p and q and can process it as we processed the other numbers. If not, then we count how many previous instances of pq happened (call this k), and multiply our current answer by .EDIT: Oh but I failed systests anyway RIP.
•  » » 12 дней назад, # ^ |   0 I instead multiplied it by (k+1)^2 as there is no other occurrence of those p and q. Why are you multiplying with ((k+2)/(K+1))^2 ?
 » 12 дней назад, # |   0 Why I am not able to submit the solution after the contest ends
•  » » 12 дней назад, # ^ |   0 Because the system test is still running
 » 12 дней назад, # |   +33 why is D a "technically" iteractive problem? I dont get it
•  » » 12 дней назад, # ^ |   +75 Because of hacks. When you submit a hack, we need to verify whether it is a valid test case, i.e. whether the number has between 3 and 5 divisors. You can't do that without factorising the input, and that factorisation cannot be done fast enough.For that reason, you submit the factorisation as a hack. The interactor then reads this factorisation, and writes the product on its standard output. From then on, it's just a normal (non-interactive) task.I am sorry for the confusion that it apparently caused.
•  » » » 12 дней назад, # ^ |   +3 "You can't do that without factorising the input, and that factorisation cannot be done fast enough." So what exactly will go wrong if you'll try to factorize it? Will it be something like "checker TL exceeded", since you have to proceed that input within (let's say) 1 second, or is it "we can do that, but it will load CF servers too much" (sounds questionable due to small number of hacks). I don't think it is "you'll have to wait for the verdict for too long" either, since it isn't instant anyway. Could you please add a few details about what the issue is, for those who don't know how CF works? I'm just curious about what is the technical limitation behind it.
•  » » » » 12 дней назад, # ^ |   +6 You would get a "Judgement Failed" verdict with a comment that validator exceeded the time limit. Which is what I was getting in Polygon when preparing the problem.Someone with a deeper knowledge of the platform might be able to tell you more details.
•  » » » » » 12 дней назад, # ^ |   +10 Thank you! Together with comment by KAN, it cleared my doubts.
•  » » » » 12 дней назад, # ^ |   +5 AFAIK the TL on any judge executable (validator, checker, etc) is 10 or 20 seconds. I suppose it can be raised, but is it needed? Also, we'll have to have the same format for all system tests, so we need to factorize them too, that might take long time.
 » 12 дней назад, # |   +22 Nice contest,Beautiful problems
 » 12 дней назад, # |   0 Hi majk, arsijo,There is something wrong with the checker for task D. For example this submission is getting WA on test 9:I assume that the test case is: 3 30 30 42My program locally returns 24 and the checker says it returns 45. I do not see any reason why there should be any difference. Could you take a look into this?Thanks!
•  » » 12 дней назад, # ^ |   0 The input is 3 15 15 21 (the first integer on the line is the number of prime factors of ai).
 » 12 дней назад, # |   -18 Precision... how I love it. Changing from int(c ** (1/3)) to int(c ** (1/3) + 0.0001) changed WA11 on AC
•  » » 12 дней назад, # ^ |   +77 After running into such stuff once or twice you'll probably start doing things like "let's check +-10 in each direction, just to be sure", even if you don't really need that :)
•  » » 12 дней назад, # ^ |   +10 And then comes a time you have to do something like this XD long long int sq = sqrt(n); while(sq*sq > n) sq--; while(sq*sq <= n) sq++; 
 » 12 дней назад, # |   +14 If only the constraints of D was 1e18,I've been a candidate :((
 » 12 дней назад, # |   0 Until this moment I realized how weak the pretests of D was. Still, my bad after all, so no huge complaints. Great problemset overall, to be honest (even I myself took away my very chance to be in top100).
 » 12 дней назад, # |   +14 Nice Contest , Quick editorial,Fast sys testing. Thanks Codeforces!!!!
 » 12 дней назад, # |   -15 Wow I barely reached yellow! Purples are half div2 — half div1, so now I'm completely div 1. Also it seems now I'm a nerd: http://codeforces.com/blog/entry/61683#comment-456882 :)
 » 12 дней назад, # |   +15 Why did you cut off solution from solution? First one is already tedious enough to write...
•  » » 12 дней назад, # ^ |   +7 In reality, the uses around 17000 queries.
 » 12 дней назад, # |   0 How well did we need to do to get an intership?
 » 12 дней назад, # | ← Rev. 2 →   +7 My C got TLE, it ran in 1450ms with time limit being 1s, can anybody explain why is it so? It is sieve-like implementation so the time complexity should be O(n*log(n)).Hi, majk, could you help?Submission : 43960105
•  » » 12 дней назад, # ^ |   +86 The sieving part is correct, the part to blame is actually: rep(i,0,n){ s=s+'0'; } Sadly, this is .Alternatives are s += '0' use std::stringstream std::string s(n, '0') The best one in this particular case is 3.
•  » » » 12 дней назад, # ^ |   +27 Thanks for your reply, it now runs in 77ms.
 » 12 дней назад, # |   0 When i though about C problem as a DP problem on DAG, i defined the state such thatdp[i][j]=1 if the player j can win when the game starts at position i, else it equals 0.I found some submissions only use dp[i] and nothing else changed in the rest of the solution, so what is the idea behind the possibility of removing the second dimension in my defined state?Thanks in advance :)
•  » » 12 дней назад, # ^ | ← Rev. 4 →   +10 If one of the player wins for a given position, then the other one loses. Because there is always one player who wins and the other one loses. I don't see why would you need a second dimension.Unless your state refers to which player starts playing, but I still don't understand why it would be needed since it is specified in the statement that Alice starts playing.
•  » » » 12 дней назад, # ^ |   +10 Ok i got it, Thanks brother :)
 » 12 дней назад, # |   0 What corner case does test 16 for problem D have? My code passed pretests but gave WA for that one.
•  » » 12 дней назад, # ^ | ← Rev. 2 →   +26 Test 16 is a random test, where each number is a product of two primes slightly over 109. Pretest 10 is the same random test, but with a different seed. So there should not be anything special about it.
 » 12 дней назад, # |   +63 How do the organizers know who lives in the Bay Area?
•  » » 12 дней назад, # ^ |   0 BTW, should you permanently live in Bay Area or you can just be here for the time of contest?
•  » » » 11 дней назад, # ^ | ← Rev. 2 →   +18 "We invite top-30 participants who don't need sponsored travel to our location. If you get good score in round-1, want to be invited to onsite, and can manage travel costs, don't hesitate to send a personal message and we'll definitely consider you when processing scoreboard."This was what they said here. So, you don't even really need to live there. You just need to be there at the time of the contest.
 » 12 дней назад, # | ← Rev. 2 →   0 In problem C , can any one tell me what's wrong in my approach ? why does it give wrong answer on Test 23 ?http://codeforces.com/contest/1033/submission/43970251
•  » » 12 дней назад, # ^ |   0 I solved it with DP , states are , Current State is to pick the optimal choice depends on transitions (For example :- currentTurn for Alice , Alice must search for any odd moves to Win and Bob must search for even moves to Win )
 » 9 дней назад, # |   0 This algorithm is great! It has helped me alot in this problem!