USACO January Contest 2016-2017

7 лет назад, # ^ |

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

→ Ответить

1000000007

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

aropan

7 лет назад, # ^ |

+21

Fixed.

→ Ответить

ista2000

7 лет назад, # ^ |

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

→ Ответить

AnonymousBunny

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

mnaeraxr

7 лет назад, # ^ |

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

→ Ответить

AnonymousBunny

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # ^ |

Yup, I basically did it like this too.

→ Ответить

TimonKnigge

7 лет назад, # ^ |

← 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.

→ Ответить

radoslav11

7 лет назад, # |

← 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

→ Ответить

7 лет назад, # ^ |

+10

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

→ Ответить

7 лет назад, # |

← Rev. 6 →

+34

My solutions, short:

platinum 1

platinum 2

platinum 3

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

→ Ответить

7 лет назад, # ^ |

← 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;

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

Alpha_Q

7 лет назад, # ^ |

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]}$ .

→ Ответить

goodthingstaketime_._

7 лет назад, # ^ |

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.

→ Ответить

tenshi_kanade

7 лет назад, # ^ |

+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";
}

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

oversolver

7 лет назад, # ^ |

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

→ Ответить

Alpha_Q

7 лет назад, # |

← 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

→ Ответить

FunTry

7 лет назад, # ^ |

← Rev. 2 →

-12

→ Ответить

7 лет назад, # ^ |

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

→ Ответить

7 лет назад, # |

+16

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

→ Ответить

bciobanu

7 лет назад, # ^ |

How does it work here?

→ Ответить

7 лет назад, # ^ |

my code

→ Ответить

mnaeraxr

7 лет назад, # ^ |

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

→ Ответить

beAwesome

7 лет назад, # ^ |

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?

→ Ответить

7 лет назад, # ^ |

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.

→ Ответить

codingMachine

7 лет назад, # ^ |

← Rev. 2 →

Can you give the link of that russsian article?

→ Ответить