All teams received an email stating that only onsite teams attending World Finals in Russia would be eligible for medals. The remote teams would be placed in a separate "open division" that would not be eligible for medals but would get titles such as "high honors" and "honors". This last minute change has left us reconsidering our decision to compete remotely.

You also need to be fully vaccinated (with proof of vaccination) to be able to attend World Finals in Russia.

Hello Codeforces! I am writing this blog post to bring attention to and publicly discuss inconsistencies in the ICPC World Finals selection process for North America.

For those who are unaware, every North American (NA) team competes in one regional (which is usually determined by their geographical location) and top teams are selected from each regional to represent NA in World Finals. The only official rule is that the winner of each region qualifies for finals. The remaining teams are selected based on several criteria that are not officially specified. In the past few years, NA has received 23+ world finals slots.

I am a member of Georgia Tech’s premier ICPC team, and my teammates are AlanWaP and RaresC. We compete in the southeastern USA (SER) regional in North America. Our region also contains University of Central Florida, who consistently have a top ~25 team at World Finals and who were the North American Champions and bronze medalists in the 2018 world finals. This year Georgia Tech ranked second in our regional solving 7/11 problems, and the top UCF team solved 9/11 problems. We have been in similar situations for the last four years: achieving 2nd place, losing to UCF, and not advancing to world finals.

Since UCF is the reigning NA champion, we expected to qualify for World Finals this year. In the past, there seems to have been an unofficial rule that gives the region of last year’s medalist(s) additional world finals spot(s). This rule appeared to be in place for Harvard and MIT, which are both in the Northeastern North America (NENA) regional. In 2016 world finals when both Harvard and MIT medaled, NENA received 3 world final spots for the next world finals. Note that the difference in problems solved between rank 1 and rank 3 was 4 problems. Similarly, when Berkeley was a medalist in the 2015 world finals, the PACNW region received three slots instead of their normal two for the next world finals.

After communication with NA ICPC officials, it seems that the difference in number of problems solved is primarily taken into account while determining how many slots are allotted to a region. This metric is inconsistent with the NENA example above, and it is also unreliable for several reasons:

• First, different regionals have different problem sets and some are significantly easier than others. For example, in Mid-Atlantic USA 2018, there were only 8 problems, 5 distinct teams solved all of them, and every problem was solved by at least 9 teams. SER was undoubtedly one of the hardest (if not the hardest) NA problem set this year.
• Second, it doesn’t take into account the strength of the region. For regions where the top teams are not as strong as UCF, one should expect to have closer competition.
• Last, our team's computer crashed for 30 minutes during SER 2018 around the 150 minute mark, which seriously impacted our time penalty. Printing at our site also took at least 45 minutes, making it almost impossible to “debug on paper” while a teammate codes another problem. Our team did not get a contest extension even though we made multiple requests, so we ran out of time coding the 8th solution. We want to point out that several schools in our region including UCF competed at a different site and didn’t encounter these problems. That said, both of these problems were officially recorded and the NA selection committee was aware of the differences.

The World Finals teams were announced recently, and we were surprised to not have advanced. Furthermore, the number of teams from NA was reduced from 23+ to 19 this year. The officials told us that the reason for this is the “growth of ICPC”. Why were so many slots cut from North America? They also told us that “NA champ’s region gets an extra slot convention” was considered but not used this year due to the new space constraints. However, they gave additional slots to other regions based on scoreboard closeness.

It is AlanWaP s last year of eligibility, and possibly my and RaresC s last participation as well. We’ve all invested a nontrivial number of hours into programming competitions, so this is incredibly disheartening for us. We performed very well nationally in NAIPC 2018 and in NAQ 2018. It is evident that we are a very strong NA team with the potential to perform well at world finals, so it seems odd that a region like SER is so underrepresented. Unfortunately, there is very little transparency in the selection process, and Georgia Tech regularly receives the short end of the stick. It’s terrific that our region has fierce competition, but we believe SER should routinely be awarded more WF slots because of this.

On a more positive note, there is discussion about North America moving to a super-regional system to decide teams next year, which would be fantastic and should eliminate all the problems caused by comparing incomparable regions. Coincidentally, it is likely going to be hosted by Georgia Tech. There has been an ongoing push for a more fair selection process for years, so we hope that the super-regional contest becomes the new standard for qualifying for World Finals from North America.

Edit: Relevant comment threads: Link 1 Link 2 Link 3

So I tried to open CF for the last two hours and was getting an error message which stated that due to some hardware issue, CF will be unavailable until 10 January 2017. That made me REALLY sad.....

I spent thirty minutes contemplating what I'd do in winter break, and squirmed at the idea of migrating to other websites. Please don't troll us CF :(

Hello CodeForces Community,

I would like to invite you all to take part in the CodeChef July Lunchtime. It is an IOI Style contest where participants will be given 4 problems to solve in 3 hrs. With the IOI just two weeks away, LunchTime forms a great way to practice and test your preparation.

The problems were set by me animeshf (Animesh Fatehpuria) and PraveenDhinwa (Praveen Dhinwa) and were tested by me and pushkarmishra (Pushkar Mishra). I hope you will enjoy solving them. We have problems of various difficulty levels ensuring that everyone can find something interesting to solve! Please give me your feedback on the problem set in the comments below after the contest.
You can find the rest of the details about the contest below.

Time: 30th July 2016 (1930 hrs) to 30th July 2016 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: Contest Page

Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, please register here in order to participate.

• Problem Setter: PraveenDhinwa (Praveen Dhinwa), animeshf (Animesh Fatehpuria)
• Problem Tester: animeshf (Animesh Fatehpuria) pushkarmishra (Pushkar Mishra)
• Editorialist: animeshf (Animesh Fatehpuria) pushkarmishra (Pushkar Mishra)
• Russian Translator: Antoniuk (Vasya Antoniuk)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team
• Contest Admin: PraveenDhinwa (Praveen Dhinwa), pushkarmishra (Pushkar Mishra)

Prizes:

• Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here

Introduction

Mo's Algorithm has become pretty popular in the past few years and is now considered as a pretty standard technique in the world of Competitive Programming. This blog will describe a method to generalize Mo's algorithm to maintain information about paths between nodes in a tree.

Prerequisites

Mo's Algorithm — If you do not know this yet, read this amazing article before continuing with this blog.

Preorder Traversal or DFS Order of the Tree.

Problem 1 — Handling Subtree Queries

Consider the following problem. You will be given a rooted Tree T of N nodes where each node is associated with a value A[node]. You need to handle Q queries, each comprising one integer u. In each query you must report the number of distinct values in the subtree rooted at u. In other words, if you store all the values in the subtree rooted at u in a set, what would be the size of this set?

Constraints

1 ≤ N, Q ≤ 10⁵

1 ≤ A[node] ≤ 10⁹

Solution(s)

Seems pretty simple, doesn't it? One easy way to solve this is to flatten the tree into an array by doing a Preorder traversal and then implement Mo's Algorithm. Maintain a lookup table which maintains the frequency of each value in the current window. By maintaining this, the answer can be updated easily. The complexity of this algorithm would be

Note that you can also solve this in by maintaining a set in each node and merging the smaller set into the larger ones.

Problem 2 — Handling Path Queries

Now let's modify Problem 1 a little. Instead of computing the number of distinct values in a subtree, compute the number of distinct values in the unique path from u to v. I recommend you to pause here and try solving the problem for a while. The constraints of this problem are the same as Problem 1.

The Issue

An important reason why Problem (1) worked beautifully was because the dfs-order traversal made it possible to represent any subtree as a contiguous range in an array. Thus the problem was reduced to "finding number of distinct values in a subarray [L, R] of A[]. Note that it is not possible to do so for path queries, as nodes which are O(N) distance apart in the tree might be O(1) distance apart in the flattened tree (represented by Array A[]). So doing a normal dfs-order would not work out.

Observation(s)

Let a node u have k children. Let us number them as v₁,v₂...v_k. Let S(u) denote the subtree rooted at u.

Let us assume that dfs() will visit u's children in the order v₁,v₂...v_k. Let x be any node in S(v_i) and y be any node in S(v_j) and let i < j. Notice that dfs(y) will be called only after dfs(x) has been completed and S(x) has been explored. Thus, before we call dfs(y), we would have entered and exited S(x). We will exploit this seemingly obvious property of dfs() to modify our existing algorithm and try to represent each query as a contiguous range in a flattened array.

Modified DFS-Order

Let us modify the dfs order as follows. For each node u, maintain the Start and End time of S(u). Let's call them ST(u) and EN(u). The only change you need to make is that you must increment the global timekeeping variable even when you finish traversing some subtree (EN(u) = ++cur). In short, we will maintain 2 values for each node u. One will denote the time when you entered S(u) and the other would denote the time when you exited S(u). Consider the tree in the picture. Given below are the ST() and EN() values of the nodes.

ST(1) = 1 EN(1) = 18

ST(2) = 2 EN(2) = 11

ST(3) = 3 EN(3) = 6

ST(4) = 4 EN(4) = 5

ST(5) = 7 EN(5) = 10

ST(6) = 8 EN(6) = 9

ST(7) = 12 EN(7) = 17

ST(8) = 13 EN(8) = 14

ST(9) = 15 EN(9) = 16

A[] = {1, 2, 3, 4, 4, 3, 5, 6, 6, 5, 2, 7, 8, 8, 9, 9, 7, 1}

The Algorithm

Now that we're equipped with the necessary weapons, let's understand how to process the queries.

Let a query be (u, v). We will try to map each query to a range in the flattened array. Let ST(u) ≤ ST(v) where ST(u) denotes visit time of node u in T. Let P = LCA(u, v) denote the lowest common ancestor of nodes u and v. There are 2 possible cases:

Case 1: P = u

In this case, our query range would be [ST(u), ST(v)]. Why will this work?

Consider any node x that does not lie in the (u, v) path.
Notice that x occurs twice or zero times in our specified query range.
Therefore, the nodes which occur exactly once in this range are precisely those that are on the (u, v) path! (Try to convince yourself of why this is true : It's all because of dfs() properties.)

This forms the crux of our algorithm. While implementing Mo's, our add/remove function needs to check the number of times a particular node appears in a range. If it occurs twice (or zero times), then we don't take it's value into account! This can be easily implemented while moving the left and right pointers.

Case 2: P ≠ u

In this case, our query range would be [EN(u), ST(v)] + [ST(P), ST(P)].

The same logic as Case 1 applies here as well. The only difference is that we need to consider the value of P i.e the LCA separately, as it would not be counted in the query range.

This same problem is available on SPOJ.

If you aren't sure about some elements of this algorithm, take a look at this neat code.

Conclusion

We have effectively managed to reduce problem (2) to number of distinct values in a subarray by doing some careful bookkeeping. Now we can solve the problem in This modified DFS order works brilliantly to handle any type path queries and works well with Mo's algo. We can use a similar approach to solve many types of path query problems.

For example, consider the question of finding number of inversions in a (u, v) path in a Tree T, where each node has a value associated with it. This can now be solved in by using the above technique and maintaining a BIT or Segment Tree.

This is my first blog and I apologize for any mistakes that I may have made. I would like to thank sidhant for helping me understand this technique.

Sample Problems

1) Count on a Tree II
2) Frank Sinatra — Problem F
3) Vasya and Little Bear

Thanks a lot for reading!

Original Post
Related Blog