We invite you to participate in CodeChef’s Starters 156, this Wednesday, 16th October, rated upto 6 stars (i.e. for users with rating < 2500)
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Setter, Contest Admin, and Statement Verifier: Shreyan Dominater069 Ray
Tester: Sushil SmolBrain Raaja
Text Editorialists: Nishank IceKnight1093 Suresh.
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
The following is the number of problems in each division :
- Division 1 : 5 problems
- Division 2 : 7 problems
- Division 3 : 7 problems
- Division 4 : 8 problems
There are no subtasks this time.
Good Luck!
Congratulations to Top 5!
As a tester with a smol brain, I can guarantee that participating in this contest increases your brain size by $$$10$$$%
Contest starts in ~20 Minutes
can you please make someone manage the clarification tab, please?
hey, sorry for that, i apologize for the long delay
I spent 30 mins in contest and solved a variation of D1B (when we want to minimize $$$\Sigma^{n}_{i=1} |B_i-C_i|$$$)...
Consider a difference array $$$d[i] = b[i+1] - b[i]$$$ where $$$1 \leq i \lt n$$$.
For convinence, set $$$d[0]=d[n]=-INF$$$.
You are allowed to perform the following operations on the difference array:
Our goal is to ensure that in the final state: $$$0 \leq d[i] \leq x$$$ for all $$$1 \le i \lt n$$$.
This problem is similar to a "stone-moving" model. For every $$$d[i] \gt x$$$, we greedily move some stones to $$$d[j] \lt x$$$ (choosing the closest one).
Are you sure your solution is correct?
Let's take an example: x = 2, b = 1, 3, 6, 7, 10, 12, 14
You d array will be -INF, 2, 3, 1, 3, 2, 2, -INF
If you process the first 3 first, then closest one is the 1 right to it.
The d array become -INF, 2, 2, 2, 3, 2, 2, -INF.
Then for the other 3, you need to match with the right -INF and takes 3 operations. 4 in total. The final original array is 1, 3, 5, 7, 9, 11, 13
But actually, if you process the second 3 first, it only takes 3 operations in total. The final original array is 2, 4, 6, 8, 10, 12, 14
My bad. Now I think we can use the network flow model to solve it.
Using your example, let's set nodes $$$0$$$ to $$$8$$$, as well as source point $$$S$$$ and sink point $$$T$$$.
For nodes $$$i$$$ and $$$i+1 (0 \le i \lt 8)$$$, add bidirectional edges with infinite capacity between them. Then connect edges $$$S \overset{\text{capacity=1}}{\rightarrow} 2$$$, $$$S \overset{\text{capacity=1}}{\rightarrow} 4$$$, $$$0 \overset{\text{capacity=INF}}{\rightarrow} T$$$, $$$3 \overset{\text{capacity=1}}{\rightarrow} T$$$ and $$$8 \overset{\text{capacity=INF}}{\rightarrow} T$$$. The cost of all edges is $$$1$$$. This allows us to find the MCMF.
You were not supposed to minimize the sum of differences. rather you had to minimize the maximum difference.
How to solve Count Triplets
Imagine that you have two fixed indexes $$$i$$$ and $$$k$$$, such that $$$i \lt k$$$, and you must choose $$$j$$$.
Then we have an $$$O(n^2)$$$ solution, iterate for every pair $$$(i,k)$$$ and add the count of the possible $$$j$$$'s to the answer. For reducing the complexity remember that $$$1\leq a_i \leq 100$$$, so $$$|a_i-a_k| \lt 100$$$. We can iterate with $$$k$$$ being between $$$i-100$$$ and $$$i+100$$$, making the complexity $$$O(200n)$$$.
Hi, The editorialist's PYPY code for problem Count Triplets keeps TLEing when I submit it(it checks 200 options for k). I only check for 100 options for k and mine is consistently getting accepted even though it is sometimes very close to the time limit. Maybe next time, will you consider setting a more relaxed time limit for such problems? I think this is the second time recently that something like this has happened the other one being starters 153-(XSQR problem) where someone could possibly figure out all the interesting ideas of a problem and get TLE because of slightly imperfect implementation. I and many others don't want to not be able to solve problems because of reasons like this in future.
first time i submitted : https://www.codechef.com/viewsolution/1098982208 passes in 1.45 seconds, and the TL is 4s (2x multiplier for pypy i think)
Please do not spread misinformation.
also do note our c++ codes are 0.1-0.2s
Did you know 2x TL used to be standard for quite a long time? and we gave you 10x TL here and you still complain....
I am sorry, by mistake I have been submitting all my solutions in python3 instead of PYPY3 lol. Thanks for helping me figure this out. My solution passes in 0.64 seconds. But My point still stands if I try to submit in python3(Any idea why such huge difference?) but python users should always use pypy, so I guess its fine.
pypy use JIT (Just-in-Time) compilation, so I guess it is faster. In general pypy performs well with a large number of arithmetic operations.
My alternative, simpler solution for the MAGNET problem:
First, find a chain of length 4 (let's assume it's 1-2-3-4). We only track M1 and M2. Perform the operations in the order 3, 4, 2, 1. After that, use node 1 as the root and perform the operations in non-decreasing order of depth. We can see M1 and M2 will never be merged.
Submission
My alternative, more complicated solution for the MAGNET problem :
Root at centroid, alternate between different subtrees, way of arranging elements exists because all sizes <= n / 2. Insert the centroid after the 1st element (otherwise you run into issues on very small depth graphs). Drawing and visualizing can help understand why it works
My solution was pretty similar but simpler. Print all nodes in BFS order from the centroid. Resolve ties between nodes that have the same distance from centroid using their subtree sizes. That is root at centroid and if two nodes are equidistant, then print the one with lower subtree size first.
Here's the sub : https://www.codechef.com/viewsolution/1098937685
My solution for the MAGNET problem: For trees with diameter less than 3, traversal is not possible. Otherwise take any leaf node (1) and pick the node adjacent to it (2). Now do a dfs traversal from node (2) pushing all the visited nodes in order of visiting, except node (1) and node (2). At the end, push (1) and (2) to the result. It can be shown that the magnets initially at node (1) and node (2) will always be adjacent.
Submision Link