USACO January Contest 2016-2017

8 years ago, # ^ |

Wait until 16:00 UTC today when the contest ends for everyone.

→ Reply

1000000007

8 years ago, # ^ |

Really sorry. I thought contest has already ended since it marked ended in clist.by.

→ Reply

8 years ago, # ^ |

This is something repeated every contest... opened an issue for it there.

→ Reply

aropan

8 years ago, # ^ |

+21

Fixed.

→ Reply

ista2000

8 years ago, # ^ |

Its still on for me, I got 10 minutes left :P Got AC on problems 1 and 2 only :/

→ Reply

AnonymousBunny

8 years ago, # ^ |

← Rev. 2 →

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?

→ Reply

8 years ago, # ^ |

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.

→ Reply

mnaeraxr

8 years ago, # ^ |

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)?

→ Reply

AnonymousBunny

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

Yup, I basically did it like this too.

→ Reply

TimonKnigge

8 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

radoslav11

8 years ago, # |

← Rev. 7 →

How did you solve 2 (platinum). I did this with n ternary searches inside the binary but it TLE, because it was $\text{[math]}$ . After some thinking I removed the ternary and replaced it with a derivative so the final solution became $\text{[math]}$ . 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)?

code: http://ideone.com/ojPGlI

PS: sorry for the early post

→ Reply

8 years ago, # ^ |

+10

FFS I WROTE IT JUST ABOVE, 16:00 UTC, DO YOU NOT HAVE A CLOCK ONLINE?!!!1!

→ Reply

8 years ago, # |

← Rev. 6 →

+34

My solutions, short:

platinum 1

platinum 2

platinum 3

UPD: I see a lot of downvotes. CF comments as usual.

→ Reply

8 years ago, # ^ |

← Rev. 3 →

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;

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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.

→ Reply

Alpha_Q

8 years ago, # ^ |

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 $\text{[math]}$ and time $\text{[math]}$ .

→ Reply

goodthingstaketime_._

8 years ago, # ^ |

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.

→ Reply

tenshi_kanade

8 years ago, # ^ |

+11

Problem 1 can be solved much simpler in O(N_logN).

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 P_i in the range [left_i, right_i], where left_i and right_i are the in and out times of the preorder traversal for node i.
Process the nodes in reverse order of P_i and maintain a list of nodes already processed. After processing a node, we add 1 to position left_i. Queries can be done fast with a BIT.

Here's source code

#include <bits/stdc++.h>
#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<int,int>

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<int> E[100005];
vector<Node> 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";
}

→ Reply

8 years ago, # ^ |

Yeah, good point. What I wrote was just the first thing that came into my mind.

→ Reply

oversolver

8 years ago, # ^ |

please, be careful in future for telling these "first things"

→ Reply

Alpha_Q

8 years ago, # |

← Rev. 3 →

+25

For tallbarn, you're given a sequence a and asked to minimize the sum $\text{[math]}$ subject to $\text{[math]}$ . Suppose $\text{[math]}$ . We have a lower bound from a consequence of Cauchy-Schwarz inequality, mostly known as Titu's lemma (I wrote an article here)

$\text{[math]}$

$o$ with equality when $\text{[math]}$ for some constant t. But $\text{[math]}$ implies $\text{[math]}$ . So we can set $\text{[math]}$ and achieve the minimum value $\text{[math]}$ . But b_i values have to be positive integers, so the sequence b has to be adjusted. First off we should make all b_i < 1 equal to 1.

At this step I greedily adjusted the sequence in two ways and took the minimum.

Firstly I replaced b_i with ⌊ b_i⌋ for all i. Then the new total sum $\text{[math]}$ 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 b_j for some j then the sum decreases by

. $\text{[math]}$

so pairs (a_i, b_i) get priority based on this value. We can add all pairs in a priority queue, keep increasing top elements and push them again till $\text{[math]}$ again.

Secondly, I replaced b_i with ⌈ b_i⌉ for all i and did something similar to above. This time the sum $\text{[math]}$ will be greater than k and we can delete extra values keeping another priority queue.

Finally take the minimum from these two adjustments.

Code: http://ideone.com/gItN6P

→ Reply

FunTry

8 years ago, # ^ |

← Rev. 2 →

-12

→ Reply

8 years ago, # ^ |

Actually, in reals, $\text{[math]}$ with the constraint $\text{[math]}$ has its minimum at $\text{[math]}$ from Lagrange multipliers (or simply taking derivatives when all but two variables are fixed).

→ Reply

8 years ago, # |

+16

I use Simulated Annealing method on third task and get OK :)

→ Reply

bciobanu

8 years ago, # ^ |

How does it work here?

→ Reply

8 years ago, # ^ |

my code

→ Reply

mnaeraxr

8 years ago, # ^ |

I like your idea, you didn't bother in implement lis in O(nlogn) :) Nice approach. +1

→ Reply

beAwesome

8 years ago, # ^ |

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?

→ Reply

8 years ago, # ^ |

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.

→ Reply

codingMachine

8 years ago, # ^ |

← Rev. 2 →

Can you give the link of that russsian article?

→ Reply