Hello Codeforces!
I would like to invite you to participate in HackerEarth October Circuits. It's a long contest that will start on October 14, 21:00 IST. Contest will run for 8 days.
The problem set consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.
Xsquare, rivudas and I are the testers of the problem set you'll have to work on — thanks to satyaki3794, gamer12, harshil, tanmayc25 and PrinceOfPersia for preparing these tasks.
The contest will be rated. There will be some cool prizes for the top 5 competitors:
1. $100 Amazon gift card + HE t-shirt.
2. $75 Amazon gift card + HE t-shirt.
3. $50 Amazon gift card + HE t-shirt.
4. HE t-shirt.
5. HE t-shirt.
Update the post with the correct date i.e. 14th October. Currently, it shows June 18.
Thanks!
The approximation problem was quite interesting. It's a pity that it was again possible to obtain what appears to be the optimal solution in all testcases (again after Aug16). Somewhat harder tescases would have made it more interesting. On the other hand a higher value of N would have made creation of the testcase quite time-consuming,
you were great, can you please explain in-general the method you use?, or give us some resources from where we can learn such solutions?? this was my first time I solve such things, I made some sorts and bruteforce on the few first values, but I can't get more than 97.351
How'd you even get 97.351. My brute force got ~90 pts T_T 97.351 is just what I needed for a T-shirt lol
I didn't use anything fancy. I searched locally (multiple restarts of hill climbing with random initial state) for fixed c using neighborhoods of at most 3 room flips while conserving the number of inversions. For relatively few values of c this works fine (discarding values of c which don't yield good result). To get an initial set of c's which look promising, I experimented with different heuristics. The one that turned out best was to compute a greedy solution for all values of c, neglecting the inversion constraint. The best solution was (as far as I tested) always under the top 30 values computed that way.
One thing thing I thought about for quite some time but didin't come up with a really good solution was the following: Given c and n find a random (uniformly distributed) n-element binary vector (representing the set of rooms) with exactly c inversions. I came up with some ugly algorithm behaving quite well for 0<<c<<n*(n-1)/4, but it wasn't really satisfying. Does anyone know an O(n) algorithm for this?
Can someone post the general approaches to solve the problems. There isn't a complete editorial. Thanks.
I'll post the brief ideas of solutions for the non-approximation problems :
Brute Force all possiblities. An O(n5) solution would work.
Key observation is that most triplets will return 0 with that quotient. So, you're left with a few possibilities and you can check them all.
Flatten the tree. Store the weights of each depth in a respective vector. Calculate prefix sum of the vectors. Each query is the sum of a range in the vector which can be found by binary search.
This can be done by Dinic. It is quite easy to reduce it to a max bipartite matching problem and we can translate this to max flow and use Dinic to solve this in
by Karzanov's Theorem.
Idea is to calculate dp[i] = number of vertices j where dist[j] + w(j, i) = dist[i] while doing Dijkstra. Then, multiply all dp[i].
We can actually calculate the cost where u is chosen as root for all possible u using tree dp. Think of what happens when the root moves from a parent to its child.
Use square root decomposition (you can see the editorial here.)
Hey, Could you please elaborate on the solution for 6th one. The tree dp. Thanks.
1.Root the tree somewhere and do a dfs(or maybe a couple more) to find the f,g and C values at each node. Let these values be stored in arrays f[],g[] and C[].
2.This gives you the C values for all nodes but considers only members of the subtree for that particular node (This also means that we have answer for the root directly as C[root]).
3.Now when we move from the root to its child, we see that all nodes which are not a part of this node's subtree are at a distance D+1 (if they were at D from the parent).
4.Let x[child] = C[parent]-C[child]-f[child]-g[child]. We can convince ourselves that this would be the C value of parent had the whole subtree corresponding to the child been missing.
5.Let y[child] = f[parent]-f[child]-g[child]. Again an argument similar to above point can be given.Justification for finding x and y follows...
6.We notice that contribution of a node at a distance D from root to its f value is D+1 and to its C value is ((D+1)*(D+2))/2.
7.So if the contribution of a node w (in subtree of parent and not in that of child) was initially(for parent) (D+1)*(D+2)/2, now (for child), it will be (D+2)*(D+3)/2.
8.We see that if to y[child], we add the sum of all nodes outside child's subtree,we will have each each outward node(located in parent's subtree , not in child's) D+2 times where D was distance of that node from parent.
9.now if we add this to x[child] we have a particular outward node [(D+2)+(D+1)*(D+2)/2 = (D+2)*(D+3)/2] times as desired earlier.
10.In this way we can make transitions from parent to child in constant time after an initial O(No of nodes). Please also notice that x and y values after being calculated for a node should be passed to their children in turn. Just add the newly found x[child] to C[child] to get the actual value of C if we root the tree at child.
11.See picture attached for clarification of point 10. Have a nice day!
Image Link
Solution Link
Is the current leaderboard final or not ??? Do the second 50-tests in the approximate problem tested or not yet ???
I'm pretty sure there was no rejudge, yet. I expect they will update this comment with status updates: www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/approximate/unforgettable-mission/?scroll-id=comments-174-801&scroll-trigger=inview#c73985
Another way of checking is to open one of the submissions and click on the inputs — you can see the current test cases (e.g. input #50 for the original set is: 99 394073632). Until you see different tests when clicking on your submissions, then the rejudge didn't take place, yet.