Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

Автор 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:

  1. tourist
  2. V--o_o--V
  3. CongLingDanPaiShang3k5
  4. Errichto
  5. 300iq
 
 
 
 
  • Проголосовать: нравится  
  • +352
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится -78 Проголосовать: не нравится

But, is it rated?

»
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 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

On the other Lyft Level 5 challenge blog, it still says the elimination round has 5 problems. Could you change that please?

»
2 месяца назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

Look at the tags!! One of them is "dont ask if rated" LOL XDXDXD!!!!

»
2 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Its time is very unfriendly to Chinese players.

»
2 месяца назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

So about the internship/jobs will you take look at the cf profiles or just consider the contest results ?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +68 Проголосовать: не нравится

    That moment when you are confused whether to risk international master or not

»
2 месяца назад, # |
  Проголосовать: нравится +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 :(

»
2 месяца назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

is it rated?
can it bring inspiration or disappointment to us?

»
2 месяца назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

majk your last contest also was about alice and bob, do you have any fantasy?

»
2 месяца назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

Is It RaTeD ?

»
2 месяца назад, # |
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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    As it has point distribution so i hope it will be like normal codeforcses rounds

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry, the scoring distribution was not published at the time I posted that comment.

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

It is a CuSi Round for Chinese.

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

Set the start 15 min later plz! :'(( Liverpool vs ManCity! :((

»
2 месяца назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

I wish everyone success !

»
2 месяца назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

?DETAR TI SI

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

Hope, It will be an awesome round for both div1 and div2 users. :)

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится -31 Проголосовать: не нравится

:(

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Clashes with Liverpool vs Manchester city :-/

»
2 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I dont wanna die without a tshirt.

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I just wonder that why there's no explanation about interactive problems in the announcement, some kind of information I mean.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Contest over in an hour.never done interaction problem before..It would have been better if there was just one.

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

When tourist is there.. no one has to worry that a question will go unsolved..:)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry for silly ques..Can someone share his approach for Problem C.. I used DFS but got TLE in TC 6..

»
2 месяца назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

How to solve D? Couldn't get AC with Pollard Rho.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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

  • »
    »
    2 месяца назад, # ^ |
    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<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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I solved with Fermat factorization (ofc after eliminating p^2, p^3, p^4 and small prime numbers)

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

what are you supposed to do with D if it is a large semiprime

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

    I used this method:
    http://www.naturalnumbers.org/Qfactor3.html

    UPD : Got TLE :/ Nevermind

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    2 месяца назад, # ^ |
    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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why doesn't Codeforces has __int128? :'( I had problem D if it wasn't because of it

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution for D?

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    There can be four cases in total:

    1. The number has 3 divisors, therefore the number is square of some prime.

    2. The number has 5 divisors, therefore the number is 4th power of some prime.

    3. The number has 4 divisors, the number might be cube of some prime.

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

»
2 месяца назад, # |
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?

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does anyone know why I might have gotten TLE on problem C pretest 6?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I forgot to input n in problem A and spent 1 hour to find the mistake... I need to sleep more often...

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

what a contest.

Mathematics rocks.

»
2 месяца назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

What if the king is being checked in the initial postion in problem A?

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    There might be some p * q number with the same values, or at least share the same prime divisor(s).

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
2 месяца назад, # |
  Проголосовать: нравится 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??

»
2 месяца назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Problem D solution can be found here

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to Solve C??

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится -18 Проголосовать: не нравится

    Just simple DFS

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 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))

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But those values must be pre-calculated to check that right? How to do that?

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        Recursive dp.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +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;
        }
        
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится +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 :((((

»
2 месяца назад, # |
  Проголосовать: нравится 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..

»
2 месяца назад, # |
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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 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 ?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why I am not able to submit the solution after the contest ends

»
2 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

why is D a "technically" iteractive problem? I dont get it

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +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.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +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.

»
2 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Nice contest,Beautiful problems

»
2 месяца назад, # |
  Проголосовать: нравится 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 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!

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The input is 3 15 15 21 (the first integer on the line is the number of prime factors of ai).

»
2 месяца назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Precision... how I love it. Changing from int(c ** (1/3)) to int(c ** (1/3) + 0.0001) changed WA11 on AC

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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 :)

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +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++;
    
»
2 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

If only the constraints of D was 1e18,I've been a candidate :((

»
2 месяца назад, # |
  Проголосовать: нравится 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).

»
2 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Nice Contest , Quick editorial,Fast sys testing. Thanks Codeforces!!!!

»
2 месяца назад, # |
  Проголосовать: нравится -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 :)

»
2 месяца назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Why did you cut off solution from solution? First one is already tedious enough to write...

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How well did we need to do to get an intership?

»
2 месяца назад, # |
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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +86 Проголосовать: не нравится

    The sieving part is correct, the part to blame is actually:

    rep(i,0,n){
        s=s+'0';
    }
    

    Sadly, this is .

    Alternatives are

    1. s += '0'
    2. use std::stringstream
    3. std::string s(n, '0')

    The best one in this particular case is 3.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

  • »
    »
    2 месяца назад, # ^ |
    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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What corner case does test 16 for problem D have? My code passed pretests but gave WA for that one.

  • »
    »
    2 месяца назад, # ^ |
    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.

»
2 месяца назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

How do the organizers know who lives in the Bay Area?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BTW, should you permanently live in Bay Area or you can just be here for the time of contest?

    • »
      »
      »
      2 месяца назад, # ^ |
      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.

»
2 месяца назад, # |
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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 )

»
2 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Fake account in Top 5. Will he receive a fake $500 bill?

»
7 недель назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Any updates on the t-shirt delivery?