Hello Everyone,
We gladly invite everyone to participate in Alkhwarizm organized as a part of annual Techfest of IIIT Allahabad–Aparoksha 2016.
The problem setters and tester are Xsquare, hagu, Divanshu, m17, dragonslayerx, ayush_awasthi. The problem setters have tried to bring many interesting problems for everybody this time.
The contest starts at 9:00PM (IST) on 3rd April, 2016. Check you local timezone here. It is an individual contest with 5 hours duration.
The Total Prize at stake is Rs. 50,000. For Indian Winners distribution is Rs 20,000, 15,000 and 10,000 for 1st, 2nd and 3rd rank respectively. Also CodeChef will provide goodies to International Winners.
The Registration Link for the prizes is here. Click here to Register
The Problem Set will consist of 10 Problems for various topics of Competitive Programming. It has problems of various difficulty levels and diverse fields so we hope everyone will find something of his taste. Editorials to all problems will be provided as soon as the contest ends. Follow the event page for more updates.
Link to Facebook Event — Event Page
Link to Contest — https://www.codechef.com/ALKH2016
Happy Coding!!!
Auto comment: topic has been updated by dragonslayerx (previous revision, new revision, compare).
Will there be prizes for Non-Indian Winners too?
Lots of exciting Codechef goodies including Tshirts and Pendrives to be given to Top 3 Non-Indian participants.
Update: The contest is going to start in 1 hr 30 minutes. Get ready :)
How to solve this problem : https://www.codechef.com/ALKH2016/problems/NRTKH
The trick when we have something like 2 * f(a) = 3 * f(b) is to give a value to those letters, so if we make a = -2, b = 3, c = 0, we need to count the ranges [L, R] which sum up to 0 (forgetting, for now the condition that the range must have an a or b).
Let's make an array pref[], pref[x] = sum [0..X], that is, the sum of values till index X. Now, if we have two different indices i, j, such that pref[i] = pref[j] this means we have found a range which we must count.
Let's loop from the begin to the end of array. We are at index i now and will count how many ranges are valid that end in i, which is just the count of values that have same pref[i]. This can be done in O(nlogn) using a map in C++, for instance.
So the only thing left is to discard ranges that only contain 'c'. Notice that this ranges are summed up in our final answer when we have a contiguous range of c.
Here is my implmentation
http://pastebin.com/7EbT1fHF
@ivanilos Thanks a lot for your explanation and code :D
@ivanilos I have read your code but I am not able to understand how you are dealing with 'c'. Please describe it in detail.
Did you get that the extra counting is because of contiguous 'c'? If so, notice that when looping through a string of 'c' when we are at the first 'c' there is only one string (that only has 'c') ending at this position. When we are the second position, there are two strings ending at this position, namely, "c", "cc", so that's why I increment the variable seg and subtract it from the result (it may change whether you increment seg before or after decreasing depending or your implementation, but that's the ideia).
You may see that, in the end, what I am doing is just subtract all possible substrings of a contiguous range of 'c' — if it has len N it will have
substrings
Where is editorial
Update: the editorials have been updated. Please check them at the following link. https://tp-iiita.quora.com/Editorials-of-Alkhwarizm-2016