We invite you to participate in CodeChef’s Starters 57, this Thursday, 22nd September, rated for Div 3 & 4 Coders.
Time: 8 PM — 11:00 PM IST
Joining us on the problem setting panel are:
Setters: Nishank IceKnight1093 Suresh , S.Manuj DarkSparkle Nanthan, Srikkanth srikkanthr Ramachandran, Arpit Dutt ashwathamaa Dixit, Raghav rag-hav Agarwal, Milind jainmilind Jain
Tester: Takuki tabr Kurokawa
Statement Verifier: Nishank IceKnight1093 Suresh
Contest Admin: Nishank IceKnight1093 Suresh
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they 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!
Unrated for div2 again lol
It's quite irritating when you suddenly remove a division(here div-2) from rated participation. I think you guys should judge the contest beforehand to avoid miscommunication because lots of users have to reschedule themselves accordingly!
I just noticed it. Skipped my final exam studies for nothing lol
Solved
TREEDIVSwithout even knowing the constraint on $$$T$$$ (number of tests)This is what happens when there is only one tester..
"The sum of N across all test cases won't exceed 3⋅10^4" and "N >= 1" implies "T <= 3⋅10^4".
Agreed that "T >= 1" was missing.
Actually in my AC solution, I am
memsetting an array of size $$$10^6$$$ in each testcase, so I thought $$$T$$$ shouldn't have been as big as $$$3 \cdot 10^4$$$, else it would have TLE-d, but seems like I am wrong.The largest $$$T$$$ in the testfiles is a bit more than $$$1100$$$, which is also the case where your code took the most time.
That's still more than $$$10^9$$$ operations, but luckily for you memset is generally pretty fast. I didn't really expect submissions in anything other than $$$\mathcal{O}(N \cdot \text{something})$$$ per test case so I figured providing the sum of $$$N$$$ would be enough, which in retrospect was probably not the best decision.
How to solve div1 E (treedivs)?
I solved it using euler tour, linear sieve and Mo's Algorithm. Number of factors = product of (power of primes + 1)
I thought of Mo's Alogrithm because N <= 3e4.
https://www.codechef.com/viewsolution/74864374
In probelm Div2 E (TREEDIVS):
I calculated prime numbers upto $$$10^3$$$. Then stored the frequency of the prime factors of the value of each node in a 2D array. Then using a DFS I merged the frequencies of child nodes with parent node. Finally calculated number of divisors for each node using the formula: $$$nod = \prod\limits_{i=0}^{primes.size()}(fr_i+1)$$$ where $$$fr_i$$$ is the frequency of $$$ith$$$ prime
Sadly I got WA :( Any idea why? Or is the approach wrong?
my code
Why is NN 200 in your code? Are you claiming there are only 200 prime factors?
There are 168 prime numbers upto $$$10^3$$$ so I took a slightly bigger number
What about the primes greater than $$$10^3$$$ ? A number can have a prime factor greater than the square root. Did I miss anything from your code? Are you considering those?
Ohh you are right!! completely missed it lol.
thanks for your help! :)
how to solve Delicious Queries?
For every prime number $$$p$$$, store the following
1) Indices for which $$$a[i]$$$ is divisible by $$$p$$$.
2) Prefix sum of elements at these indices
3) Prefix sum of the sorted(descending) array of elements at these indices.
Also store the prefix sum of the original array. On a query, find the last index $$$\leq k$$$ such that $$$a[i]$$$ is divisible by $$$p$$$ using
upper_boundon the first array. Now subtract prefix sum at this position and add best prefix sum(descending sorted) at this location.https://www.codechef.com/viewsolution/74951342
Tree and Divisors can be solved with small-to-large merging on the tree. Note that if the prime factorization of a number is given by $$$x = \Pi \;p_i^{n_i}$$$ then the number of factors of the number is $$$\Pi\;(1 + n_i)$$$. Here is a blog which I wrote on small-to-large merging a while back.
Blog — https://mirror.codeforces.com/blog/entry/103064
Codechef solution — https://www.codechef.com/viewsolution/74799354
I used that but still TLEd on 5/11 test cases. Code
You are iterating over all primes in the subtree of the current node at the end of your dfs. That defeats the whole purpose of small to large. Instead maintain the answer for each subtree and divide and multiply when you insert a new number into it. So it will be better to first find the largest subtree and then insert all numbers into it.