cuom1999's blog

By cuom1999, history, 3 years ago, In English

When I go to the complete problemset page (example), it displays a beautiful HTML page. However, when I print it with ctrl + P to get a PDF, it gives me a file with 2 columns per page (like the below image).

How can I make it one column per page, like in the HTML?

Full text and comments »

  • Vote: I like it
  • +57
  • Vote: I do not like it

By cuom1999, 3 years ago, In English

I'm thinking about this problem that seems very natural but I don't know if there is any online judge to submit:

Given a graph of 2-way friendship with $$$n$$$ vertices and $$$m$$$ undirected edges. For each person $$$u$$$, let's recommend him/her a person $$$v$$$ such that: $$$v$$$ is not a friend of $$$u$$$, and $$$v$$$ has the biggest number of common friends with $$$u$$$. In case of ties, any answer is accepted. If $$$u$$$ is already friend with everyone, print $$$-1$$$. Number of common friends between $$$u$$$ and $$$v$$$ is number of people that are friends of both $$$u$$$ and $$$v$$$.

A simple brute-force solution will solve this in $$$O(mn)$$$. A solution involving adjacency matrix will solve it in $$$O(m\sqrt{m})$$$ but requires $$$O(n^2)$$$ space by counting how many paths of length $$$2$$$ from $$$u$$$ to $$$v$$$ for all pairs $$$(u, v)$$$. Can we solve it better?

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

By cuom1999, history, 4 years ago, In English

We usually see problems like: Given an array $$$a_1, a_2, ..., a_n$$$. How many ways to partition the array into continuous groups in which each group satisfies a condition (e.g sum not exceeding a number, ...)? This kind of problem is usually done in linear or log-linear time with dynamic programming and prefix sum.

What about changing the statement to a circular array? Formally, given a circular array $$$a_1, a_2, ..., a_n$$$. How many ways to partition the circle into continuous groups in which each group satisfies a condition? Two ways are different if there are two indices belonging to the same group in one way, but different groups in the other way.

How to solve this problem in sub-quadratic time in general? I find even the simplest conditions like the below are quite hard.

a) Each group has sum $$$\leq M$$$, with a given $$$M$$$.

b) Each group has $$$gcd > 1$$$.

...

Solution for problem a or b are appreciated.

Full text and comments »

  • Vote: I like it
  • +64
  • Vote: I do not like it

By cuom1999, history, 4 years ago, In English

Here is an interesting problem for Vietnam Informatics Competition for Youth:

Given a board $$$m \times n \ (m, n \leq 10^6)$$$. You know $$$q (q \leq 10^6)$$$ information: square $$$(x_i, y_i)$$$ contains $$$a_i \ (a_i \leq 10^9)$$$ stones. Other unlisted squares contain $$$0$$$ stones. In one step, you could move one stone to an adjacent square, which shares an edge with the current square. The task is to spread stones equally to every square. For example, it takes 2 steps to make [[0, 0], [2, 2]] become [[1, 1], [1, 1]].

I could only model this as a min-cost max-flow problem and solve for small $$$m, n$$$. How to solve the full problem?

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it

By cuom1999, history, 4 years ago, In English

Statement:

Given a tree of around $$$10^5$$$ nodes, $$$10^5$$$ queries, and an integer $$$k$$$. Each query has $$$k$$$ vertices $$$a_1, a_2, ..., a_k$$$. For each query, find a node $$$x$$$ such that $$$dist(x, a_1) + dist(x, a_2) + ... + dist(x, a_k)$$$ is maximum, then print that maximum value. Here $$$dist(u, v)$$$ is the number of edges on the simple path from $$$x$$$ to $$$y$$$.

I have been thinking about this problem for a while but not been able to solve it, even for small $$$k$$$ like $$$2$$$ or $$$3$$$. Any idea on how to solve this problem? I appreciate all ideas and any sources of similar problems.

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

By cuom1999, history, 4 years ago, In English

I'm thinking about this problem: Given $$$n$$$ rectangles on a unit grid with coordinates around $$$10^9$$$. We want to decompose the union of them into non-overlapping rectangles. There are two interests: the number of output rectangles and the running time. Here is one of my approaches:

Process rectangles one by one. We keep a list of processed non-overlapping rectangles. For a newly added rectangle, we iterate over the list and find one that intersects our new rectangle. If there is, we divide the new rectangles into 4 small parts and process them recursively. This approach depends on the size of the result; so if there are $$$k$$$ output rectangles, the running time seems to be around $$$O(nk)$$$. In random test cases, $$$k \approx O(n)$$$. And it seems to be very hard to generate a counter test since we could shuffle the order of rectangles first.

I'm also thinking about scanline but haven't figured out how to get a good number of output rectangles. The best thing I came up with would result $$$O(n \log n)$$$ time complexity but may contain $$$O(n^2)$$$ rectangles in the worst cases, which is easy to generate counter tests.

I also tried googling but the closest thing I found is partitioning a polygon. Would you share some thoughts on this problem?

Full text and comments »

  • Vote: I like it
  • +20
  • Vote: I do not like it

By cuom1999, history, 5 years ago, In English

Today I read the problem statements of ICPC Asia Nakhon Pathom 2017. Then, I found a very interesting (to me) problem but still cannot have solved it yet :(

You are given a graph with $$$n$$$ vertices and $$$m$$$ weighted edges. You have to handle $$$q$$$ queries online of the form: Given 2 integers $$$L$$$ and $$$R$$$, what is the size of the largest connected component if we only consider edges having weights in the range $$$[L, R]$$$.

Here $$$n,m,q \leq 100000$$$.

I have never met any problems in this type so any insight ideas or similar problems are very welcomed. Thank you very much!!!

Full text and comments »

  • Vote: I like it
  • +60
  • Vote: I do not like it

By cuom1999, history, 6 years ago, In English

"In a triangulation of a regular n-gon, there always exists a diagonal that divides the polygon into 2 small polygons and the smaller one has at least vertices."

I saw this property in the NEERC 2014's editorial but still cannot prove it. Can anyone help me? Thank you!

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By cuom1999, history, 7 years ago, In English

I submitted two same codes for problem 949C - Data Center Maintenance. Initially, I chose Lang GNU C++14 but got RTE. After a while, I tried my luck, chose GNU C++11 and miraculously, got AC. Here are my codes:

Code with GNU C++14 : 36116002 (verdict RTE)

Code with GNU C++11 : 36116440 (verdict AC)

I have not found anything to explain it and I'm afraid that these things may happen during some future contests. Can you suggest any reasons? Thank you!

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it