Greetings Codeforces community!
You all are invited to participate in CodeChef’s April Cook-Off sponsored by ShareChat. This is a short contest with 7 problems on offer. The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.
ShareChat — our contest sponsor is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Setters: T1duS (Udit Sanghi), Farhod (Farhod Khakimiyon), Kerim.K (Kerim Kochekov)
- Tester: teja349 (Teja Vardhan Reddy)
- Editorialist: adamant (Alexander Kulkov)
- Statement Verifier: Xellos (Jakub Safin)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
Contest Details:
- Start Date & Time: 21st April 2019 (2130 hrs) to 22nd April 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Contest link: https://www.codechef.com/COOK105
- 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://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)
Good Luck!
Hope to see you participating!!
Happy Programming!!
Nice and balanced problemset for Div 2. How to solve Random Game and Doubly Increasing Path ?
Random Game- If n%2 == 0: n /= 2,if n%4 == 3 or n == 1: n -- else n++
You can prove this by induction. My code —
https://www.codechef.com/viewsolution/24063596
DINCPATH- In edge u-v, if a[u]>a[v]: make it edge u->v with weight a[u]-a[v] and vice versa.
Sort all the edges. Now, you can use DP[i] = max length of path ending at .
My code
https://www.codechef.com/viewsolution/24063652
For hooli and Pied piper question, i was storing all the possible contributions values in a vector and then sorting the vector and doing binary search on the cumulative sum vector to find how many contributers we need. But this gave TLE. The storing part's time complexity is N*log(10^9). And sorting vector of above size again Nlogn. Where did i go wrong? And, if we simulate the problem using priority queue what will be the time complexity?
knighthood I got AC using priority queues.
I also used priority queues when i was getting TLE using array of Ci. But then it gave WA xD look at my code pls https://www.codechef.com/viewsolution/24061341
You are using sort(c , c+n) in while loop. Suppose ci for all i in 109 then your code's complexity will be 30*n*nlon(n) = n2log(n).
I hope you get it why it is getting TLE
sorry bro wrong code. The code is — https://www.codechef.com/viewsolution/24070549
I didn't go in deeper but Try out that case --
1
2 10 10 10 10 10
10 10
it should be "RIP" but your codes gives 0.
The constraints explicitly specify $$$A, B < Z$$$. So your Test Case is wrong!
I used a heap created by make_heap() The complexity is N*logn*log(10^9). In my understanding the heap operation is faster than the sorting of the array. implementation
If you have a test where $$$N = 10^5$$$ and every $$$C_i = 10^9$$$, then you have $$$O(NlogC)$$$ contribution values, which is around 30 million. That's not a very friendly array size to be sorting.
The question is: Is the sorting of that array slower than the 30 million insert/delete from the heap? I think it is, because the heap holds not more than N values at any time. Which means that the sorting is N log (N * 10^9). So, the array sorting is in worst case aprox 9 times slower.
Thank you :)
I am making an unweighted DAG from the edges and DP[i][f] denotes the longest length of sequence staring at ith node and includes the parent of ith node if f = 1 otherwise if f = 0 it does not include the parent of ith node. Can you please tell why my solution is wrong? My code
Use long long maybe
I have converted int to long long using typedef already.
hackerwizard I don't think there will be only one parent of a node. There can be multiple parent nodes. And you will be needing all those values. I applied the same idea, First, make DAG, apply topological sorting, Iterate over all nodes in it, store the values of dp for all parent and then applying binary search and using prefix max, find the value for current children of a node. Refer to here : Solution
Thanks
There can be multiple parents as well as multiple children, using dp on edges makes it much easier.
Thanks
Why does this TLE, (for DINCPATH), my soln's complexity is O((n + m)logN) .
Time complexity for this problem is a bit strict IMHO. I had to get rid of the TreeMap to get it passed in the contest. You can check my submission.
any hints on how to solve mystery tree ?
Disclaimer: I didn't solve it during the contest, I had bugs with the third problem and wasted almost 2 hour only on it D:
Solution: It's a centroid problem.
Insight 1: If a node is the largest in his neighborhood he is good for you. Insight 2: After querying some node, let's say U, and receiving the verdict that he has a bad neighbor (which is bigger then him), let's say V, then in the subtree of V and all his children (except U), the there exist some "good" node (the maximal one for example). Explanation for the insight: The worst case is that all node in the subtree have some neighbor which is bigger than them, but as we know that U is smaller then V, this mean that the maximum value in the subtree of V is also bigger then U, and this mean that he is bigger then all his neighbor, which mean he is "good".
As such the algorithm is as follow: find some node in the graph, such that all his children's subtree's size are smaller then n/2. After querying him, you will either find that he is good — you win, or you might find some neighbor of his which is bigger: which mean that you can start looking only at the subtree of this node, which you know from insight 2 that contain a valid "good" node.
As such for each step you get the size of the graph reduced by half, and by that you get that after 20 queries the size of the graph either turn 1 (which mean the node that remain is our solution), or you found along the way a good node.
for some good explanation of the centroid method, you can read here: https://www.geeksforgeeks.org/centroid-decomposition-of-tree/
Hope this helps :)
Thank You!