### Mantra7's blog

By Mantra7, 2 months ago,

Link to contest : SPC — Final Contest : )

If you can't see the tutorial then click on above link first.

### A. Fruits

Problem Author : Cheata

Tutorial
Solution

### B. Dice Roll

Problem Author : Mantra7

Tutorial
Solution

### C. Selfie with Tourist

Problem Author : kuki22102002

Tutorial
Solution

### D. Strong Arrays

Problem Author : Abdullah_Md010

Tutorial
Solution

### E. El Clasico

Problem Author : iowiz

Tutorial
Solution

### F. Array Uniformity

Problem Author : sapta0506

Tutorial
Solution

### G. Singleton Code (Easy Version)

Problem Author : sapta0506, KDVinit

Tutorial
Solution

### H. Singleton Code (Hard version)

Problem Author : sapta0506, KDVinit

Tutorial
Solution

### I. Find The String

Problem Author : Mantra7

Tutorial
Solution

### J. Musical Chairs

Problem Author : sapta0506

Tutorial
Solution

### K. Saving the Programming Club

Problem Author : AdC_AB2

Tutorial
Solution

### L. Can anyone solve it?

Problem Author : AdC_AB2, KDVinit

Tutorial
Solution

• +27

 » 2 months ago, # |   +28 Alternate solution to K: SpoilerUse the fact that $lcm(a, b) = \frac{ab}{gcd(a, b)}$. Applying this to the given condition gives $\frac{am}{gcd(a, m)} = \frac{(a+x)m}{gcd(a+x, m)} \implies \frac{a}{gcd(a, m)} = \frac{a+x}{gcd(a+x, m)} \implies x = \frac{a\cdot gcd(a+x, m)}{gcd(a, m)} - a$So, fixing a value for $gcd(a+x, m)$ fixes the value of $x$. $gcd(a+x, m)$ must be a factor of $m$ so try all possible factors $g$ of $m$, compute $x$ for each one, and then check if $gcd(a+x, m) = g$.Doing it this way runs into a couple of issues: 1When computing $x$, you might end up with numbers as large as $1e24$, and that clearly exceeds the range of a 64-bit integer. Multiplying them modulo $1e9+7$ isn't an option because you need the exact value of $x$ to compute $gcd(a+x, m)$. Switching to python or any other language with support for large integers would resolve this problem, but might cause TL issues because limits are quite high. To work around this, note that $gcd(a+x, m) = gcd((a+x)\%m, m)$, so it is enough to know $x$ modulo $m$. 2Naively computing all factors in $\mathcal{O}(\sqrt{m})$ is, in the worst case, $1e6$ operations per testcase and then whatever extra computation is done with each divisor. With 1000 testcases, speed could be an issue. One possible optimization is to use a fast prime factoring algorithm, like Pollard-rho, to find all prime factors of $m$ and then recursively generate all factors from these. This brings the complexity of the factorization part down from $\mathcal{O}(m^{0.5})$ to (expected) $\mathcal{O}(m^{0.25} + \sigma(m))$ where $\sigma(m)$ is the number of factors of $m$, which is about 7000 in the worst case.
 » 2 months ago, # |   +3 Really Amazing and Detailed Editorials. Great work.
•  » » 2 months ago, # ^ |   0 Plz. Can you help on opening the spoiler it says that tutorial is not available.
•  » » » 2 months ago, # ^ |   0 Click on the contest link first.After that, you should be able to see the tutorials.I am not sure why Codeforces works in this way : )
•  » » » » 2 months ago, # ^ |   +8 Thank you for your reply , now it is working.
 » 2 months ago, # |   +12 Solutions for Singleton Code seems strange. After well establishing that S(n) = n % 9 , why not do just that ? My solutions : Easy versionres = 1 for(i=0 to n-1) { res = (res*a[i])%9 } if(res == 0) res = 9  Hard versionres = a[0] % 9 for(i=1 to n-1) { res = (res^a[i])%9 } if(res == 0) res = 9; 
 » 2 months ago, # |   +8 thanks for such a wonderful contest! luckily i solved 6 problems by participating virtually :)