Today, Bangkok regional 2014 was finished. Previously I wrote a blog post regarding the contest, but I accidently deleted it when I was trying to edit it..

So I'm posting the result here if anyone is interested:

1. AAA (NTU, Singapore) con_nha_ngheo, ddldyj237, sillyboy
2. Alacrity (NUS, Singapore) flashmt, giongto35, RetiredKid
3. TaiDaJiaYou (NTU, Taiwan)
4. Java# (VNU, Vietnam) net12k44, Aquacloud, ntit_co1
5. DCM (NUS, Singapore) infrmtcs, rais.fathin38, zeulb
6. .NET (VNU, Vietnam) fpvyzv600, tsunayoshi, meodorewan
7. Sanity’s Eclipse (SJTU, China)

Amongst top 7, there are 13 people from Vietnam. Congratz guys! :)

My comments during the contest

Hi,

Today I made a couple of submissions, and I think the results are strange:

First, this submission got AC: 8645138

Then, I removed one big array, and it got MLE: 8645149. By clicking on Compare, you can see the only thing I did was removing one big array, f2, and its calculation.

I thought that because my submission uses approximately 256MB, so I tried removing another big array, and surprisingly, it still got MLE: 8645179

Then I recalculated the memory that I used in the 3rd mentioned submission and see that I only used less than 100MB. Even deep DFS can not cause it to MLE. What is happening here? Can anyone explain?

100506A - Average distance

For this problem, you need to calculate:

sum(distance(u, v)) / (some_constant)

How to calculte sum(distance(u, v)) efficiently? Obviously, you cannot iterate through all pair of vertices u and v. That would take at least O(N²).

When calculating the sum, notice that you need to add one edge multiple times. There are only N edges, but for each edge, in naive solution, you added it multiple times. So now you can see an idea for optimizing the naive solution: For each edge, count how many times it appear in sum(distance(u, v)) and add it to result.

Turns out this is quite simple: For edge (u, v) where u is parent of v in the tree, the path going through it must have the form: "something --> u --> v --> something". The number of such path is size(subtree(v)) * (n - subtree(v)).

My code

Given a Mincost Maxflow problem where all costs are non-negative integers at most K, for some small values of K (K = 1, 2, 3...)

I've heard the following claim: There is ALWAYS a conversion from this Mincost Maxflow problem to a Maxflow problem. Is this claim true? If yes, then I think it is very valuable in competitions.

Following are unofficial solutions for all problems.

100499A - Cool number

Solution 1

The most obvious solution for this problem is to brute force all numbers, and check if it is a cool number. My code

After running this code for several minutes, you should be able to get results for all K ≤ 9. The only result for K = 7 is 3211000, for K = 8 is 42101000 and for K = 9 is 521001000. From these results, you should be able to guess the result for K = 10 is 6210001000.

Solution 2

There are many ways to optimize the above solution. The most standard way is to see that the sum of all digits is equal to K, thus if you restrict your brute force to exit when sum of digit is greater than K, you should get a solution which runs in around a few seconds.

100499B - K smallest numbers

Since all numbers are at most 10⁷, you can count number of occurrence of each value.

My code.

100499C - Grid city

I don't know how to solve this problem, but following are some ideas from tester:

• For each query, (x₁, y₁) to (x₂, y₂), consider following lines:

  • Nearest North lines from (x₁, y₁) and (x₂, y₂)
  • Nearest South lines from (x₁, y₁) and (x₂, y₂)
  • Nearest East lines from (x₁, y₁) and (x₂, y₂)
  • Nearest West lines from (x₁, y₁) and (x₂, y₂)

• So we have 8 lines from (x₁, y₁) and 8 lines from (x₂, y₂). Consider all intersections of these lines (there are 64 of them). Then we can use Floyd to find shortest path in this new grid.

This problem has many implementation details that need to be taken care of, for example, the points in queries can be on locations that are not intersections.

Accepted code from yenthanh.t7 who implemented this idea.

100499D - Pairwise Coprime Set

To solve this problem, you must observe that the solution is always the set of primes less than or equal to N. This can be proved mathematically, but you can also observe this from playing with small cases.

To find all primes that is at most N, you can use Sieve of Eratosthenes.

My code

100499E - Binary Search Tree

Disclaimer: I haven't coded this problem, so not sure the following will work correctly.

Since a connected component of a binary tree is also a binary tree, the only necessary condition for it to be a binary search tree is that the keys should be in increasing order.

We write a method dfs(Node u) that returns the maximum binary search tree rooted at node u. The outline of the algorithm looks like following:

Tree dfs(Node u) {
    Tree left = dfs(left_child(u))
    Tree right = dfs(right_child(u))

    return build_result(left, right)
}

There are still two things that need to be taken care of:

• How to represent a tree efficiently? Since we know that it is always a binary tree, and only the order is important, you can represent it with an array of integers, containing the keys of the tree.

• How to build result for Node u from result of its left child and right child? To contain node u, we can only use nodes in left subtree having keys less than node u. Similarly, we can only use nodes in right subtree that have keys greater than node u. So, from the result of left subtree, we remove all nodes that have keys greater or equal to node u. Similar for right subtree, and then we can combine these keys to get the result for node u.

Now, we have something that can run in O(N²). To optimize it to O(N * logN), you can do the following:

When you get the 2 arrays from left subtree and right subtree, reuse the bigger one (adding necessary values to the other one, and return that array)

Code from team ThanQ+: here.

100499F - Tree again

Let's look closely at the pre-order traversal of the tree. You can see that for every subtree rooted at vertex u, all of its nodes are at adjacent positions! Using this information, the queries become:

• Maintain the pre-order traversal of the tree

• For query type 1, cut the segment of the pre-order traversal of sub-tree u, and put it after pre-order traversal of sub-tree v.

• For query type 2, print the i-th node in the pre-order traversal.

Thus, the main idea is to use a balanced binary search tree, such as splay tree to maintain this pre-order traversal. However, there are still some implementation details that need to be take care of: For query 1 to work, you must also maintain the end-point of pre-order traversal of each subtree. This turns out to be very hard to implement.

A trick to work around this is to modify the pre-order traversal a bit: We add each vertex twice, one when entering the pre_order_traversal method, one before exiting the pre_order_traversal method. With this, you can easily maintain the end-point of pre-order traversal of each subtree, but query 2 needs some modification to work.

You can see my code for more details.

100499G - Visual Illusion

This is the most simple problem in the constest. You just need to print the board as shown in the problem statement.

Code from team ThanQ+

100499H - CCTV

Idea:

Consider only camera 1, located at (0, 0). Divide the room into smaller triangles. For each triangle, the area that is visible from camera 1 should also be a triangle.

The most difficult part in this problem is how to divide the room into smaller triangles. One way is to sort all corners of glass cases in clockwise order. Let's call these points P1, P2, ..., Pk. Now consider triangle formed by 2 rays: (0, 0) — P_i and (0, 0) — P(i + 1). The viewable area of this triangle is also a triangle. Thus, you only need to consider all edges of glass cases, and see which edge is closest to the camera.

My code.

100499I - Fraction

Some observation:

• 0.12345 = 12345 / 100000
• 0.(123) = 123 / 999
• 0.0(123) = 123 / 9990

So, to solve this problem, you need to split the number into three parts: Integer, fraction and repeated fraction. Then add these parts together. When add these fractions together, you must be careful to avoid overflow. One way to be sure is to use Java BigInteger.

My code

100499J - Healthy Recipes

This is a knapsack problem, which can be solved using dynamic programming. However, there is one small trick in this problem: The number of meals can be exponential, and thus in the dp function, you need to reset the dp value to K when it exceeds K. See author solution for more details.

Hi everyone!

During this exciting ACM season, our country had organized an online training contest. And now we have decided to make it public via Codeforces gym!

The contest is scheduled on Sunday, Oct 12th at lasts for 5 hours 15 minutes.

The contest was designed to be easy, most suitable for div 2 and purple teams. But if reds rated want to join, you are more than welcome: We believe there should be at least 1 interesting problem for you.

The problem setters are ConanKudo, ngfam_kongu, khuebeo and me (I_love_Hoang_Yen). After happy ending at ACM World finals, we have retired from ACM careers and now set contests in our free time. Though, this is my first time adding a contest to Codeforces.

Good luck & have fun!

UPD. The contest will start in less than 24 hours. There will be problem statement in English and Vietnamese. However, due to technical reasons, Vietnamese problem statement could not be uploaded directly to Codeforces. During the first 5 minutes of the contest, we will give link to Vietnamese version in an Announcement.

UPD 2. 1 minute to contest. Good luck and have fun!

UPD 3. Contest is over. Congrats to ThanQ+ team who solved 8 problems. The problem set turned out to be much harder than I predicted. You can find solution here