The Lyft Level 5 Challenge 2018 Elimination Round (Div. 1 + Div. 2)

6 лет назад, # ^ |

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.

→ Ответить

Jasperr

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Iightcode

6 лет назад, # ^ |

+13

Found the American.

→ Ответить

SameerGulati

6 лет назад, # |

+58

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

→ Ответить

Yoring42

6 лет назад, # ^ |

+68

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

→ Ответить

aryaman

6 лет назад, # |

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

→ Ответить

ContestDestroyer

6 лет назад, # ^ |

Cuz he is green.

→ Ответить

rotavirus

6 лет назад, # |

+101

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

→ Ответить

rotavirus

6 лет назад, # |

+32

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

→ Ответить

140870

6 лет назад, # |

-40

Is It RaTeD ?

→ Ответить

qmk

6 лет назад, # ^ |

+49

swap(Is,It)

→ Ответить

Vergara

6 лет назад, # ^ |

+22

It Is RaTeD?

→ Ответить

OrzAM

6 лет назад, # |

← Rev. 2 →

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.

→ Ответить

ashkANOn

6 лет назад, # ^ |

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

→ Ответить

OrzAM

6 лет назад, # ^ |

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

→ Ответить

Anguei

6 лет назад, # |

+18

It is a CuSi Round for Chinese.

→ Ответить

Kerpoo

6 лет назад, # |

← Rev. 2 →

-20

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

→ Ответить

6 лет назад, # ^ |

-7

Never mind, Morokei has solved the problem! ;D

→ Ответить

Kerpoo

6 лет назад, # ^ |

-7

The game whitout Mo is perfect to! :(

→ Ответить

6 лет назад, # ^ |

My last hope crashed );

→ Ответить

rezcoder_

6 лет назад, # |

-25

I wish everyone success !

→ Ответить

6 лет назад, # ^ |

-27

Or maybe I wish myself contribution !?

→ Ответить

6 лет назад, # ^ |

I see some bitter irony in all this downvotes.

→ Ответить

sharmajatin741

6 лет назад, # |

-56

?DETAR TI SI

→ Ответить

_Ash_

6 лет назад, # |

← Rev. 2 →

-11

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

→ Ответить

Castle_Master

6 лет назад, # ^ |

Before getting job, i need some positive rating !

→ Ответить

Ahnaf.Shahriar.Asif

6 лет назад, # |

← Rev. 3 →

-31

→ Ответить

eisen_shinzou

6 лет назад, # ^ |

And also downvoting whoever say it...

→ Ответить

Ashish

6 лет назад, # |

Clashes with Liverpool vs Manchester city :-/

→ Ответить

Lord_Zebellak

6 лет назад, # |

+10

I dont wanna die without a tshirt.

→ Ответить

otaliptus

6 лет назад, # |

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

→ Ответить

cannabutter

6 лет назад, # |

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

→ Ответить

subash23

6 лет назад, # |

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

→ Ответить

vivek_shah

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

Maybe you didn't go from the biggest number to the smallest...

→ Ответить

vivek_shah

6 лет назад, # ^ |

I did go from biggest number to smallest. Code

→ Ответить

6 лет назад, # ^ |

I just can't see you code on Codeforces before the end of the systesting...

→ Ответить

vivek_shah

6 лет назад, # ^ |

Made redundant recursive calls and hence it caused TLE. Now I get AC! >_<

→ Ответить

6 лет назад, # ^ |

Oh, thanks! I've just find out that the order doesn't matter.

→ Ответить

TooNewbie

6 лет назад, # |

+29

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

→ Ответить

Evro

6 лет назад, # ^ |

+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

→ Ответить

madhur4127

6 лет назад, # ^ |

same approach, but verdicts WA, any corner case?

→ Ответить

YouKn0wWho

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

ibra

6 лет назад, # ^ |

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

→ Ответить

farmersrice

6 лет назад, # |

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

→ Ответить

Diegogrc

6 лет назад, # ^ |

← Rev. 3 →

-8

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

UPD : Got TLE :/ Nevermind

→ Ответить

Errichto

6 лет назад, # ^ |

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

→ Ответить

faceless_man

6 лет назад, # ^ |

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

→ Ответить

ciphereck

6 лет назад, # ^ |

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

→ Ответить

Errichto

6 лет назад, # ^ |

See my code or read the editorial.

→ Ответить

Jakube

6 лет назад, # ^ |

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.

→ Ответить

antguz

6 лет назад, # ^ |

← Rev. 2 →

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

EDIT: Too late :P

→ Ответить

Saat

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

Solution for D?

→ Ответить

OkRint

6 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

6 лет назад, # ^ |

thanks +1

→ Ответить

juanigsrz

6 лет назад, # ^ |

← Rev. 3 →

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

I think you meant 2

EDIT: Nvm i read incorrectly

→ Ответить

OkRint

6 лет назад, # ^ |

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

→ Ответить

I_Love_CardiB

6 лет назад, # |

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

→ Ответить

misael

6 лет назад, # ^ |

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

→ Ответить

I_Love_CardiB

6 лет назад, # ^ |

← Rev. 13 →

Bro, i am not asking the solution, i am asking about the input format.

here's my solution: http://codeforces.me/contest/1033/submission/43971194 Tell me why is this giving idleness time exceeded?

→ Ответить

Priyam2k

6 лет назад, # ^ |

You need to flush the output using fflush(stdout) or cout.flush() in C++;. Anyways you'll fail pretest 1.

→ Ответить

aman28rwt

6 лет назад, # ^ |

You have to flush the output

→ Ответить

I_Love_CardiB

6 лет назад, # ^ |

Yeah, i used endl for that.

→ Ответить

golions

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

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

→ Ответить

starboy_jb

6 лет назад, # |

what a contest.

Mathematics rocks.

→ Ответить

natofp

6 лет назад, # |

-14

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

→ Ответить

FieryPhoenix

6 лет назад, # ^ |

The statement guarantees it's not.

→ Ответить

natofp

6 лет назад, # ^ |

-8

Where?

→ Ответить

AkiLotus

6 лет назад, # ^ |

It is guaranteed that Bob's king is currently not in check and the target location is not in check either.

→ Ответить

natofp

6 лет назад, # ^ |

nvm im stupid

→ Ответить

hell_hacker

6 лет назад, # |

← Rev. 3 →

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.

→ Ответить

AkiLotus

6 лет назад, # ^ |

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

→ Ответить

hell_hacker

6 лет назад, # ^ |

Thanks. realized it later.

→ Ответить

6 лет назад, # ^ |

If I understand this correctly, it fails if your input is p², pq, because you ignore the p² when you process pq even though they share a factor in p.

→ Ответить

shivam7

6 лет назад, # ^ |

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.

→ Ответить

yashChandnani

6 лет назад, # |

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

→ Ответить

Dalisyron

6 лет назад, # |

-14

Problem D solution can be found here

→ Ответить

6 лет назад, # ^ |

-9

Why copied problems.who knows it will just copy paste

→ Ответить

6 лет назад, # ^ |

+20

I see very little in common between these two problems, it is pretty much like saying "Here is wiki article about problem D".

→ Ответить

6 лет назад, # ^ |

ohh i just wrote it because link leads to a code

→ Ответить

Dalisyron

6 лет назад, # ^ |

← Rev. 2 →

-19

→ Ответить

deepak_d14

6 лет назад, # |

How to Solve C??

→ Ответить

RoadToTheMaster

6 лет назад, # ^ |

-18

Just simple DFS

→ Ответить

iamdeepak

6 лет назад, # ^ |

I am stupid

→ Ответить

Heisenberg302

6 лет назад, # ^ |

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.

→ Ответить

xsc

6 лет назад, # ^ |

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

→ Ответить

sshhhh

6 лет назад, # ^ |

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

→ Ответить

xsc

6 лет назад, # ^ |

Recursive dp.

→ Ответить

xsc

6 лет назад, # ^ |

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;
}

→ Ответить

sshhhh

6 лет назад, # ^ |

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

→ Ответить

Heisenberg302

6 лет назад, # |

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

→ Ответить

6 лет назад, # |

← Rev. 2 →

My solution for D:

Notice that to have 3, 4, or 5 divisors, the number must be in the form p², p³, p⁴ 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 $\text{[math]}$ .

EDIT: Oh but I failed systests anyway RIP.

→ Ответить

ramanujan22

6 лет назад, # ^ |

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 ?

→ Ответить

blue__legend

6 лет назад, # |

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

→ Ответить

RobeZH

6 лет назад, # ^ |

Because the system test is still running

→ Ответить

lucaasdamaso

6 лет назад, # |

+33

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

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.

→ Ответить

6 лет назад, # ^ |

+10

Thank you! Together with comment by KAN, it cleared my doubts.

→ Ответить

KAN

6 лет назад, # ^ |

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.

→ Ответить

M_H_H_7

6 лет назад, # |

+22

Nice contest,Beautiful problems

→ Ответить

P___

6 лет назад, # |

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!

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

flygrounder

6 лет назад, # |

-18

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

harshits2808

6 лет назад, # ^ |

+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++;

→ Ответить

Evro

6 лет назад, # |

+14

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

→ Ответить

AkiLotus

6 лет назад, # |

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

→ Ответить

k_8

6 лет назад, # |

+14

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

→ Ответить

riela

6 лет назад, # |

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

→ Ответить

adamant

6 лет назад, # |

+15

Why did you cut off $\text{[math]}$ solution from $\text{[math]}$ solution? First one is already tedious enough to write...

→ Ответить

6 лет назад, # ^ |

In reality, the $\text{[math]}$ uses around 17000 queries.

→ Ответить

ajecc

6 лет назад, # |

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

→ Ответить

drastogi21

6 лет назад, # |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

+86

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

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

Sadly, this is $\text{[math]}$ .

Alternatives are

s += '0'
use std::stringstream
std::string s(n, '0')

The best one in this particular case is 3.

→ Ответить

drastogi21

6 лет назад, # ^ |

+27

Thanks for your reply, it now runs in 77ms.

→ Ответить

WinstonWolf

6 лет назад, # |

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

→ Ответить

FelixMP

6 лет назад, # ^ |

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

→ Ответить

WinstonWolf

6 лет назад, # ^ |

+10

Ok i got it, Thanks brother :)

→ Ответить

FelixMP

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+26

Test 16 is a random test, where each number is a product of two primes slightly over 10⁹. Pretest 10 is the same random test, but with a different seed. So there should not be anything special about it.

→ Ответить

Heisenbug

6 лет назад, # |

+63

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

→ Ответить

Arterm

6 лет назад, # ^ |

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

→ Ответить