Hello Codeforces!
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.
So be ready to have a nail-biting experience on February 17, 2018 at 21:00 IST
Register right now at the link given here to be eligible for prize money.
The problems have been set by me (shivamg_isc) and tested by Shiv Dhingra (lucifer2709).
Facebook Page — CodeRed Facebook Page
Some of our previous contests — Alkhwarizm 2017 and HumbleFool Cup 2016.
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 — mexmans, 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.
KRYP1It 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.
KRYP2Was 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.
KRYP3The 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.
KRYP4The answer is the summation of for all distinct values present in the list provided, where X is the frequency of the value.
KRYP5The 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.
KRYP6We 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
shivamg_isc for KRYP1 i was doing the same thing Dp But it consistently give wrong answer. Can u please tell where i am going wrong? https://www.codechef.com/viewsolution/17463680
Hi tarun_.
In 2nd dfs, you took the max value from the siblings only. What if the maximum value could have been obtained from above the parent side I.e from the ancestors or from any ancestors' siblings. In case you still have any doubt regarding this, I will post an example :)
i know topics like dp,graphs and solved some example, in this contest i was able to solve 2 problems only. i read the hints you wrote here, but i am almost new to every topic you wrote.Hope full editorial will help . Thanks for good contest
Thanks a lot for your feedback learner_321.
Don't worry. The full editorial will be posted tomorrow.
I will notify once it will be posted :D
Editorials are posted. Check out the blog for the link.
Hi. I am continuously getting TLE for Mo's on Tree. Can you help someway? Click
I would suggest you to use Segment Tree. The solutions using Seg Tree are consuming way lesser time than those of multiset/map. It seems that overhead in multiset/map is very high, and hence there is so much difference in time of the accepted solutions. Maybe there is a good deal of optimization required wih multiset/map. Refer to my solution. It takes 3.9 sec with multiset.
When will we get list of the shortlisted teams?