By vamaddur, history, 6 weeks ago, ,

(I'm mildly surprised at no blog post on the front page about this, but here it goes!)

Google Code Jam 2019 Round 3 will begin at 14:00 UTC. The top 25 participants will advance to the onsite finals in San Francisco!

Let's discuss (and rage about) the problems here after the contest is over!

• +83

By vamaddur, history, 18 months ago, ,

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

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

• -1

By vamaddur, history, 19 months ago, ,

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

• +4

By vamaddur, history, 20 months ago, ,

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

Picture Proof #1

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

Picture Proof #2

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.

• 0

By vamaddur, history, 20 months ago, ,

Problem Statement

Code

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

• 0

By vamaddur, history, 21 month(s) ago, ,

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

• +3

By vamaddur, history, 22 months ago, ,

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?

• -16

By vamaddur, history, 22 months ago, ,

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?

• +6

By vamaddur, history, 23 months ago, ,

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.

EDIT: Triple Bump!

• 0

By vamaddur, history, 23 months ago, ,

For the past 3 years that I have been doing programming contests, I've noticed the trend that I very rarely solve problems in the last 1/6 to 1/5 of the given time in any competition (e.g. last 20 minutes of a CF round or last hour of an ACM event).

Sometimes this lack of efficacy is due to not knowing a niche technique, or running into a genuinely hard problem. However, more often than not, I open the editorial and groan at not seeing a solution that I was millimeters away from on pen and paper. I have never went into the home stretch thinking I would not solve anything (so I don't believe its my mental at fault), but I would like to figure out if there is a way in addition to straight up practice that more experienced coders use to make the most of every minute of competition.

Hopefully those people can share their insights for both myself and the CF community. :)

• +37

By vamaddur, history, 23 months ago, ,

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.

• +11

By vamaddur, history, 23 months ago, ,

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?

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)

• -3

By vamaddur, history, 23 months ago, ,

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?

• +7

By vamaddur, history, 23 months ago, ,

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?

• 0

By vamaddur, history, 2 years ago, ,

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.

• +14

By vamaddur, history, 2 years ago, ,

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?

• +10

By vamaddur, history, 2 years ago, ,

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.

• +10

By vamaddur, history, 2 years ago, ,

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.

• +13

By vamaddur, history, 2 years ago, ,

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

• +4

By vamaddur, history, 2 years ago, ,

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?

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

• +2

By vamaddur, history, 2 years ago, ,

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.

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"

• +1

By vamaddur, history, 2 years ago, ,

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.

• +2

By vamaddur, history, 2 years ago, ,

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?

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.

• +4

By vamaddur, history, 2 years ago, ,

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.

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]){
index++;
}
ret[now] = query(to)-query(from-1);
}
for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
return 0;
}


• -7

By vamaddur, history, 2 years ago, ,

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];
else ret[e.index] = query(e.b)-query(e.a-1);
}
for(int i = 1; i <= N; i++) cout << ret[i] << '\n';
return 0;
}