This Saturday, April 24, at 5pm UTC (12pm CST), the University of Texas at Austin is hosting an "invitational" (actually open to anyone) programming contest. The contest will last 5 hours and is intended to be similar to a North American ICPC regional contest in terms of difficulty. There will be 10-14 problems, and we encourage you to follow ICPC rules.

The contest link will be posted at some point tomorrow, and the contest will be hosted in the Codeforces Gym. We hope to see you there!

EDIT: Contest published!

We are given a tree of N nodes (with integer labels 1 to N). For each node in the tree, count the number of connected subgraphs in which that node has the maximum value label.

It is not too difficult to find a quadratic time solution by rerooting the tree N times and then performing an O(N) DFS with a dynamic programming step. Is it possible to solve this problem in O(N), O(N log N), or some sub-quadratic-time-complexity though?

Tomorrow, November 23, at 7pm UTC (1pm CST), the University of Texas at Austin is hosting an "invitational" (actually open to anyone) programming contest. The contest will last 5 hours and is intended to be similar to a North American ICPC regional contest in terms of difficulty. There will be 10-14 problems, and we encourage you to follow ICPC rules: teams of 3 on one computer, using no online resources.

If you want to participate, you can sign up using the registration form: https://forms.gle/yXE4j5JyKhhQENbD9

The link to contest is: https://utipcf19.kattis.com/

Original Problem

Can someone provide an editorial of this problem or link to one that already exists (I was not able to find one via Google search)?

You can also check out this OEIS sequence!

(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!

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

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

Thanks in advance!

Problem Link

Editorial Link

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

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.

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

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!

Problem Link

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!

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!

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

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!

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)

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!

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!

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!

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"