CodeAgon 2019 Discussion Thread

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
2 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя codenationtest

CodeAgon 2019 Discussion Thread

Автор codenationtest, история, 5 лет назад, По-английски

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).

codenationtest
5 лет назад
76

Комментарии (66)

Показать архивные | Написать комментарий?

kartik8800

5 лет назад, # |

+23

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.

→ Ответить

Prakash11

5 лет назад, # ^ |

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

→ Ответить

kartik8800

5 лет назад, # ^ |

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.

→ Ответить

kingarp1914

5 лет назад, # |

Where can we see the standings?

→ Ответить

kartik8800

5 лет назад, # ^ |

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

→ Ответить

kingarp1914

5 лет назад, # ^ |

first four

→ Ответить

balu_321_go

5 лет назад, # ^ |

Then when are they going to display the standings?

→ Ответить

rr459595

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

15411019

5 лет назад, # |

Did anyone solve the last one?

→ Ответить

farmersrice

5 лет назад, # ^ |

← Rev. 2 →

+20

It looks like straightforward manacher's algorithm to me.

→ Ответить

ILoveBitches

5 лет назад, # ^ |

I solved it with Palindromic tree :)

→ Ответить

toxic_hack

5 лет назад, # ^ |

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

→ Ответить

ILoveBitches

5 лет назад, # ^ |

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

→ Ответить

toxic_hack

5 лет назад, # ^ |

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

→ Ответить

karansiwach360

5 лет назад, # ^ |

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.

→ Ответить

fugazi

5 лет назад, # ^ |

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.

Spoiler

for(int i = n -1, j = n - 1; i > 0; --i){
    while(j - d1[j] + 1 > i)j--; 
    mx[i] = 2*(j - i) + 1; 
}

→ Ответить

adhoc_king

5 лет назад, # ^ |

Is it monotonic?

→ Ответить

karansiwach360

5 лет назад, # ^ |

Yes, much easier this way.

→ Ответить

Learner99

5 лет назад, # ^ |

+11

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.

→ Ответить

RaunaqRoxx

5 лет назад, # ^ |

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.

→ Ответить

Learner99

5 лет назад, # ^ |

← Rev. 3 →

` Let Arr[i] denote the maximum length palindromic string considering ith element as center. `

` Let pref[i] denote maximum length palindromic with last index <= i `
` We can build pref[i] array in following way. `
for( int i = 1; i<=n; i++ )
      pref[i+Arr[i]-1] = max(pref[i+Arr[i]-1], pref[Arr[i]] ) 

` For ith index we can make pref[i+1]-2 length pan ending here ( removing first and last element from pref[i+1] ) `
for(int i= n-1; i>=1; i--)
      pref[i] = max(pref[i], pref[i+1] - 2) 

` Taking prefix max `
for(int i=2;i<=n;i++)
     pref[i] = max(pref[i], pref[i-1])

You can build suffix array in similar way.

→ Ответить

RaunaqRoxx

5 лет назад, # ^ |

Thank you so much.

→ Ответить

MrAladeen

5 лет назад, # |

← Rev. 3 →

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?

→ Ответить

Enigma27

5 лет назад, # ^ |

+14

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.

→ Ответить

xsanchez

5 лет назад, # ^ |

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

→ Ответить

fugazi

5 лет назад, # ^ |

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

→ Ответить

2020

5 лет назад, # |

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

→ Ответить

karansiwach360

5 лет назад, # ^ |

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$$$.

→ Ответить

2020

5 лет назад, # ^ |

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

→ Ответить

karansiwach360

5 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

techgig0

5 лет назад, # |

Ashishgup please explain the solution to 5th problem.

→ Ответить

Ashishgup

5 лет назад, # ^ |

+37

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

→ Ответить

aditya123garg

5 лет назад, # ^ |

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

→ Ответить

techgig0

5 лет назад, # ^ |

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

node
{
	node bit[2];
	sum = 0;
}

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 PseudoCode

insert(x, val)
{
	node cur = head;
	for(i = 60; i >= 0; i--)
	{
		b = (x >> i) & 1;
		if(!cur->bit[b])
			cur -> bit[b] = new node();
		cur = cur -> bit[b];
		cur->sum += val;
	}
}

Now, 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 PseudoCode

query(x)
{
	node cur = head;
	ans = 0;
	for(i = 60; i >= 0; i--)
	{
		b = (x >> i) & 1;
		if(b == 0 && !cur->bit[b])
			return ans;
		else if(b == 0)
			cur = cur->bit[b];
		else
		{
			if(cur->bit[0] != NULL)
				ans += (cur->bit[0])->sum;
			if(!cur->bit[b])
				return ans;
			cur = cur->bit[b];
		}
	}
	return ans + val[x];
}

I hope this makes sense.

Thank you

→ Ответить

navneet.h

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

ravan

5 лет назад, # |

How to solve 4th ??

→ Ответить

adhoc_king

5 лет назад, # ^ |

Find all possible numbers at each index and then this

→ Ответить

rr459595

5 лет назад, # ^ |

← Rev. 3 →

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?

→ Ответить

adhoc_king

5 лет назад, # ^ |

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

→ Ответить

dominics

5 лет назад, # |

Can we solve the second question using two pointers?

→ Ответить

ak532

5 лет назад, # ^ |

Yes, using the sliding window technique.

→ Ответить

Enigma27

5 лет назад, # ^ |

+12

Yes, we can solve it using two pointers.

Approach

→ Ответить

maheshwari29

5 лет назад, # ^ |

Can you please tell how to code this?

→ Ответить

Enigma27

5 лет назад, # ^ |

+26

Code

/*
Let v  is a vector of pair {ind, char} where ind is the index of the  string and char is the character with odd frequency, 

f = frequency array for characters, distinct = num of distinct char we have got, n = number of characters with odd frequency 

*/

    sort(v.begin(), v.end());
    for(int i=0,j=0;i<v.size();i++){
        while(j<v.size() && distinct < n){
            f[v[j].second]++;
            if(f[v[j].y]==1) distinct++;  // 0 to 1 transition i.e new char encountered
            j++;
        }
        if(distinct==n){
            ans=min(ans,v[j-1].first-v[i].first); // relax the answer
        }
        f[vv[i].second]--;
        if(m[vv[i].second]==0) distinct--;  // 1 to 0 transition   
    }
    cout<<ans<<endl;.

/*
In 4th problem, just make a vector of pair of indices with all possible values that the number at that index can be made. 

Then copy-paste this same solution.
*/

→ Ответить

vivo

5 лет назад, # |

+24

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

→ Ответить

dvshah

5 лет назад, # ^ |

+13

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?

→ Ответить

yas9

5 лет назад, # |

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

→ Ответить

blinkshot

5 лет назад, # ^ |

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.

→ Ответить

Master_coder

5 лет назад, # |

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)

→ Ответить

anupamshah_

5 лет назад, # |

How to approach 4th question ?

→ Ответить

ankitpriyarup

5 лет назад, # |

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

→ Ответить

thisSideAnonymous

5 лет назад, # ^ |

← Rev. 2 →

How many test cases of 5th passed for you?

P.S. — I solved 4

→ Ответить

ankitpriyarup

5 лет назад, # ^ |

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

→ Ответить

geeky.ass

4 года назад, # |

+40

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.

→ Ответить

nik7

4 года назад, # ^ |

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

→ Ответить

do_good_

4 года назад, # ^ |

+27

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

→ Ответить

geeky.ass

4 года назад, # ^ |

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.

→ Ответить

Enigma27

4 года назад, # ^ |

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.

→ Ответить