Reminder: in case of any technical issues, you can use lightweight websites m1.codeforces.com, m2.codeforces.com or m3.codeforces.com ×

### Bojack's blog

By Bojack, history, 7 months ago, ,

Let's discuss the problems.

Problem Set

•
• +6
•

 » 7 months ago, # |   0 Auto comment: topic has been updated by Hunter_Gon (previous revision, new revision, compare).
 » 7 months ago, # |   0 Auto comment: topic has been updated by Hunter_Gon (previous revision, new revision, compare).
 » 7 months ago, # |   0 How to solve C, D, H, J.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 If this contest has a time limit, Problem C is very interesting
•  » » 7 months ago, # ^ |   0 Is there any time limit?
•  » » » 7 months ago, # ^ |   0 Yes, Time limit — 2s.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +3 Problem C Let x be the number which has odd number of odd divisors​. Through observation, you can find that , where ei is even. In this configuration, total number of odd divisors will be . In other words, we are looking for x = 2w × y, where y is a perfect square number.You should solve the problem for range [1, N], and print solution of range [1, R] minus solution of range [1, L - 1]. To solve for [1, N], you should iterate for all possible power of 2. For each k, add .Problem D Firstly design a function f(n), which returns the highest number which is smaller than n, and has the digits allowed in the problem statement. This can be easily done with greedy observations. You can now start with input N, and iterate by setting N = f(N) each time. Stop this iteration and print the answer, when current N is prime. Use Miller-Rabin for primality testing. I don't know the proof why a prime number with the given definition can be found with small number of iterations. We went with intuition. If anyone can prove it, then please share it here.Problem H Trivial dynamic programming solution. States: idx, lastColor.Problem J You can always make the longest possible path in the answer graph equal to 1. Make the tree rooted. Toggle the direction of edges in consecutive levels to face different directions. Let's say u - v be an edge, where u is at level i. Set the direction of the edge from u to v. Now, let v - w be an edge, where v is at (i + 1)th level, Here set the direction from w to v.
•  » » » 7 months ago, # ^ |   0 Thanks bhaai.
•  » » » 7 months ago, # ^ |   0 And will the problem set be added to gym?
•  » » » » 7 months ago, # ^ |   0 Lol. I don't know anything about it. I was a participant in this contest.
•  » » » » » 7 months ago, # ^ |   0 And if it is possible, can you please write an editorial for other problems too? It would be great for us.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   -14 oo
•  » » » 7 months ago, # ^ |   +5 For problem D: here
 » 7 months ago, # |   +3 Where I can submit?
 » 7 months ago, # |   0 What about problem D? Our team got AC on problem C in a O(1) solution.
•  » » 7 months ago, # ^ |   0 Check prophet_ov_darkness's comment.What is the O(1) solution for C?
•  » » » 7 months ago, # ^ |   0 The numbers to count have even power of odd primes. They can or can't have even power of even prime, 2. So, the number of numbers those are either square or double of a square counts. But precision is an issue that was to be solved.
•  » » » » 7 months ago, # ^ |   0 How did you solve the precision error?
•  » » » » » 7 months ago, # ^ |   0 We got Wrong Answer for precision error while calculating square root of a number. So instead my teammate did binary search to calculate square root.Also you can use sqrt((double) value); This is called typecasting. Really important issue.
 » 7 months ago, # |   0 for problem G — is it possible to solve it in less than o(10^8).. 10^8 will get TLE I think. if it possible to solve it in less complexity pls share your idea
•  » » 7 months ago, # ^ |   0 Many people solved it in that way, they got AC.
 » 7 months ago, # |   0 how to approach the problem I (Vugol search)????
•  » » 7 months ago, # ^ |   +4 We solved it using trie.For any query, note that we can do any of the following. Find an anagram fron the database and try to maximize lcp+smartness Ignore the anagram thingies and just try to maximize lcp For the latter, keep a trie using all the words from the database. Now traverse for the query word and take the maximum lcp.For the first part, find out which strings in database are anagrams of each other. You can partition them into components by simply sorting the characters of those strings. Now for each such component i.e. the strings which are anagrams of each other, make a trie consisting of the database words. Find out which query words are anagrams of these strings. Traverse the trie and try to maximize the results by a rmq-similar approach.
•  » » » 7 months ago, # ^ |   0 How to solve E?
•  » » » » 7 months ago, # ^ |   +3 This should help: #
•  » » » 7 months ago, # ^ |   0 can u briefly explain the approach of finding anagrams from the trie plz?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +4 We can internally sort the strings. Like "me" becomes "em". Now the strings with the same sorted outcome are anagrams of each other. Build a trie using those strings. Similarly find out which query strings have the same sorted outcome i.e. anagrams of these strings. For those queries, traverse the trie and update the maximum value if possible.I tried to draw something: (Not exactly sure if it helps. I am bad at explaining things, I guess.) ( If the image doesn't show: https://pasteboard.co/HHl76cI.jpg )
•  » » » » » 7 months ago, # ^ |   +3 tnx a lot :). And u are good enough to explain something :)
•  » » » 7 months ago, # ^ |   0 How did you solve F (find the substrings)?
•  » » » » 7 months ago, # ^ |   +3 We calculated the number of distinct sub-strings for every length upto |s| using suffix array. Then it got pretty easy. We had d_i as the number of distinct substrings of length i, the result is summation of (26^i — d_i) for every i from n to m. mochow did it. :3
 » 5 months ago, # |   0 does anyone have the problem set of onsite dhaka regional?