http://blog.csdn.net/jiangshibiao/article/details/21446033

Can someone further explain the proof of the formula given in this blog?

Thanks in advance!

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 166 |

3 | Petr | 156 |

4 | csacademy | 155 |

5 | Swistakk | 150 |

6 | lewin | 149 |

7 | Um_nik | 142 |

8 | Errichto | 141 |

9 | matthew99 | 138 |

10 | PikMike | 137 |

http://blog.csdn.net/jiangshibiao/article/details/21446033

Can someone further explain the proof of the formula given in this blog?

Thanks in advance!

"An alternative is to consider all O(2^B) valid values for A in an outer loop. If one indexes not by the full signature but by a 64-bit hash of it, then the runtime becomes O(2^BN), but in the unlikely event of two different signatures hashing to the same 64-bit value, the answer may be incorrect or must be verified. Many who wrote exponential solutions in B received time outs; on occasion a low constraint is a red herring and hides an easily implemented more efficient solution."

I tried this approach in my solution here, but I get TLE with a complexity that has an added factor of B * log N (due to the map and hash computation). How can I prune my current solution down to the intended complexity?

Please help, and thanks in advance!

When I name a variable "index" in my C++11 code, it successfully compiles with MinGW in CodeBlocks on my PC.

However, on any online compiler/IDE (in this case, Ideone), I get a compile-time error.

How can I make my compiler and/or IDE identify reserved words and prevent me from using them by accident?

I know it's a minor problem, and I could easily circumvent it by "misspelling" variable names (as I am doing now; e.g. prevy instead of prev), but I would still like to fix it.

I tried using the logic in this blog post, but I keep getting WA. My code uses the identity 0*nC0+1*nC1+2*nC2+...+n*nCn = n*2^(n-1).

Can someone please find the flaw in my counting method (or even better, provide a test case that breaks my code)?

Thanks in advance!

Given an undirected connected graph, what is the minimum number of edges that must be added to it to make it 2-vertex-connected, and what are those edges?

Is the methodology for this problem similar to the same situation of making a graph 2-edge-connected (adding ceil(numPendants/2) edges)?

Please help, and thanks in advance!

More Detailed Problem Description

I understand the theory for this problem (fast matrix exponentiation), but I need a problem to test my code on, as I was not able to find one after multiple Internet searches. Could someone please provide a problem that asks for a solution along these lines?

Thanks in advance!

My strategy is to compute the number of palindromic substrings from index 0 to index i in a prefix sum array, and then compute the number of palindromic substrings from i+1 to strlen(N)-1 in a suffix sum array. We can then sum the products of prefix[i]*suffix[i+1] and somehow account for overcounting to get our answer. My main issue is finding the number of palindromic substrings in O(N) time (O(N^2) is not feasible as N could be up to 10^5).

Is my method reasonable, and if so, how can I solve the subproblem of finding the number of palindromic substrings in a prefix?

Please help, and thanks in advance!

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!

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!

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)

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!

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!

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!

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!

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!

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!

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!

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.

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"

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2018 16:45:32 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|