ICPC India 2021 Preliminary Online Round is happening at 4th of September 2022 from 8:00-10:30 PM IST here.
Let's use this blog to discuss the round after it ends. I know there is one more blog but it already 256 comments and it would be tedious to continue this round discussion there.
Hope to see you all on the leaderboard.
Pune gwalior me distinct colleges kitne h?
around 115
From which source or site you are telling this??
i copied all the teams from teams section under the Gwalior pune and removed duplicate colleges.
How to solve LEXRIS?
I tried with trie and segment tree but that didn't work.
I solved it with Polynomial Hashing with DP Segment Tree.
If anyone wants the implementation then here you go :)
First calculate the lexicographic order of substrings. Now dp[i][j] = best possible result if (i,j) is your first substring. You will need to maintain suffix maximums to query over only substrings lexicographically larger than first string
calculate the lexicographic order of substrings. Is there a way to do this quickly? During the contest we felt that sorting all substrings naively would TLE.
No that won't give TLE since it is N^3
I thought that sorting of every substring using
std::sort
would take $$$\mathcal{O}(N^3\log(N^2))$$$ time in the worst case. Isn't that true ?$$$log(n^2) = 2 log n$$$ so it is $$$O(n^3 log n)$$$ in worst case which is fine
It's easy,
dp[i][j]=max score if s[i..j] is your last substring
. Now the transition isdp[i][j]=score[j-i+1]+max(dp[k][l]) where l<i and s[k..l]<s[i..j]
. Now notice that you can easily check this using LCP and Suffix Array. Then it's just some case handling depending on whether the LCP iss[k..l]
,s[i..j]
, or both, or neither. Notice that you can maintain prefix max for each row of the DP to quickly get the answer. Then you can take max over all (and0
, of course).Submission (uncommented)
I was taking prefix max of only the previous row in my code and that passed the samples. I only realised my mistake after the contest. I'm so mad right now.
Sorting (Lexicographically), then calculated all substring which are same because we cannot select substring with same values we need to select strictly increasing in lexicographic order.
Used Fenwick tree to find prefix maximum score.
Now to select each substring (l , r). We need to find the a substring which ends before l (Non overlapping) and is Lexicographically smaller which was maintained by sorting already. So i used fenwick tree to find maximum score till [0 , l-1] and updated current score at r because no substring starting before r can be selected with current subrting. This update also makes a maximum update from (r , n). Please view code for better understanding.
Code for reference Click Here
So our Solution used this same idea
We iterated through every $$$ N*(N+1)/2 $$$ subtrings and inserted them into the trie. And while inserting in the trie we maintained a vector denoting all sub-strings that ended at that node. Now we did a dfs traversal on the trie to get the lexicographical order of all the substrings (and as well as it covered the case of substrings which are equal).
Now one thing to note here is that let's suppose we are on a substring $$$ (i,j) $$$ then the only thing matters is what is the ending index of this segment for substrings having their starting point $$$ > j $$$ if they are in lexicographical order.
So we used 1d dp array, where $$$ dp[i] $$$ stores the best score one can achieve among all the sub-strings that ends at $$$ i $$$.
Now using above observation it was just dp + prefix max query to find the max value we can get from the prefix $$$ [0...i] $$$. So we iterated on this lexicographical ordered substrings and updated the dp value simultaneously.
Time Complexity: $$$ O(N^3) $$$
Space Complexity: $$$ O(N*N*26) $$$
Sorry if wasn't able to explain it properly. You can check out the solution code and comment if found anything wrong in explanation.
Solution
Also what would be the CF rating for this problem ?. My guess is 2100+ .
No offence, We secured $$$ 70th $$$ rank (missed by one).
This is what we did(without any Complicated data structures):
Define dp[i][j] as the maximum score for the suffix [i..n] such that the first substring starts at index i and has a length j.
Now, step 1 is to precompute longest_common_prefix[i][j] as the length of the longest common prefix of substrings starting at i and j respectively for all i,j. This can be done naively in O(n^3) time.
Now, coming to the transitions, to calculate dp[i][j], we will iterate for k, that is, the starting point of the next substring. Now if lcp[i][k] is 'L' and s[k+L] > s[i] OR if L>=j, then we can say that dp[i][j] = max (dp[k][L+1] + a[j], dp[k][L+2] + a[j]....).
This can be done quickly by maintaining suffix maximums.
There is no need for seg tree or fenwick tree. Just sort all the substrings in increasing order. Consider a substring $$$[i,j]$$$ as an interval $$$(i,j)$$$. Every interval has some priority (which is of course, determined by its position in sorted order).
Now imagine placing intervals in increasing order of their priority (i.e from smallest lexographical order to largest). Suppose you're at the $$$i^{th}$$$ substring. Let $$$l(i)$$$ and $$$r(i)$$$ denote the left and right endpoint of the substring.
Define $$$dp[r(i)]$$$ as the maximum score you can get if you place the $$$i^{th}$$$ substring at the last operation, so, $$$dp[r(i)] = max ( dp[j] + cost[r(i)-l(i)+1] )$$$ for all $$$j$$$ such that $$$j<l(i)$$$.
This is because at last I'm placing the substring $$$[l(i) , r(i)]$$$, so before that I must have placed a substring $$$[l(j),r(j)]$$$ such that $$$r(j) < l(i)$$$ (substrings must be non overlapping), and since I'm placing substring in increasing order, its guaranteed that $$$j^{th}$$$ string will be smaller than $$$i^{th}$$$ string (there's a small catch here but you can easily fix it ;) ).
Since there are $$$O(n^2)$$$ substrings and for every substring I will iterate through all $$$j$$$'s, there are only $$$O(n)$$$ right endpoints, so it would take $$$O(n^3)$$$ time.
Note that you can sort all substrings using trie, so that would also take $$$O(n^3)$$$ time :)
Very neat and simple solution, thanks for sharing. Can we extend this and use Suffix Array/Segment tree to solve in $$$O(N^2)$$$?
Looks difficult, sorting is also the bottleneck. You can optimize dp transitions using seg tree, but I don't see how can we do sorting in $$$O(n^2)$$$ using suffix tree. (I don't know much about suffix array)
We can do the sorting in $$$O(n^{2}\log{}n)$$$ by precalculating lcp in $$$O(n^{2})$$$ for all pair of suffix of the string starting at $$$i,j$$$.
Nice !
When will the final result come?
Kinda mad that my LEXRIS failed because it had anti-hash tests :(
How to solve Beautiful Array?
Can anyone provide a counter case to the following idea (except for $$$n \leq 4$$$):
Conditions extend to also imply $$$a_i \ne a_{i + 1}$$$.
Brute over all possible values for the MOD 3 positions in $$$O(n ^ 3)$$$.
For each triple, try to perform swaps between each pair when they have each other's values. I think the order in which we perform the swaps shouldn't matter since we only have 3 positions (I couldn't find a countercase with $$$n \leq 10$$$ while stress testing).
Same as what I did. Did you fail at test 11 too?
You forgot to resolve 3-length cycles, i guess...
Consider the array,
[1,2,3,1,2,3,1,2,3,1,2,3, 2,3,1]
is your answer 2 for this case?
Even handling n=4 was quite tricky imo.
Agreed.
I simplified it though, basically the answer can't be more than 2, you can just change 1st and 4th element to get a beautiful array.
You can easily check if answer is 0, now just check if answer is 1.
If 1st and 4th elements are equal, you just wanna make 2nd and 3rd element different from 1st, if that can be done in 1 move, answer is 1.
If 1st and 4th element are unequal, then either 1st element will take 4th's value or vice versa, so just try both and this case can also be checked pretty easily.
Another way could've been, to make a check function and then try every move on the array and check.
What we came up was even simpler, I have no proof to why this works but just intuition.
We failed at test 5.
But this got WA, can anybody get why?
Code Link : Beautiful Array
You need to handle the cases for n = 3 and n = 4 separately as well. Here is a failing test case:-
answer should be 0 your code gives 1
We didn't even think about this while debugging. We were so sure we were messing up the implementation part. Damn.
Thanks for the reply.
Congrats for failing.
Next time fail better
For the amrita puri regionals, Will the first team after rank 30 be eligible for regionals? Even if there are some teams below 30 from the same college.
Vichitr Any update regarding this?
I found out that answer for E is $$$m^{th}$$$ term in Expansion of $$$\frac{1}{(1+x)(1-x)^{n+1}}$$$ for all even $$$n$$$ except $$$n=2$$$, for which its just $$$ceil\left({\frac{n^2}{2}}\right)$$$ by OEIS.
How funny it'd have been if I OEIS'd my way into the regionals
But idk how to fft, also no time
How do you get this?
Warning: Looking at the image in spoiler may give you eye cancer
I did this for $$$n=2,4,6,8,\cdots$$$ (The variable n in code is actually $$$m$$$)
https://oeis.org/A000982 a(n) = ceil(((n)^2)/2)
https://oeis.org/A001752 Expansion of 1/((1+x)*(1-x)^5)
wasn't on oeis
https://oeis.org/A001780 Expansion of 1/((1+x)*(1-x)^9)
Then I checked for n=6,10,12 [here](https://www.wolframalpha.com/widget/widgetPopup.jsp?p=v&id=f9476968629e1163bd4a3ba839d60925&title=Taylor%20Series&theme=blue&i0=1%2F((1%2Bx)*(1-x)%5E11)&i1=x&i2=0&i3=10&podSelect=&showAssumptions=1&showWarnings=1)
I had >40 mins when I found the formula, but me being a nub green couldn't implement it, and my teammates also lost hope on trying further problems as we were quite satisfied with the progress so far.
It was quite frustrating not being able to implement it despite knowing the answer.
Ah, I wanted to know if we could get the formula using generating functions and then solve using FFT. I'm not sure as I don't know much about this topic.
But what you have done is still impressive :)
Amritapuri meetup when
How to solve Tree regression?
It can be proven that it is always optimal to choose the Path as the longest path from among the vertices of the set. (Try to prove by contradiction, it is quite simple)
So the problem boils down to finding the longest path in a given subset of the tree. For this, we used a concept called auxiliary tree (which is basically, making a tree which contains all the vertices of a subset of the tree along with some more vertices to make sure all the LCAs are present in the auxiliary tree). The size of such auxiliary tree is never more than twice the size of the subset of the tree. The weights of the edges of this auxiliary tree is the original distance between the 2 points in the original tree. Thus we can simply find the longest path using 2dfs method.
However, solving each query in MlogN gave us TLE, and we had to use O(1) per query LCA, that was quite strange in my opinion, we lost rank 1 due to those penalties :(
Edit: Refer to radoslav's video on Auxiliary Trees
Thankyou
Where and when will we get updates regarding regionals, qualified teams etc?
We will publish it on CodeDrills Discuss and contest pages. Regionals would also publish it on their sites.
Any idea on how to solve Integer Median Probability (G)?
When $$$N$$$ is odd then the answer is 1. Now if $$$N$$$ is even then the middle two elements in the array(sorted order) must have the same parity. Consider the number of selections where the smaller middle element is $$$i$$$ and the larger middle element is $$$j$$$ with $$$i < j$$$ (We will have to handle $$$i = j$$$ separately). We have to chose $$$\frac{n}{2}$$$ elements from $$$[1,i]$$$ and $$$\frac{n}{2}$$$ elements from $$$[j,m]$$$ with at least one $$$i$$$ and one $$$j$$$ respectively. Number of ways for $$$[1,i]$$$ are $$$i^\frac{n}{2} - (i-1)^\frac{n}{2}$$$ and for $$$[j,m]$$$ it is $$$(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}$$$. Also you have to arrange them in the array so pick $$$\frac{n}{2}$$$ places for the smaller elements.
Your answer is now $$$\sum_{i < j,\; j-i\; is\; even} \binom{n}{\frac{n}{2}}[i^\frac{n}{2} - (i-1)^\frac{n}{2}] \cdot [(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}]$$$ plus the number of arrays where both middle elements are equal.
To find arrays with middle elements equal, just subtract all arrays where middle elements are unequal from the total number of possible selections. To find the number of arrays where middle elements are unequal, you need to compute the above expression for all $$$i < j$$$.
When are the results getting announced?
By EOD according to this message on the telegram group.
Thanks for the information and what telegram group is this
Codedrills community link :- https://t.me/codedrills
Kanpur has announced their results. You can check through the following link:- http://kanpur.indiaicpc.in/?page_id=698
Gwalior has announced their results. Link:- https://docs.google.com/spreadsheets/d/1sPxbLjSGQ1oYnvMdSWeaH-5EZuCJSbfKe8ijPXT0Hzc/edit?usp=sharing
Amritapuri results link :- https://docs.google.com/spreadsheets/u/0/d/1Em1o9QT6iWvjNcDSFdXD9yc4SqIuuWzTeXKrkkr4Sug/htmlview#gid=0