Aparoksha presents to you an all-new flagship event CodeRed in association with ACM.
If you have the appetite for algorithmic problem solving, then don't miss it out!
It will be a 5-hour long team event with a maximum size of the team being 3 members.
The preliminary round will be held on Codechef, and the onsite round will be held during Aparoksha.
The total prize money is worth INR 50,000. The best 40 teams will make it to the onsite round.
Also, top 2 teams in the online round will get INR 3000 and 2000 respectively, along with Codechef Laddus.
All teams making it to the onsite round will get CodeRed T-shirts.
Contest link is here — CodeRed 2018
The problem set comprises 6 problems of varying difficulty level.
Great Prizes and Glory await you in the Coding Arena. CODE ON!
Upd 1:- Contest is about to begin in almost 1 hour. Best of luck :)
Upd 2:- The contest is over, and was a great success with about 900 teams registering for the contest.
Thanks for the overwhelming response. :D
Congratulations to the winners :D
- Mutability — uwi
- Twin Prime — jtnydv25, HackerTina
- Accidently in Warsaw — Mex-Mans, YerzhanU
- noticeMeSenpai — satylogin, sarkysaurabh, vaibhav138
- karma — wittyskull, garuna, abhi_1595
Top 2 teams will get cash prizes of INR 3000 and INR 2000 respectively, along with Codechef Laddus. :)
Feedback of the contest in the comments will be highly appreciated :D
The detailed editorials will be published on Monday.
For now, I am posting the hints.
It was based on DP on Tree. For each node, it was required to maintain the best values that can be obtained from rest of the nodes. Two DFS were required- one for calculating answers from descendants, and the other one from ancestors/siblings. Max of both the values will be the answer.
Was based on Mo's on Tree. In order to get the minimum absolute difference of squared values, there were 2 possible solutions. One can be to maintain 2 multisets. The first multiset stores the squared values of the nodes. The second multiset stores the difference between closest/adjacent values in the first multiset. Other was to use Segment Tree. At each node compute the minimum absolute difference of the squared value between its constituent leaf nodes.
The constraints indicate that the problem is to be solved using Matrix Exponentiation. However, the matrix used for matrix exponentiation will have dimensions of (N2, N2), thereby leading to a complexity of O(N6Log(Y)). This will time-out. Proper observation will lead you to the fact that there is symmetry in the distribution of number of ways i.e we do not need N2 points. Owing to symmetry, (N2) / 8 points are sufficient. This reduces the complexity by a great extent.
The answer is the summation of for all distinct values present in the list provided, where X is the frequency of the value.
The fact is that LCS and related stuff was of actually no importance. You can find the LCS anyhow using DP as the total length is just 5000. Based on the LCS values, you need to make an N * M matrix, which will be binary matrix. In this binary matrix, you need to find out how many squares of following form exist?
This square will have 1's on all of its borders as well as on the 45-degree diagonal. Other elements can be 0/1.
This can be solved using careful implementation of DP and then Merge Sort Tree or Square Root Decomposition.
We can maintain a sorted set of numbers by iterating over the array. We can simply use lower_bound in C++ or equivalent in other languages.
set<long long>::iterator it = s.lower_bound(val); it--; return (*it);
Upd 3:- Editorials are finally posted. :) Click Here