Contest has ended. No further submissions allowed.

This sounds convincing, I think. You will be able, but after the contest ends for everyone.

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

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?

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

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;

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 .

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.

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.

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

.

Actually, in reals, with the constraint has its minimum at from Lagrange multipliers (or simply taking derivatives when all but two variables are fixed).

How does it work here?

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

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?

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?

How do you make sure the sum of the x's is equal to K?

After the results are published, problems are moved to practice.

Read the comments here before asking.