If this contest has a time limit, Problem C is very interesting

Is there any time limit?

Problem C
Let x be the number which has odd number of odd divisors​. Through observation, you can find that , where e_i is even. In this configuration, total number of odd divisors will be . In other words, we are looking for x = 2^w × 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.

https://algo.codemarshal.org/contests/icpc-dhaka-preli-18

Check prophet_ov_darkness's comment.

What is the O(1) solution for C?

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.

https://algo.codemarshal.org/contests/icpc-dhaka-18

You can submit also