### i4018's blog

By i4018, history, 3 years ago, ,

The second USACO contest of the 2016-2017 season has started and will end on Jan 16 at 23:59 UTC-12 time.
Let's discuss the problems here after the contest :)

• +93

 » 3 years ago, # |   +25 Bringing it back to recent actions
 » 3 years ago, # | ← Rev. 3 →   0 Is it possible that I submit my solution even thought I have already competed for 4 hours? Of course this submission will be out of competition.
•  » » 3 years ago, # ^ |   +8 Contest has ended. No further submissions allowed. This sounds convincing, I think. You will be able, but after the contest ends for everyone.
•  » » » 3 years ago, # ^ |   0 OK, thank you.
 » 3 years ago, # |   0 How to solve "Building a Tall Barn" and "Subsequence Reversal" from Platinum?
•  » » 3 years ago, # ^ |   +3 Wait until 16:00 UTC today when the contest ends for everyone.
•  » » » 3 years ago, # ^ |   0 Really sorry. I thought contest has already ended since it marked ended in clist.by.
•  » » » » 3 years ago, # ^ |   0 This is something repeated every contest... opened an issue for it there.
•  » » » » » 3 years ago, # ^ |   +21 Fixed.
•  » » » » 3 years ago, # ^ |   0 Its still on for me, I got 10 minutes left :P Got AC on problems 1 and 2 only :/
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 I was trying this for the third one (couldn't debug in time, ended up with 6/10): note that instead of saying "reverse a subsequence", you could say "select a bunch of pairs of indices such that for any two pairs one of them is contained within the other and swap the values of each pair". Now let DP(l, r, p, q) denote the answer of the subarray (l, r) given that the lis lies within the range (p, q). From (l, r) you can go to either (l+1, r), (l, r-1), (l+1, r-1), or swap a[l] and a[r] and then go to (l+1, r-1).Did anyone get ac with this approach?
•  » » » 3 years ago, # ^ |   +5 Yes, I did. You can calculate each state in either O(n^2), O(n), or O(1). Anything faster than O(n^2) works, but I did it in O(1). Also, I did it recursively, and I'm sure than a huge number of states were never reached in the computation.
•  » » » » 3 years ago, # ^ |   0 I did it in O(n^2) and get full score. Less than 1 sec in max test. How did you manage to compute the dp in O(1)?
•  » » » » » 3 years ago, # ^ |   +5 I was computing the transitions in O(1). DP(l, r, p, q) is the maximum of the following values: DP(l, r-1, p, a[r])+1 if a[r] lies in range [p, q] DP(l+1, r, a[l], q)+1 if a[l] lies in range [p, q] DP(l+1, r-1, a[l], a[r]) + 2 if p<=a[l]<=a[r]<=q DP(l+1, r-1, a[r], a[l])+2 if p<=a[r]<=a[l]<=q
•  » » » » » » 3 years ago, # ^ |   0 Yup, I basically did it like this too.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 You've forgotten about the two cases where we do swap the values a[l] and a[r], but only use one of them in the sequence, e.g.: DP(l+1, r-1, p, a[l])+1 if a[l] lies in the range [p, q] DP(l+1, r-1, a[r], q)+1 if a[r] lies in the range [p, q] An example of such a sequence would be 3 1 2 100 4 5 6 7 8. Swapping the 3 and the 100 will give you an optimal sequence of length 8.
 » 3 years ago, # | ← Rev. 7 →   +6 How did you solve 2 (platinum). I did this with n ternary searches inside the binary but it TLE, because it was . After some thinking I removed the ternary and replaced it with a derivative so the final solution became . It passed but I wasted like 2.5 hours on this. So my question is. Is there an easier solution (or actually what is the easy solution)?PS: sorry for the early post
•  » » 3 years ago, # ^ |   0 It is not over. Please delete the comment. Around 40 minutes remain(if I am not wrong).
•  » » 3 years ago, # ^ |   +10 FFS I WROTE IT JUST ABOVE, 16:00 UTC, DO YOU NOT HAVE A CLOCK ONLINE?!!!1!
 » 3 years ago, # | ← Rev. 6 →   +34 My solutions, short: platinum 1HLD trick where I bruteforce over all subtrees of smaller sons and use BIT for the subtree of the largest sons. It needs one more precomputational pass where I don't use the BITs, but figure out which numbers will be in them so that I could compress them. .code platinum 2In real numbers, with the constraint has a minimum at . I thought it would be sufficient to use this as an estimate (take the lower bound, but at least 1 cow) and then greedily add a remaining  ≤ N cows in order to minimise the time.I failed the last test case only... so I added a better greedy where I look at the smallest time I can lose by removing 1 cow, the largest time I can gain when adding 1 cow somewhere, and as long as more is gained than lose, remove and add a cow accordingly. It can be implemented with a set<>; if there are T such remove/add steps, the time complexity is .code platinum 3DP over subarrays with states (start, end, max. number on the left, min. number on the right). O(N4).codeUPD: I see a lot of downvotes. CF comments as usual.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 They are probably because your spoilers were empty until a couple of minutes ago. I like your solutions, but don't understand what you're saying about the first problem. Why would you need anything that has anything to do with HLD? My solution was with the "merging sets" trick, but a set can't answer a query "how many numbers are there smaller than x" so I essentially made n segment trees and for each vertex merged the segment trees of its children.EDIT: removed second solution, I got something wrong;
•  » » » 3 years ago, # ^ |   +8 Lol why would I post solution when the contest was running? :D And I did say "short". Very, very short. But I got a lot of downvotes after they weren't empty.I call it HLD trick because you're basically building BITs over HLD, although not building or using the HLD paths directly. You can do the same with segtrees and with BITs, but you need to build them first, in that precomputation pass, and then, you can merge only the elements from the trees for the smaller sons into the largest one.
•  » » » » 3 years ago, # ^ |   0 Okay, I get it now, thank you. :)We basically did the same thing, but I didn't precompute these paths. Instead every vertex chose its biggest child's tree as its own, and merged all the other seg-trees into it.
•  » » 3 years ago, # ^ |   0 After flattening the tree, problem 1 can be solved with a merge sort tree. We keep a vector in each node of a segment tree that contains the relevant range sorted. For querying, we can binary search in current node to find the count of numbers greater than some x. Space and time .
•  » » 3 years ago, # ^ |   0 I realized that if k was small, the greedy algorithm above did not work. So if k <= 10^7, I set all b[i] = 1, otherwise I did the above algorithm, and it got AC.
•  » » 3 years ago, # ^ |   +11 Problem 1 can be solved much simpler in O(NlogN). Do a DFS and store the preorder of each node, then every subtree will be contained in a contiguous range. Now the answer for a node i will be the number of elements greater than Pi in the range [lefti, righti], where lefti and righti are the in and out times of the preorder traversal for node i. Process the nodes in reverse order of Pi and maintain a list of nodes already processed. After processing a node, we add 1 to position lefti. Queries can be done fast with a BIT. Here's source code#include #define all(x) x.begin(), x.end() #define f(i,a,b) for(int i = (a); i <= (b); i++) #define fd(i,a,b) for(int i = (a); i >= (b); i--) #define pb push_back #define pii pair using namespace std; ifstream fin("promote.in"); ofstream fout("promote.out"); struct Node { int index, left, right, value; Node(int _index, int _left, int _right, int _value) : index(_index), left(_left), right(_right), value(_value) {}; friend bool operator < (Node n1, Node n2) { return n1.value > n2.value; } }; int P[100005], Ans[100005], T[100005], N, Ord; vector E[100005]; vector Nodes; void dfs(int n) { int l = ++Ord; for(int v : E[n]) dfs(v); Nodes.pb(Node(n,l,Ord,P[n])); } void update(int x) { while(x <= 100000) { T[x]++; x += x&-x; } } int query(int x) { int ret = 0; while(x) { ret += T[x]; x -= x&-x; } return ret; } int main() { fin >> N; f(i,1,N) fin >> P[i]; f(i,2,N) { int p; fin >> p; E[p].pb(i); } dfs(1); sort(all(Nodes)); for(Node n : Nodes) { Ans[n.index] = query(n.right) - query(n.left-1); update(n.left); } f(i,1,N) fout << Ans[i] << "\n"; } 
•  » » » 3 years ago, # ^ |   0 Yeah, good point. What I wrote was just the first thing that came into my mind.
•  » » » » 3 years ago, # ^ |   0 please, be careful in future for telling these "first things"
 » 3 years ago, # | ← Rev. 3 →   +25 For tallbarn, you're given a sequence a and asked to minimize the sum subject to . Suppose . We have a lower bound from a consequence of Cauchy-Schwarz inequality, mostly known as Titu's lemma (I wrote an article here) $o$ with equality when for some constant t. But implies . So we can set and achieve the minimum value . But bi values have to be positive integers, so the sequence b has to be adjusted. First off we should make all bi < 1 equal to 1. At this step I greedily adjusted the sequence in two ways and took the minimum. Firstly I replaced bi with ⌊ bi⌋ for all i. Then the new total sum is less than k and the target value has increased. We can add the extra values in a way that the sum will be minimized. If we add 1 to bj for some j then the sum decreases by . so pairs (ai, bi) get priority based on this value. We can add all pairs in a priority queue, keep increasing top elements and push them again till again. Secondly, I replaced bi with ⌈ bi⌉ for all i and did something similar to above. This time the sum will be greater than k and we can delete extra values keeping another priority queue.Finally take the minimum from these two adjustments.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -12 .
•  » » 3 years ago, # ^ |   +5 Actually, in reals, with the constraint has its minimum at from Lagrange multipliers (or simply taking derivatives when all but two variables are fixed).
 » 3 years ago, # |   +16 I use Simulated Annealing method on third task and get OK :)
•  » » 3 years ago, # ^ |   0 How does it work here?
•  » » » 3 years ago, # ^ |   +6
•  » » 3 years ago, # ^ |   +5 I like your idea, you didn't bother in implement lis in O(nlogn) :) Nice approach. +1
•  » » 3 years ago, # ^ |   0 Can you explain your method in a bit more detail? I haven't heard of simulated annealing, and would like to learn more about it.Also, what sorts of problems does one use simulated annealing on?
•  » » » 3 years ago, # ^ |   0 when n is small and you need to minimaze/maximaze some function you can use Simulated Annealing method. like this task i know only where to read about this method in russian, sorry:( i think you can google it and find some information about it.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you give the link of that russsian article?
•  » » » » » 3 years ago, # ^ |   +8
 » 3 years ago, # | ← Rev. 2 →   +25 In P2, you can solve with binary search.Define f(x, i) to be the time you can cut off if room i currently has x cows, and you place one more. Then . You can binary search D such that all rooms have f(x,i)<=D, which you can solve with some quadratic formulas. Complexity is O(n log K)
•  » » 3 years ago, # ^ |   +3 Your LaTeX is slightly messed up.Anyways, what I really wanted to say, your username is really nice, especially appropriate for the tree problem you proposed P1 for the USACO contest. (Is it you?)BTW, to whom you send nodes?
•  » » » 3 years ago, # ^ |   -6 No, that guy is some doppelganger who wants to take my name. Really, i am just some poor guy who just sends nodes, particularly segtree ones because low cost :)
•  » » 3 years ago, # ^ |   0 How do you make sure the sum of the x's is equal to K?
•  » » » 3 years ago, # ^ |   0 That's the transition of the binary search: if sum of x's is more than K, try higher differences, else try lower differences.
 » 3 years ago, # |   +17 If I'm not mistaken I've achieved in Platinum 1.First, I compressed values in interval {1, ...N}. Then, put all nodes with their discovery time and finish time in one array, along with values of nodes, and sorted them by position. Finally, by iterating through that array and updating BIT, made solution for every node.Code.
 » 3 years ago, # | ← Rev. 2 →   0 Does this work for platinum 1st problem? Firstly build eulerian tour over tree. Now sort cows by p. Answer for cow v is (sum on segment [l[v], r[v]]) / 2, and after that add position l[v] and r[v] 1.
 » 3 years ago, # |   0 Is there any way to submit now? I optimised P2 a bit but time was up!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 After the results are published, problems are moved to practice.
 » 3 years ago, # |   +5 Where can I find problems? http://usaco.org/index.php?page=contests have only problems till first contest