The Lyft Level 5 Challenge 2018 Elimination Round (Div. 1 + Div. 2)
By majk, 6 years ago, In English

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. DearMargaret
  4. Errichto
  5. 300iq
  • Vote: I like it
  • +352
  • Vote: I do not like it

Comments Comments (147)
| Write comment?
»
6 years ago, # |
  Vote: I like it -78 Vote: I do not like it

But, is it rated?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Maybe you can have a look at the first paragraph :D

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +69 Vote: I do not like it

      Maybe you can have a look at the tags :D The last tag is obviously the reason he posted that.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Clashes with the last 15 minutes of Liverpool vs Man city, sorry but watching and supporting Mo Salah is my choice :D

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +95 Vote: I do not like it

    I've spoken with him and he said he would not play football because match clashes with contest ;D

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    While the world cup takes place in Russia. I do not see any comment on football. Not relevant, but I like Messi :)

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -32 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Its time is very unfriendly to Chinese players.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +117 Vote: I do not like it

    Blame Trump

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I see you don't have a job/class you have to be at 9 am on Monday ;)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Oh I have class, I just don't go if I don't wake up in time :P

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Found the American.

      → Reply
»
6 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +73 Vote: I do not like it

[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 :(

→ Reply
»
6 years ago, # |
  Vote: I like it +101 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Is It RaTeD ?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It is a CuSi Round for Chinese.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -25 Vote: I do not like it

I wish everyone success !

→ Reply
»
6 years ago, # |
  Vote: I like it -56 Vote: I do not like it

?DETAR TI SI

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -31 Vote: I do not like it

:(

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Clashes with Liverpool vs Manchester city :-/

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I dont wanna die without a tshirt.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

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

    UPD : Got TLE :/ Nevermind

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thought about this, didn't notice n was 500. phew!

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't got your solution. Can you please explain a little bit...

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Assuming you have only semiprimes remaining, you could try factoring some of them by calculating GCD of every pair.

    EDIT: Too late :P

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for D?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks +1

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      You wrote "4. The number has 4 divisors..."

      I think you meant 2

      EDIT: Nvm i read incorrectly

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Hmm, the number has between 3 and 5 divisors. I think you might be mistaken somewhere.

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to flush the output

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

what a contest.

Mathematics rocks.

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Problem D solution can be found here

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve C??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Just simple DFS

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Recursive dp.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it 
        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;
}
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          yeah! thanks.
          My bad! I kept thinking there must be some simpler solution than memoized dp during the contest , considering it a C problem :((((

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the system test is still running

    → Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +75 Vote: I do not like 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 (non-interactive) task.

    I am sorry for the confusion that it apparently caused.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      "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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like 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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nice contest,Beautiful problems

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +77 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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++;
    → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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://mirror.codeforces.com/blog/entry/61683#comment-456882 :)

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    In reality, the uses around 17000 queries.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C , can any one tell me what's wrong in my approach ? why does it give wrong answer on Test 23 ?

http://mirror.codeforces.com/contest/1033/submission/43970251

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I solved it with DP , state: <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 )

    → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any updates on the t-shirt delivery?

→ Reply