We invite you to participate in CodeChef’s Starters 166, this Wednesday, 25th December, rated upto 5 stars (i.e. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin: Yash yash_daga Daga
Statement Verifier: Kanhaiya notsoloud1 Mohan
Text Editorialists: Nishank IceKnight1093 Suresh
Tester: Manan mexomerf Grover
Setters: Nishank IceKnight1093 Suresh, Kanhaiya notsoloud1 Moha, gg_98, Practice_Track, Eiandy_Bahnady.
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
Good Luck!
Is this rated up to 5 or 6 stars? Website says 5.
It is rated unto 5 stars only, I posted the wrong blog by mistake, really sorry for the inconvenience.
Updated it now.
Reminder: The contest will start in an hour.
Very Strict Time Limits in
All Equal, Nice Problems :) for a changealmost all questions were GPTable. Poor contest.
Screencast of me writing this round in rust
Every single person in the top 25 of div2 has used GPT. This is just pathetic.
There were many cheaters in div1 too:
Rank 1 here Standings Username- optimusprimeop cheated on all questions,look at these submissions — 1 and 2, the number of functions(most aren't required) used for trivial tasks are laughable.
oh yeah. Almost every code I check for the 5th problem is GPT generated in div1. The guy who got rank 1 in div1 has every single question GPT generated.
In the hard version of divisors I didn't noticed that I used map and an extra log(M) factor gave me TLE for 4 times. :(
Why did my submission for Divisors Array(Hard version) give TLE? I think it is within the limits of the constraints.
Link: https://www.codechef.com/viewsolution/1117737372
for(auto x: tmp)m[x.first] += x.second;there are aprox $$$\frac{m}{log(m)}$$$ prime and you are iterating all of them $$$n$$$ times so it's $$$O(\frac{m * n}{log(m)})$$$ which is not within time limit
How is the number of primes m / log(m)??? It is log(m)/loglog(m).
https://en.wikipedia.org/wiki/Prime_number_theorem
That is the distribution of prime numbers themselves. You are getting confused between the two.
i'm not confusing, you didn't even read the provided article
it clearly says.
N / log(N) is the numbers of prime number less than N. But a number can only have log(m) prime factors. so tmp will only have log(m) elements.
But tmp is clearly initialized with all primes up to 10^7
Ohh right... Thank you!!!
what temp stores prime factors of $$$m!$$$ right?
$$$m! = 1 * 2 \ * ... m$$$
all the no. from 1... m are present in $$$m!$$$
how many primes are there in range $$$1...m$$$
$$$O(\frac{m}{log(m)})$$$, so what will be size of temp?
Got it now...I didn't realize that you were pointing to the initialization part. Thank you!!!
May be 664,579(count 1e6) prime numbers below 1e7 and log2(1e7) + log3(1e7).... (count 100). & in the second loop n times over tmp(will have a large size).
tmp will only grow to log(m) so final time complexity should be n * log(m) * log(max(a)). And even the author's solution contains a sieve till 1e7.
Codechef please take this opportunity to go through the code of top 100 of div1 and div2 and ban the people who has GPT code. If you guys are not capable of doing that then unrate this contest. Great way to catch a lot of losers.
Lol. What a joke. Ratings updated with gpt users at the top. Dominater069's math puzzles is better than this shite. Atleast that was GPT proof.
Dominator be like :
What sorcery was DPOWER? caught me off-guard completely. Do you recommend any other similar style problems to better develop an intuition for these? Thanks for the contest!
Same, I thought it was something similar to recent Div3 problem(2051F).But then I guess simple casework did the trick for me fortunately !
I am unable to understand why I am getting run time error for Costly Permutation (COSTPERM)
Link: https://www.codechef.com/viewsolution/1117884655
I would guess stack overflow in dfs?
For problem Divisors Array (Hard Version) I had to use segment trees here. I thought to use persistent segment trees but it was an overkill maybe.
For any number till 1e7 there can be max log2(1e7) around 25 different primes so I update only 25 elements in the segment tree get the answer and re-update the segment tree as it is which is (a+1)*(b+1)*... where a,b,c etc are primes for M! and then a change of max 25 for each element. So total TC = (25 * log2(MAX M) * N) which is 580 something for each 1e5 element should get AC.
Is there any easier way to do this rather than segment trees?
PS: I can't see solution on codechef for obvious reasons.
you can simply multiply updated (a+1) and use modInverse to divide with old (a+1).
Here let M!= p1^a . P2^b ......
so number of divisor of M!=(a+1)*(b+1)....
now let arr[i]=p1^c . p2^d.....
so res=(a+1)*(b+1)*(a+c+1)*(b+d+1)/((a+1)*(b+1))
but u need to use modInverse to divide here