vamaddur's blog

By vamaddur, history, 3 weeks ago, In English,

Problem Statement

I was wondering if there is a possible solution that uses a segment tree rather than a BBST (balanced binary search tree), as I find that segment trees are easier to implement.

Please help, and thanks in advance!

EDIT: Triple Bump!

Read more »

 
 
 
 

By vamaddur, history, 3 weeks ago, In English,

Problem Statement Solution

Could someone please provide an alternate solution with an explanation to this problem, or explain the official solution with more clarity (I only understand the first two lines)? I do not understand the logic behind precomputing "cost" or how the recurrence works.

Thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By vamaddur, history, 5 weeks ago, In English,

Problem Link

Source Code

Test Data

I tried to solve the problem above using a Segment Tree for each plane. The idea is that I find the maximum interference level between each pair of intersection points, and do a Range-Maximum-Query on the segments the query overlaps. It seems that I have the correct idea/complexity since my code passes the cases of Batch 2 (consisting of max case), but I WA on the Batch 1 Cases.

I think the error I have lies in how I determine the indices for querying in lines 98-120, but I have not been able to find/fix it. Where did I go wrong in solving the problem?

Please help, and thanks in advance!

EDIT: Bump? I would appreciate if someone commented what additional information they would need to help me out instead of relentlessly pushing the downvote button...

EDIT 2: Ended up solving it (YAY!) by changing the custom comparator for "Intersection", but I don't know why it works. If someone could explain that to me... (Solution)

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By vamaddur, history, 6 weeks ago, In English,

Pictures of the Problem

The gist of the problem is to find the area that a rubber band around N circles of equal radius encloses. My thought process is as follows:

1) Find the convex hull of all the circle centers.

2) Use the Shoelace Theorem to find the area of the convex hull.

3) Add the area of the convex hull and the area of one circle of radius K to a running total.

4) Add the area of augmenting rectangles on the convex hull to the running total; for each rectangle, the area is found by multiplying the distance between two adjacent vertices on the hull by K (essentially the hull perimeter times K)

My implementation of these ideas is here, which gets WA on all hidden cases. Is my logic incorrect, or is there a bug in my implementation?

Please help, and thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By vamaddur, history, 6 weeks ago, In English,

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=516 Official Solution: http://www.usaco.org/current/data/sol_grass_gold.html

I was able to reduce the problem to solving it on a weighted DAG after compressing the graph into strongly connected components. However, I am not able to handle the caveat of being able to traverse a reversed edge at most once.

Is there a way to solve this final step of the problem without dynamic programming? If not, can someone explain what exactly is going on in the "solve" function and calls to it?

Please help, and thanks in advance!

Read more »

 
 
 
 

By vamaddur, history, 7 weeks ago, In English,

Link

Can someone prove the correctness of the approach described in the first answer on the thread? I understand why the first step is crucial as a starting point.

Thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +14
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

Given a positive integer N, calculate the sum of inversions in every bitmask of length N.

For example, if N = 2, our masks are 00 (0 inversions), 01 (0 inversions), 10 (1 inversion), and 11 (0 inversions). We output 1.

For example, if N = 3, our masks are 000 (0 inversions), 001 (0 inversions), 010 (1 inversion), 011 (0 inversions), 100 (2 inversions), 101 (1 inversion), 110 (2 inversions), and 111 (0 inversions). We output 0+0+1+0+2+1+2+0 = 6.

How can I do this efficiently?

Please help, and thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

Given a set {a, b, c, d}, its non-empty subsets in lexicographic order are as follows: {a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d}

I found an O((sizeofset)^2) method of finding the Nth lexicographically smallest subset here, but I was wondering if there was a faster way to do this.

I know that finding the Nth lexicographically smallest string can be reduced from O((sizeofset)^2) time to O(sizeofset). time, which motivated me to ask this question about a similar reduction for subsets.

Please help, and thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

Given a graph with at most 2*10^5 nodes and 2*10^5 edges, bicolor the graph such that the difference between the number of nodes with each color is minimized, and print out that difference.

I am able to bicolor each of the connected components, and find the number of each color in each component. I tried to make the final step of finding the minimum difference into the subset sum problem before realizing that there are restrictions on what numbers can go together.

E.g. I have components (Red, Blue) as (1, 5) and (2, 4); the optimal subset sum solution would normally be to put the 1 and 5 together, and the 2 and 4 together. However, the (1, 5) pair and (2, 4) pair are component pairs, which is not allowed.

Please help, and thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

I know how to find the diameter of a tree in linear time, prove the validity of the algorithm used to do so (successive BFS's), and prove why it doesn't work for non-tree connected graphs.

However, I need an algorithm/approach that has better complexity than O(N^2) to find the diameter of a relatively large WEIGHTED pseudotree (a tree with one extra edge).

Please help, and thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

Let P(x) be a function that returns the product of digits of x. For example P(935) = 9*3*5 = 135. Now let us define another function P_repeat(x):

int P_repeat(int x){
    if(x < 10) return x
    return P_repeat(P(x))
}

For a value v, find the number of numbers x less than N such that P_repeat(x) = v.

How would I make a transition between states in a digit DP for this problem?

Please help, and thanks in advance!

UPD: The bounds are N <= 10^13.

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By vamaddur, history, 2 months ago, In English,

Given two non-empty strings A and B composed of lowercase Latin letters, what is the minimum number of substrings of A needed to form string B? The lengths of A and B are at most 100000. If the task is not possible for a given input, output a rogue value (a.k.a. -1).

I was thinking about solving this with an O(N^2) DP method, but that does not fit into the time limit of 5 seconds.

Please help, and thanks in advance!

EDIT: Note that chosen substrings can overlap. I put some cases below.

Input #1: abcbcd abcd

Output #1: 2

Input #2: iamsmart iamdumb

Output #2: -1

Input #3: asmallmallinmalta atallmallinlima

Output #3: 5

Explanations: "abcd" = "ab" + "cd", no "d"s in the first string of Input 2, "atallmallinlima" = "a" + "ta" + "llmallin" + "li" + "ma"

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • -20
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By vamaddur, history, 3 months ago, In English,

http://codeforces.com/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

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it