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 tshirt. 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
Many thanks to:
 arsijo for the round coordination,
 fhlasek, KAN, Nasic_number_one, Sonechko, StasyaCat, zubec for testing the round
 MikeMirzayanov for Codeforces and Polygon platforms
 Lyft for sponsoring the round
 Alice and Bob for playing a crucial role in some of the statements
I'll be on the community Discord server shortly after the contest to discuss the problems.
UPDATE 1: The scoring distribution will be 500100015002250275032504000.
UPDATE 2: The contest is over and there is an editorial.
UPDATE 3: Congratulations to the winners:
But, is it rated?
Maybe you can have a look at the first paragraph :D
Maybe you can have a look at the tags :D The last tag is obviously the reason he posted that.
Well some people didn't get that :p
IT WON'T BE RATED!!! > https://www.youtube.com/watch?v=gehfVhX7Spk
Seems I didn't realize that it's a joke(
Clashes with the last 15 minutes of Liverpool vs Man city, sorry but watching and supporting Mo Salah is my choice :D
I've spoken with him and he said he would not play football because match clashes with contest ;D
Maybe Mo wants to participate and win a Tshirt :)
Guess we could call his solutions... Mo's algorithm.
While the world cup takes place in Russia. I do not see any comment on football. Not relevant, but I like Messi :)
On the other Lyft Level 5 challenge blog, it still says the elimination round has 5 problems. Could you change that please?
Thank you, fixed
Look at the tags!! One of them is "dont ask if rated" LOL XDXDXD!!!!
Its time is very unfriendly to Chinese players.
Blame Trump
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.
I see you don't have a job/class you have to be at 9 am on Monday ;)
Oh I have class, I just don't go if I don't wake up in time :P
Found the American.
So about the internship/jobs will you take look at the cf profiles or just consider the contest results ?
That moment when you are confused whether to risk international master or not
How come no one ever thanks Vasya for his help in problem statements :(
Cuz he is green.
is it rated?can it bring inspiration or disappointment to us?
majk your last contest also was about alice and bob, do you have any fantasy?
Is It RaTeD ?
swap(Is,It)
It Is RaTeD?
It seems that I can register whenever I want until the contest ends.
So, is it a ACMlike contest?
If yes, is it of extendedACM style (with hacking phase after the contest ends) ?
Sorry for my unnatural English.
As it has point distribution so i hope it will be like normal codeforcses rounds
It is a CuSi Round for Chinese.
Set the start 15 min later plz! :'(( Liverpool vs ManCity! :((
Never mind, WreckingBall has solved the problem! ;D
The game whitout Mo is perfect to! :(
My last hope crashed );
I wish everyone success !
Or maybe
I wish myself contribution !
?Maybe !
I see some bitter irony in all this downvotes.
?DETAR TI SI
Hope, It will be an awesome round for both div1 and div2 users. :)
Before getting job, i need some positive rating !
:(
And also downvoting whoever say it...
Clashes with Liverpool vs Manchester city :/
I dont wanna die without a tshirt.
I just wonder that why there's no explanation about interactive problems in the announcement, some kind of information I mean.
Contest over in an hour.never done interaction problem before..It would have been better if there was just one.
When tourist is there.. no one has to worry that a question will go unsolved..:)
Sorry for silly ques..Can someone share his approach for Problem C.. I used DFS but got TLE in TC 6..
Maybe you didn't go from the biggest number to the smallest...
I did go from biggest number to smallest. Code
I just can't see you code on Codeforces before the end of the systesting...
Made redundant recursive calls and hence it caused TLE. Now I get AC! >_<
Oh, thanks! I've just find out that the order doesn't matter.
How to solve D? Couldn't get AC with Pollard Rho.
Given a number x there's 4 probabilities for it
either x = p^2 or x = p^3 or x = p^4 or x = pq where both p and q are primes
so if x has a root,then you can know the primes easily without any struggle,the only problem is pq
you 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
same approach, but verdicts WA, any corner case?
I have solved it using Shanks's square forms factorization which will give you any divisor of n, x such that 1<x<n. As there can be only 4 types of number of form p^2 or p^3 or p^4 or p*q where p and q are primes, you can have a prime using Shanks and get the other prime by considering some cases. Thus after prime factorizing each prime, count the occurences and get the answer easily. Hope it helps. Happy Coding.
I solved with Fermat factorization (ofc after eliminating p^2, p^3, p^4 and small prime numbers)
what are you supposed to do with D if it is a large semiprime
I used this method:
http://www.naturalnumbers.org/Qfactor3.html
UPD : Got TLE :/ Nevermind
Compute gcd between every pair of elements to get some candidates for primes. If those don't divide some notprimepower number in the input, assume that it consists of two unique primes.
thought about this, didn't notice n was 500. phew!
I didn't got your solution. Can you please explain a little bit...
See my code or read the editorial.
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.
Assuming you have only semiprimes remaining, you could try factoring some of them by calculating GCD of every pair.
EDIT: Too late :P
Why doesn't Codeforces has __int128? :'( I had problem D if it wasn't because of it
Solution for D?
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
thanks +1
You wrote "4. The number has 4 divisors..."
I think you meant 2
EDIT: Nvm i read incorrectly
Hmm, the number has between 3 and 5 divisors. I think you might be mistaken somewhere.
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?
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.
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?
You need to flush the output using
fflush(stdout) or cout.flush() in C++;
. Anyways you'll fail pretest 1.You have to flush the output
Yeah, i used endl for that.
Does anyone know why I might have gotten TLE on problem C pretest 6?
I forgot to input n in problem A and spent 1 hour to find the mistake... I need to sleep more often...
what a contest.
Mathematics rocks.
What if the king is being checked in the initial postion in problem A?
The statement guarantees it's not.
Where?
It is guaranteed that Bob's king is currently not in check and the target location is not in check either.
nvm im stupid
What is wrong with this thinking in D?
First if a number has 5 divisors it has to be p^4 form
if a number has 3 divisors it has to be p^2 form
if a number has 4 divisors, we have 2 cases: p^3 or p*q
all 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 number
Edit Nevermind. for the p*q case I considered that all the numbers cannot share a common prime which is obviously a stupid mistake.
There might be some p * q number with the same values, or at least share the same prime divisor(s).
Thanks. realized it later.
If I understand this correctly, it fails if your input is p^{2}, pq, because you ignore the p^{2} when you process pq even though they share a factor in p.
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.
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??
Problem D solution can be found here
Why copied problems.who knows it will just copy paste
I see very little in common between these two problems, it is pretty much like saying "Here is wiki article about problem D".
ohh i just wrote it because link leads to a code

How to Solve C??
Just simple DFS
I am stupid
Yes, you should stop doing CP.
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 inum, i2*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.
For every ith, 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))
But those values must be precalculated to check that right? How to do that?
Recursive dp.
yeah! thanks.
My bad! I kept thinking there must be some simpler solution than memoized dp during the contest , considering it a C problem :((((
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..
My solution for D:
Notice that to have 3, 4, or 5 divisors, the number must be in the form p^{2}, p^{3}, p^{4} 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.
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 ?
Why I am not able to submit the solution after the contest ends
Because the system test is still running
why is D a "technically" iteractive problem? I dont get it
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 (noninteractive) task.
I am sorry for the confusion that it apparently caused.
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.
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.
Thank you! Together with comment by KAN, it cleared my doubts.
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.
Nice contest,Beautiful problems
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 42
My 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!
The input is 3 15 15 21 (the first integer on the line is the number of prime factors of a_{i}).
Precision... how I love it. Changing from int(c ** (1/3)) to int(c ** (1/3) + 0.0001) changed WA11 on AC
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 :)
And then comes a time you have to do something like this XD
If only the constraints of D was 1e18,I've been a candidate :((
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).
Nice Contest , Quick editorial,Fast sys testing. Thanks Codeforces!!!!
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#comment456882 :)
Why did you cut off solution from solution? First one is already tedious enough to write...
In reality, the uses around 17000 queries.
How well did we need to do to get an intership?
My C got TLE, it ran in 1450ms with time limit being 1s, can anybody explain why is it so? It is sievelike implementation so the time complexity should be O(n*log(n)).
Hi, majk, could you help?
Submission : 43960105
The sieving part is correct, the part to blame is actually:
Sadly, this is .
Alternatives are
s += '0'
std::stringstream
std::string s(n, '0')
The best one in this particular case is 3.
Thanks for your reply, it now runs in 77ms.
When i though about C problem as a DP problem on DAG, i defined the state such that
dp[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 :)
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.
Ok i got it, Thanks brother :)
What corner case does test 16 for problem D have? My code passed pretests but gave WA for that one.
Test 16 is a random test, where each number is a product of two primes slightly over 10^{9}. Pretest 10 is the same random test, but with a different seed. So there should not be anything special about it.
How do the organizers know who lives in the Bay Area?
BTW, should you permanently live in Bay Area or you can just be here for the time of contest?
"We invite top30 participants who don't need sponsored travel to our location. If you get good score in round1, 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.
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
I solved it with DP , states are <CurrentNodeValue , Turn > , 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 )
This algorithm is great! It has helped me alot in this problem!