Please use this thread to discuss the problems of CodeAgon 2019.

Q1 : Represent N as sum of minimum numbers ending with 9. eg 28 = 19 + 9, 27 = 9 + 9 + 9.

Q2: Make frequency of each digit even and minimize the last — first deleted numbers index difference.

Q3: Maximum diameter of tree where parent of x = (x — x&(x-1) ). ie last bit unset.

Q4: array of site n, multiply or divide(if possible) by k any number of times. return minimum (MAX — Min) element of modified array.

Q5: online queries of type 1) change value of index x to v. 2) sum of all values with index <= x Q <= 1e5 x <= 1e18

Q6: return max product of size of 2 non intersecting palindromic substring. required in O(n).

Auto comment: topic has been updated by codenationtest (previous revision, new revision, compare).Auto comment: topic has been updated by codenationtest (previous revision, new revision, compare).The third problem said 1<=N, however there were definitely cases in which N was equal to 0. Many wasted quite some time because of this.

floor(log2(n+1))+floor(log2(2(n+1)/3)) Is this the answer for third problem?

You can try comparing the output you get with the output this code gives you and find out https://ideone.com/jQ3whW (not my solution), my approach was different so I can't comment on the correctness of the equation you gave.

Where can we see the standings?

I don't think it is possible to view standings as of now. How many did you solve?

first four

Then when are they going to display the standings?

Most probably never as they have intentionally changed the interface(more like hiring contest) this time where you can't see standings.

Did anyone solve the last one?

It looks like straightforward manacher's algorithm to me.

I solved it with Palindromic tree :)

How did you handle the only odd length palindrome condition? Did you remove the type — 2 root?

toxic_hack If the length of maximum palindromic suffix ending at index i is even, and the length of palindromic suffix ending at index i with odd length is x, there always exist a index j before i where length of maximum palindromic suffix ending at j is odd and >=x

How can you prove this? Seems like complete magic to me.XD

For every index $$$i$$$, calculated maximum palindrome length if this is the center element of that palindrome using binary search and hashing.

Updated in two lazy segment trees, maximum possible length of palindromes ending at a position and starting from a position. After that, it is straightforward to calculate best possible answers for each position. Could not debug in time, just passed 17 of 29 test cases.

You don't need lazy segment tree for the later part.

Suppose you have the array $$$d1[i] = \text{maximum length palindrome centred at i}$$$, then to find $$$mx[i] = \text{length of maximum length palindrome starting at } i $$$, we need to know the furthest center of a palindrome possible from i, that can be done by two pointers.

SpoilerIs it monotonic?

Yes, much easier this way.

You can do binary search and using string hashing find max length considering this index as a center.

Build a prefix max and suffix max array where prefix(i) denotes length of longest string which is palindrome and has a ending point <= i. Suffix(i) denotes length of longest string which is palindrome and has a starting point >= i.

Iterate over all index and update answer. Ans = max( Ans, pref(i)*suff(i+1) )

If you want, I can elaborate on how to build the prefix and suff array.

It would be really helpful if you could elaborate on building the prefix and suffix array, I have an intuition it requires building the longest prefix suffix array, but can't really use it to find what the question wants. Thanks in advance.

You can build suffix array in similar way.

Thank you so much.

In 5th question I used simple BIT (point update and range sum query) with map but was getting TLE for large x.

How to optimize it?

You can use dynamic segment tree to solve this problem, which is nothing but a trie like implementation of segment tree. Refer the last point of this blog for implementation.

Was there some more optimization in it ? Because dynamic segtree was giving tle for range 1e18 .

Just creating exactly the nodes with data in them, and not using long long for every variable converted my TLE to AC.

My solution was failing at Test Cases #0 and #1. Can anybody please point out, where I might be going wrong?

For second binary search on length is the way to go?, And can someone give some idea about 4

Insert all possible values in a min-heap/multiset with indices. Suppose, in the beginning, there is nothing at all indices. Continuously pop-out values from the multiset, at each instance the popped-out value $$$X$$$ with index $$$i$$$ is the maximum and if at least one value has been popped out for all indices, the current answer will be $$$X-$$$min of (max of previously popped-out values for an index) for all indices except $$$i$$$.

lets take an example 1 5000 9999 and k =10000 now can you explain with this example please

Multiset will contain (1,0), (10000,0), (5000,1), (50000000,1), (9999,2), (99990000,2) in sorted order. First popped value (1,0), then (5000,1). Then, (9999,2) is popped, after which at least one value for each index 0, 1 and 2 has been popped out. With minimum of maximum of values at each index popped except 2 is 1. So, current answer is 9999-1.

Then (10000,0) is popped out, then min of max of values at each index popped out except 0 is 5000. Current answer is min(ans, 10000-5000). Then similarly 50000000-9999, then 99990000-10000.

Not a working code but it's well commented :) might help someone see how to do binary search on length of sub-string. link

AshishGup please explain the solution to 5th problem.

There were many approaches to solving the problem, but here is mine:

For the subtask with Q = 1e5, X = 1e9, there was a very short Q log^2N code using a BIT (Map instead of array): http://p.ip.fi/trAf

Whereas for the full version with Q = 2e5, X = 1e18, there was a Q logN code using approaches like dynamic segment tree or tries. I personally used tries because I find it easier to code: http://p.ip.fi/FG_F

Can you please explain how you are storing the sum and querying it. And if you can share some problems like this.

Allow me to explain the amazing approach of AshishGup. First of all, now using dynamic segment trees or using sqrt decomposition seems to be overkill.

Whoever is reading out this must try out problem of finding max XOR in an array using trie first then move ahead. A node structure representing a bit in trie would be like

The head of trie would point to the most significant bit. At each node we will store sum while we are updating. Lets say $$$110010$$$ and $$$110110$$$ has come then in our trie, at $$$3rd$$$ node we are actually storing sum for both of numbers with same pattern of bits before it.

Insert PseudoCodeNow, while querying we will traverse through bits/nodes of $$$X$$$(the input) and whenever its $$$ith$$$ bit is $$$1$$$ we will add sum stored in corresponding node for $$$0th$$$ bit. This is because we are assure that if $$$ith$$$ bit of $$$X$$$ is $$$1$$$ then all numbers whose $$$ith$$$ bit is $$$0$$$ will be smaller than $$$X$$$.

Remember we will not do this when $$$ith$$$ bit is $$$0$$$. This is easy to prove. This is left as a task.

Query PseudoCodeI hope this makes sense.

Thank you

if unordered_map was used,would it still be tle. but very cool trick, using map in bit, saw it first time.what other places could we use map instead of array, like segtree.

How to solve 4th ??

Find all possible numbers at each index and then this

If array is {5,6,2} and k=3, which possible numbers will you store for first index? I mean how many times will you multiply a number by k and store it?

You'll multiply once as it will become divisible by k

Can we solve the second question using two pointers?

Yes, using the sliding window technique.

Yes, we can solve it using two pointers.

ApproachFor each character with odd frequency, push its indices in a vector.

Now you have $$$n$$$ vectors($$$n = $$$ number of characters with odd frequency), and you have to take one element from each of them such that Max — Min is minimized.

This is the exact same problem as the problem no. $$$4$$$ which can be solved using two pointers

Can you please tell how to code this?

Codewhat can be possible values for index in que. 4

Had issues with the compiler of 4th question. Did anyone else have?

There was some issue with the Sample test case. However, if you use custom input or run all test cases, then test cases run as intended. Also, does anyone know when will we be able to see the rank list?

Its embarrassing to ask but how to approach the first question? I tried a greedy solution but it was failing

First of all you have to look at the last digit of the number, it will directly tell you the answer of the question (if it exists). How ?

Because the last digit of multiples of 9 follow the repeating pattern :- 9, 8, 7,.. 2, 1

For eg. if n = 357, you can say the answer is 3 because 9 + 9 + 9 = 27 and guess what you just have to change the one number of these three. Like 357 = 339 + 9 + 9.

Now you should also check for whether answer exists. For that, first find the expected answer, say x and substract (x — 1) * 9 from n and if it is less than 9, the answer doesn't exist.

Oh yes. Thank you!

what wrong with my 3rd solution only getting 9 testcases AC . my solution is x = log(n) , p = pow(2,x) remain = n-p+1 , second = log(remain) ; ans = max(2*x-1,second+1+x)

How to approach 4th question ?

How many questions did you guys solved? Trying to get a little idea about leaderboard here. I solved 4 completely and 5th one partial

How many test cases of 5th passed for you?

P.S. — I solved 4

11/21 and in 6th 3 I don't think 6th one will count

I solved 3 and got 7/29 in 6th question.

codenationtest Ashishgup Enigma27 When are the results out? In case, you have already contacted the shortlisted participants, we would really like to see the leaderboard as it was also a prize-based contest and transparency is expected.

Why are you tagging these persons. Did they organise the contest

If anything is related to India, Ashishgupta needs to be tagged. Its mandatory.

I assumed they were the problem setters as they were active in this blog and are associated with CodeNation. I apologize if they aren't involved in this contest.

I was not the problemsetter.I participated in contest same as you. AFAIK top 20 contestant have already been contacted for prizes. They contacted me for the interviews but I think that was from their previous pool-test.

Oh! Btw, how many did you solve? And were you in the top 20 contestants?

I solved 5 problem and took partial in 6th. There are more than 20 people who solved all the 6 problems.

That'd be great, thanks :)

geeky.ass How many did you solve?

I solved the first 4 completely and got partial points in the 6th problem. How about you?