Click Here for Problem

Chinese Solution, since USACO does not have an official solution for the problem above.

I had a lot of trouble with the implementation of this question, so I looked up this solution online. Google Translate could only do so much for the page (the only solution I could find), but I think I was able to discern the following from the code:

1) The array "per" reverses the permutation process, and length of 31 represents a bitmask of that length,

2) The idea behind the "per" is that the result of a number of consecutive permutations can be assembled in logarithmic time, and

3) The variable "num" in the third main loop functions as a mask.

However, I do not fully understand the purpose of "bot", "now", and "k" in the third main loop, and the mathematics in the first and third main loops.

I would appreciate an explanation for these parts of the solution.

Thanks in advance!

We are given an array of size N and Q queries (1 <= N, Q <= 100000). Each query has 4 parameters: index i, index j, length L, and differences D (0 <= D <= 1). We must answer "YES" if a permutation of the subarray from arr[i] to arr[i+L-1] differs from a permutation of the subarray from arr[j] to arr[j+L-1] in at most D places, and "NO" otherwise.

This sounds like an offline segment tree problem, but I am not sure how to start implementing it.

Can someone give me some hints to get me started and moving in the right direction?

Please help, and thanks in advance!

UPD: Just for the sake of it, I tried submitting a naive N^2 solution, which didn't make it in the time limit of 2 seconds, as expected.

UPD2: Original problem statement is here.

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213

For whatever reason, implementing any of the three official editorial solutions is not working out for me, so I am changing tact.

My idea is to store the depths relative to the root for each node, run a DFS and BIT similar to what I used in this problem, add/subtract values to/from the BIT according to a sliding window (e.g. when L = 3 and a node with depth 5 is at the bottom of the sliding window, nodes with depth of at most 8 are at the top), and query all nodes in the window that are ancestors of the node in question.

I would appreciate comments on my method.

Please help, and thanks in advance!

UPD: I coded my fourth attempted solution, only for it to fail the same cases (7, 8, and 9). I would appreciate it if someone could find out what is wrong with it, as I have wasted 8+ hours trying to upsolve this problem to get no variance/change in results.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

int N;
vector<int> children [200001];
pair<long long, int> pis [200001];
int tree [200001], id [200001], mx [200001], ret [200001], curr = 1, index = 1;
long long L, depth [200001];

void add(int pos, long long x){
    while(pos < 200001){
        tree[pos] += x;
        pos += (pos&-pos);
    }
}

int query(int pos){
    int sum = 0;
    while(pos > 0){
        sum += tree[pos];
        pos -= (pos&-pos);
    }
    return sum;
}

int dfs(int x){
    id[x] = curr++; mx[x] = id[x];
    for(int i = 0; i < children[x].size(); i++){
        int next = children[x][i];
        mx[x] = max(mx[x], dfs(next));
    }
    return mx[x];
}

int main(){
    //freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);
    scanf("%d %d", &N, &L); depth[0] = 0ll;
    for(int i = 2; i <= N; i++){
        int x; long long y; scanf("%d %I64d", &x, &y);
        children[x].push_back(i); depth[i] = depth[x]+y;
    }
    dfs(1);
    for(int i = 1; i <= N; i++) pis[i] = make_pair(depth[i], i);
    sort(pis+1, pis+N+1);
    for(int i = 1; i <= N; i++){
        long long curDepth = pis[i].first; int now = pis[i].second; int from = id[now]; int to = mx[now];
        while(index <= N && curDepth+L >= depth[pis[index].second]){
            add(id[pis[index].second], 1);
            index++;
        }
        ret[now] = query(to)-query(from-1);
    }
    for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
    return 0;
}

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=213

My code below is my attempt to solve this problem, which keeps failing cases 7 through 9. I do not see a significant difference between my logic and the logic of the judge solution (the last one in the editorial here Your text to link here...). Can someone explain why my solution keeps producing a WA? I even resorted to changing my code to 0 based indexing after 3 hours of trying to perfectly match the judge solution, with no change in output. I sincerely apologize for posting a wall of code, but I have not found another way to resolve the issue after privately asking other users to look over it for me.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int id = 1;

struct Node{
    Node *parent;
    vector<Node*> children;
    long long depth;
    int last, label;
    Node(){ parent = NULL; depth = 0ll; last = -1; }
    void preorder(){
        label = id++;
        for(int i = 0; i < children.size(); i++) children[i]->preorder();
        if(children.size() == 0) last = label;
        else last = children.back()->last;
    }
};

struct Event{
    int a, b, index;
    long long len;
    bool operator<(const Event &other) const{
        if(len != other.len) return len < other.len;
        else return a < other.a;
    }
};

int N;
Node tree [400001];
long long L, fenwick [400001], ret [400001];
vector<Event> events;

void add(int pos, long long x){
    while(pos < 400001){
        fenwick[pos] += x;
        pos += (pos&-pos);
    }
}

long long query(int pos){
    long long sum = 0;
    while(pos > 0){
        sum += fenwick[pos];
        pos -= (pos&-pos);
    }
    return sum;
}

int main(){
    freopen("runaway.in", "r", stdin); freopen("runaway.out", "w", stdout);
    scanf("%d %d", &N, &L);
    for(int i = 2; i <= N; i++){
        int x; long long y; scanf("%d %lld", &x, &y);
        Node *par = tree+x;
        tree[i].parent = par;
        tree[i].depth = (par->depth)+y;
        par->children.push_back(tree+i);
    }
    tree[1].preorder();
    for(int i = 1; i <= N; i++){
        Event c;
        c.a = -1; c.b = -1;
        c.len = tree[i].depth; c.index = tree[i].label;
        Event d;
        d.a = tree[i].label; d.b = tree[i].last;
        d.len = tree[i].depth+L; d.index = i;
        events.push_back(c); events.push_back(d);
    }
    sort(events.begin(), events.end());
    for(int i = 0; i < events.size(); i++){
        Event e = events[i];
        if(e.a == -1) add(e.index, 1ll);
        else ret[e.index] = query(e.b)-query(e.a-1);
    }
    for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
    return 0;
}

Please help, and thanks in advance!

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=102

Another user pointed out to me the similarity between this problem and one on the most recent January contest (http://www.usaco.org/index.php?page=viewproblem2&cpid=696). The latter problem can be solved using the combination of a preorder traversal and BIT.

I was wondering if it is possible to solve the former problem with a combination of a Segment Tree and DFS (closest possible method to a preorder traversal). The segment tree would use lazy propagation to update the range of edges, but I am not sure how to use a DFS in this situation.

Am I on a right track? If so, I would appreciate input on how to continue. If not, please point me to another possible solution.

Please help, and thanks in advance!

http://codeforces.me/contest/145/submission/28183892

I keep missing Test Case #58 on this problem because my answer does not have enough elements. Does my program RTE before printing out the last 2 elements, or is my IO flawed in some way that prevents it from reading in the last few queries?

Please help, and thanks in advance! vamaddur