Hello CodeForces Community!
Gear up this October and accelerate your programming minds for this month's Mega Cook-Off. This is the last mega warm up which will help you win the final race in the upcoming ACM ICPC 2018. So hurry up, note down the details and be there. Joining me on the problem setting panel are:
- Problem Setters and Editorialists: SAeed (Saeed Sryhini) & Mhammad1 (Mohammad Shahhoud)
- Problem Tester: kingofnumbers (Hasan Jaddouh)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
Note: Top 25 Indian students will be eligible for ACM ICPC regional travel reimbursement. Each of them shall be reimbursed an amount of upto INR 1500 upon producing the travel bills. For more details visit: https://www.codechef.com/icpc/2018.
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.
Contest Details:
Time: 22nd October 2017 (2130 hrs) to 23rd October 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/COOK87
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes:
- Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])
Good Luck! Hope to see you participating!!
It's great to see a contest prepared by my teammates. I think it will be awesome :D
How to solve Chef and Dancing Steps?
For each index i, find the rightmost index j such that XOR(j...i) >= m. You can do it by inserting prefix XORs into a trie and processing from left to right.
Now the problem reduces to -
For a given subarray [L, R], find the minimum value of i-rightmost[i]+1, such that rightmost[i] >= L. This can be done offline using segment tree or online using persistent segtree.
Code
First assign
. Now a query [qL;qR] becomes:
Find such i and j (qL - 1 ≤ i < j ≤ qR) such that
and j - i is minimum.
Well for every position i we will find the closest position Li to its left, such that
. This can be done with a trie in 
time. We notice that for every query we are interested in only such pairs (Li, i).
Well now the query [qL;qR] becomes:
Find the minimum i - Li, such that qL ≤ Li and i ≤ qR. This is a well known problem which can be solved offline in
time. Lets consider all queries and pairs (Li, i) as events. We sort all events by their right end and start iterating them from left to right. We will have a segment tree for minimum. Now if the current event is an update (one of the (Li, i) pairs), we update position Li with i - Li. If the event is a query, the answer will be the minimum in [qL - 1;qR].
There is also another online solution using binary search on the answer. The complexity after the trie part will be
using a segment tree or 
using a sparse table.
I got the idea for this question but I was unable to implement the trie properly?? Can you tell me how to find the largest Li using trie ??
Maintain a max_index property for each node of the trie, which stores the maximum index of the array whose value was inserted into the trie and whose leaf is in this subtree. Now, suppose you want to find max index for given value val. Iterate through the bits from MSB to LSB.
If ith bit of val is 0 and ith bit of M is 1, go along direction 1.
If ith bit of val is 0 and ith bit of M is 0, compare global ans with max_index of 1-subtree and go along direction 0.
If ith bit of val is 1 and ith bit of M is 1, go along direction 0.
If ith bit of val is 1 and ith bit of M is 0, compare global ans with max_index of 0-subtree and go along direction 1.
You can see the code I linked in my comment above for this.
Thanks. I understood.
We're coming, We're back... Next Year. :P
Nice problems :)
Thanks. Hope to see ACM back... Next Year :P
Thanks for making me lose my job with that problem...
No, I'll give you another chance, but don't study again at work xD
You didn't lose your job. We gave you a fair chance. Actually 4 people managed to use that chance and got the problem accepted xD.
For Chef and Dancing Steps, can someone please point out a mistake in this algorithm-- Calculate the latest index i for each array index j such a(i)^a(i+1)...a(j) >=M Answer the queries offline, while moving left to right in the array, update at index last[i], the value i-last[i]+1. For each query ending at r, calculate the minimum value in the range(l,r) and that is the answer for that query.
I could not find any mistake in my solution. Any help would be really appreciated Code
UPD: Found the bug.One of the array size was 1e6 instead of 1e7
How to solve 5th problem?
Centroid decomposition
If you subtract the mean Y from all values of the array, you need to count the number of paths such that the sum of new values on the path is >= 0 and the number of values <= X on the path is <= (L+1)/2 where L is length of the path.
I could not finish coding this on time during contest. After I submit in practice, I will link the code here for reference.
Now i finished to code last problem. Here is my code. Now i tested with random samples, unfortunately my code works in 4sec (the problem's time limit is 3sec). My solution uses Centroid Decomposition with Fenwick and Ordered set. How can i optimize my code? I used Fenwick and Ordered set to find the number of pairs(C,D) bigger than another pair (A,B) such that C>=A and D>=B. Can i use another data structure to decrease time?
What's your code complexity?
The intended complexity is: O(N.Log2(N))
About N * log3(N).
It will not pass the TL, you have to improve more, see satyaki3794 comment.
Ordered set has a very high constant factor. Why do you need ordered set? Just sort the given points in increasing order of sum of new_values. Then process from right to left and use 1-D Fenwick tree to maintain the condition of the count of values <= X. At any point in time, the Fenwick tree only contains those values which already satisfy the "sum" condition for the current index you are processing.
Thanks for your help. Finally got AC, works in 0.46 sec. Here is my submission.
Btw Thanks for contest.
When the rating may get updated? I have participated for the first time.
Search your username here : codechef-rating-predictor.7e14.starter-us-west-2.openshiftapps.com/contest/COOK87/all/
How to sleep at night after your solution gets WA because you missed long long in assigning value to a single variable :/ ?
Nice problems btw :)
Please point out some common silly mistakes that can be made in Chef and Dancing Steps. I got WA during contest, not able to find any error till now.
Code
UPD: nvm, Found it