Topcoder tutorials have always been a good resource to learn new algorithms and techniques. I was looking for some articles there and found out that all the links that were here are not working. What happened to them? Will they be back? And does anyone have a pdf or any other format version of them?

Problem: Given n points in x - y plane, it is required to find the minimum area for a square that encloses all the points.

For sure, some points will lie on the square sides in the optimal solution. I found a solution that finds the convex hull for the points. Then for each vertex, we will assume it is on the boundary, so, we will try to find the best rotation for the square. The rotation angle interval is determined by the angle at this vertex, so that the interval limits produce squares with sides overlapping with the two polygon sides intersecting at this vertex.

The solution finds the the best rotation angle for each vertex using ternary search. I am not sure why the area of a square for a fixed vertex is a unimodal function. Can someone prove it?

Hello Codeforces!

Suffix automaton is one of the interesting algorithms I learnt for strings. I was impressed by Maximal article for it and it helped me clearly grasp its concepts and applications. However, it is in Russian. I used yandex/google translate to understand it.

There are some articles for suffix automaton in English. Check here, here and here.

During an algorithms course, I was required to write a report for a non-basic data structure. I picked suffix automaton, so that It can be useful for anyone. It is compiled with LaTeX and there is a presentation that contains a visualization for it.

Here is the link. The article is not complete, but it contains the main points in Maximal article. It is just a translation for the original article (maybe I edited some parts, but not that much). If you need the source code, I can share it as well.

Hello everyone.

A few months ago, I read the proof for the complexity of Edmonds-Karp algorithm O(VE²) in "Introduction to Algorithms" and Dinic's algorithm O(V²E) on Maximal. Both proofs are convincing in the sense that they provide a correct upper bound. Also, the output-sensitive complexity O(flow·E) helps in some problems.

However, due to the graph constraints, some problems I encounter make me feel reluctant to:

1. consider running a max flow algorithm as a subroutine, so I try to come up with another idea.
2. select the algorithm that will pass the time limit (coding time vs. running time).

Here is an example of such problems: ASC 4 — A. Unique Attack. With the given graph constraints (1 ≤ V ≤ 800, 1 ≤ E ≤ 10000), it seems that max flow algorithms will not pass in 1 second. However, they do! (even Edmonds-Karp).

I was wondering if someone can provide a (quite large generated) test case that is close to the upper bound or maybe share intuitions/approximations/estimates for a tighter bound.

Hello Codeforces, I hope you enjoyed the round!

Just some notes about the problems:

• In problem A, the picture and example notes should complete your understanding for the problem if the statement itself is not clear.

• Solutions that check the lights of each part separately should have failed on pretests. My bad.

• Problem C was assigned as B at the beginning, but moved to C lest it is harder than B difficulty. However, I think problem B is still easier than problem C (check the solution below).

• I thought problem D is easier than problem E. Once, conditions are well-understood and related to each other and the problem is modeled correctly, then its implementation is easy.

The points I have just described is my own opinion in the problems. Of course, you might have a different point of view. However, I would like you to keep in mind that I did my best to make statements clear and pretests strong.

Thanks for your understanding!

812A - Сахир и перекресток

For pedestrian crossing i (1 ≤ i ≤ 4), lanes l_i, s_i, r_i, s_i + 2, l_i + 1, r_i - 1 are the only lanes that can cross it. So, we have to check that either p_i = 0 or all mentioned lanes are 0.

Complexity: O(1)

Implementation

812B - Охранник Сахир

When Sagheer reaches a floor for the first time, he will be standing at either left or right stairs. If he is standing at the left stairs, then he will go to the rightmost room with lights on. If he is standing at the right stairs, then he will go to the leftmost room with lights on. Next, he will either take the left stairs or the right stairs to go to the next floor. We will brute force on the choice of the stairs at each floor. Note that Sagheer doesn’t have to go to the last floor, so he will go to the highest floor that has a room with lights on.

Complexity: O(n·2ⁿ)

Implementation

812C - Сахир и нубийский рынок

If Sagheer can buy k items, then he can also buy less than k items because they will be within his budget. If he can’t buy k items, then can’t also buy more than k items because they will exceed his budget. So, we can apply binary search to find the best value for k. For each value k, we will compute the new prices, sort them and pick the minimum k prices to find the best minimum cost for k items.

Complexity:

Implementation

812D - Сахир и детский сад

Let’s go through scenario requests one by one. For request a b, if toy b is free, then child a can take it. Otherwise, child a will wait until the last child c who requested toy b finishes playing. Since, no child can wait for two toys at the same time, each child depends on at most one other child. So we can put an edge from the a to c. Thus, we can model the scenario as a forest (set of rooted trees) as each node has at most one outgoing edge (to its parent).

For query x y, if toy y is free, then child x can take it and no child will cry. Otherwise, toy y is held by another child. Lets denote z to be the last child who requested toy y. So x now depends on z. If z is in the subtree of x, then all children in the subtree of x will cry. Otherwise, no child will cry. We can check that a node is in the subtree of another node using euler walk (t_in and t_out) with preprocessing in O(n) and query time O(1)

Complexity: O(k + n + q)

Implementation

812E - Сахир и дерево с яблоками

In the standard nim game, we xor the values of all piles, and if the xor value is 0, then the first player loses. Otherwise, he has a winning strategy. One variant of the nim game has an extra move that allows players to add positive number of stones to a single pile (given some conditions to make the game finite). The solution for this variant is similar to the standard nim game because this extra move will be used by the winning player, and whenever the losing player does it, the winning player can cancel it by throwing away these added stones.

This problem can be modeled as the mentioned variant. Lets color leaf nodes with blue. The parent of a blue node is red and the parent of a red node is blue (that’s why all paths from root to leaves must have the same parity). Blue nodes are our piles while red nodes allow discarding apples or increasing piles.

If the xor value of blue nodes s = 0, then Soliman loses on the initial tree. To keep this state after the swap, Sagheer can:

• swap any two blue nodes or any two red nodes.

• swap a blue node with a red node if they have the same number of apples.

If the xor value of blue nodes s ≠ 0, then Sagheer loses on the initial tree. To flip this state after the swap, Sagheer must swap a blue node u with a red node v such that

Complexity: O(n + maxA) where maxA is the maximum value for apples in a single node.

Implementation

You can read more about games from this link

Hello Codeforces!

I would like to invite you to Codeforces Round #417 that will take place tomorrow on June 1st, 2017 at 17:05 MSK.

This is my first round. Great thanks to KAN for his efforts and help in the round preparation, mike_live and 300iq for testing the problems, and MikeMirzayanov for the awesome Codeforces and Polygon platforms.

The round is rated for the second division. Participants from the first division can take part out of competition. As usual, the participants will be given 5 problems and two hours to solve them.

I hope you will find the problems challenging and interesting!

UPD 1: Scoring disrtibution: 500 — 1000 — 1500 — 2000 — 2500.

UPD 2: Due to a technical issue, the contest is delayed by 10 minutes.

UPD 3: Contest is over. Congratulations to the winners!

Div2 Winners:

1. TERESO

2. neverfirst

3. _luckyE

4. zstu_jack

5. jiyutian

Div1 Winners:

1. y0105w49

2. _Reborn_

3. eddy1021

4. chemthan

5. KrK

UPD 4: Editorial

Suppose we have the standard knapsack problem and our DP state is (idx, remWeight). Due to memory constraints, we can memoize two rows only (say idx and idx + 1). How can we print the solution (the sequence of taken indices) for this problem?

Hello,

In this gym contest problem H. I got RTE even when I submitted the package solution because of the following error:

Error occurred during initialization of VM Incompatible minimum and maximum heap sizes specified

I don't know what to do with it, but I think there is a problem with the judge itself. Any help?

Hello,

I have tried to solve this problem [Promotions]. It was in SWERC 2015. This problem is reduced to counting successors of every node in a DAG. My best algorithm to solve it is to make a dfs for every node and count the number of reachable nodes. So, the complexity is O(VE), but I got TLE with Java. I checked online solutions and found nothing different (except they are in C++). I wonder if there is a more efficient algorithm, maybe O(V^2) or if someone can provide an efficient AC Java implementation for it.

Thanks!

Hello CF !

Before you proceed further, I do appreciate the efforts from Edvard and MikeMirzayanov about doing the Educational rounds, and putting their time for it. This post is solely based to try and make it better.

What got my thoughts about this was a recent conversation with MedoN11 about them.

The goal of the educational rounds is to educate people about well known topics/techniques in Competitive Programming, right ?

While I really like Educational Rounds, I personally do not see that much of a difference between them and regular rated rounds, maybe C-D are easier than usual for Educational, but if someone puts up an Educational as a rated round, I don't think many will notice.

IMO, it would be really great if we can start seeing classical problems appear. ( Basic RMQ, Classic Maxflow applicatons, Popular but "classic" DP optimizations,etc).

Many of these types ( and of course others that I do not know about) hardly appear in Educational rounds, and if they do, they are often a little bit random. For example, the past 2 rounds were really great for learning Matrix Power applications, first one was classical Linear recurrence to let you know about them, and the other was an application using them to count paths in a graph, but I can’t think of something else similar that happened.

If problems start to follow the same pattern but for a variety of topics, CF will have a plenty of classical problems similar to those on UVa/SPOJ that are used in trainings of different levels, and even make CF better than it is! And for sure, the problems will not be simple classical problems. They will need some creativity, as well ;)

I hope Edvard have a look at this. Thanks!

Hello,

Sometimes I encounter problems and can't come up with a solution better than backtracking. Even my backtracking solution, I can't analyze its time complexity. So, I try implementing it, see the worst case and find my intuition is true. Here are two of them, if someone can help me to prove why it should pass the time limit.

Problem 1: UVa 10506 — The Ouroboros problem. link, solution

Problem 2: UVa 165 — Stamps. link, solution

Thanks!