### IceKnight1093's blog

By IceKnight1093, history, 5 days ago, 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:

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! Comments (22)
 » Not rated for Div 2 (+.+)'
 » 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
 » 5 days ago, # | ← Rev. 2 →   Solved TREEDIVS without 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.
 » 5 days ago, # | ← Rev. 2 →   How to solve div1 E (treedivs)?
•  » » 3 days ago, # ^ | ← Rev. 3 →   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
 » 5 days ago, # | ← Rev. 2 →   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$ primeSadly 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?
•  » » 4 days ago, # ^ | ← Rev. 2 →   For every prime number $p$, store the following1) 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_bound on 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
•  » » » thanks a lot , got it now!
 » 4 days ago, # | ← Rev. 3 →   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.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.
•  » » » » Can you please elaborate how my solution doesn't fit within the time limit? I can't figure out it's complexity.