xuanquang1999's blog

By xuanquang1999, history, 5 months ago, In English,

I'm trying to solve the problem 101237G — Total LCS from 2013-2014 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest. The task give two string S and T, each with at most 2000 character, and ask to compute the longest common subsequence (LCS) of string S and substring T[i..j] for all pair 1 ≤ i ≤ j ≤ |T|.

I can't come up with anything beside the naive O(|S| * |T|2) dynamic programming. I have read the code from some contestant (using coach mode) but I still have no idea how those solution work. Can anyone give me a hint?

Thanks in advance.

Read more »

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

By xuanquang1999, history, 13 months ago, In English,

I'm solving 27E — Number With The Given Amount Of Divisors. My code involved a function mul(a, b) that will return 1018 + 7 if multiplying a and b will lead to overflow, and min(1018 + 7, a * b) otherwise. I checked for overflow using the condition a*b div a != b.

When I submit my solution using C++14, it seemed that the overflow check failed, which lead to WA on test 5.

34068376

However, when I uncomment the if statement in the mul function (which, theoretically don't print anything out), it get accepted.

34068431

I resubmitted the WA code with C++11 and C++17 Diagnostics, and it get accepted too.

I don't know what happened here. I suspected that some kind of optimization from compiler caused this strange behavior, but unfoturnately I know nothing about compiler optimization. Can anyone give me a proper explanation about this strange behavior? Thanks in advance.

Read more »

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

By xuanquang1999, history, 16 months ago, In English,

I'm solving problem L — Windy Path from 2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1). But, when I submitted my solution, I got "Denial of Judgement". I tried to resubmit it many times, but nothing changed. What should I do? Thanks in advance.

Link to my submission

Read more »

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

By xuanquang1999, history, 17 months ago, In English,

I'm trying to solve B — Safety Grade from SEERC 2011. My solution is to iterate over all the pair of vertices in the graph (let's call the pair (s, t)), calculate the maximum flow (using Edmond-Karp algorithm) from s to t, and the answer is the minimum value among these max flow value. Also, notice that the answer can't exceed the minimum of each vertex's degree (which won't exceed ), so each maximum flow calculation will be done in less than BFS. So, the overall complexity of the algorithm is O(n * m2).

I don't know why my solution got Runtime Error (that's the last verdict I would expect to get in this problem). I ran stress-testing for half an hour, but couldn't find any wrong test case. I need help finding what's wrong with my implementation. Thanks in advance.

Read more »

 
 
 
 

By xuanquang1999, history, 20 months ago, In English,

In this morning training, our team was given this problem from Prologin contest — 2015 Regional event (unfortunately, the statement is written in French, but I'll try to summarize the statement as accurate as possible):

"There are N rooms and M roads, road i directly connect room ui with room vi. There are also K switches, switch i can control road ai and road bi. More specifically, if switch i is on, roads ai is enabled and roads bi is disabled, and vice-versa (disabled road can't be walked on). If there is no switch controlling road i, then that road is always enabled. It's guaranteed that one road will be controlled by at most one switch, and when all switches are off, the roads system will form a tree (connected acyclic graph). Is it true that for all 2k states of the switches, the roads system will always form a tree?"

Our teams have discussed this problem for the entire morning but failed to come up with any algorithm that can solve this problem in polynomial time. It also doesn't help that the original statement didn't give constraint of N, M, and K, too. Can someone help us on this matter? Thanks in advance.

Read more »

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

By xuanquang1999, history, 21 month(s) ago, In English,

Recently, a terrorist group has attacked in Iranian Parliament in Tehran. Link to the newspaper

I feel really worried about the safety of contestants who are going to participate in IOI 2017 there (which is, including me). I also worried that this year's IOI will be cancelled due to terrorism.

Does your Ministry of Education and Training worry about this? What is your thinking about this incident?

Read more »

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

By xuanquang1999, history, 21 month(s) ago, In English,

This is a problem I was given back when I'm training for APIO Vietnam team selection.

"There are n (n ≤ 600) factory that is planned to be built on a line, number from 1 to n. There are m (m ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu + 1 = xv. There are another p (p ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu ≤ xv. (xi mean coordinate of factory i, if it's going to be built)

Your task is to pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of different coordinate is maximum. (If there's no way to do this, print "-1")

I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.

UDP1: Sorry about the mistaken objective. The correct objective is "the number of distinct point", not "factory".

UDP2: The problem I'm asking is the same with this POI problem (Thanks Swistakk for informing me this). I've updated the statement summary in the blog.

Read more »

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

By xuanquang1999, history, 21 month(s) ago, In English,

I'm trying to solve 720B — Cactusophobia from Russian Code Cup 2016 Final. I read the editorial and understood the flow solution for this problem. So I find some implementation for this problem. I read dreamoon's solution (20732895), which used Dinic flow finding algorithm and run in 373ms. But, since Dinic algorithm run in O(n2m), and the graph can have up to 30000 vertices and edges, how could this run in time? Can someone enlighten me about this? Thanks in advance.

Read more »

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

By xuanquang1999, history, 23 months ago, In English,

One of my friend recently asked me the following problem:

"Given an array a1, a2, ..., an and a number K (n ≤ 105, ai ≤ 109). Is there a way split the array into K disjoint sub-arrays (don't have to be contiguous) such that sum of each sub-array is equal to each other (and equal to )?"

My teacher came up with the following greedy solution: for each sub-array, keep choosing the maximum number such that sum of sub-array with that number is still smaller or equal to S. When it's impossible to add more number from a to this sub-array, check if the current sum is equal to S.

However, both my teacher and me are unable to neither prove the correctness of the solution nor find a counter-example for it. Is this greedy solution always optimal? How to prove (or disprove) it? Thanks in advance.

Read more »

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

By xuanquang1999, history, 23 months ago, In English,

I have recently encounter this game-theory problem:

"Two player X and Y is going to play a game. Initially, they choose a number P (P ≤ 1018) and a set of number A1, A2, A3, ..., An (n ≤ 5000, 0 ≤ Ai < P). They will take their turns alternatively. In each turn, one player will remove a number from the set. After K turns, if the sum of all remaining numbers in the set is divisible by P, player X will win. Otherwise, player Y will win.

Determine who will win the game, if both of them play optimally. (The name of player who make the first move will be given in the input)"

I completely have no efficient approach for this problem (except the naive bitmask DP). Can anyone give me an hint? Thanks in advance.

Read more »

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

By xuanquang1999, history, 2 years ago, In English,

I have recently encountered this problem:

"Given an array a1, a2, ..., an, (1 ≤ n ≤ 105, 1 ≤ ai ≤ 106), count the number of subsequence ap1, ap2, ..., apk that ap1&ap2&...&apk = 0 (print the remain of division of that number by 109 + 7"

The best solution that I can come up is a dynamic programming solution that is not fast enough to solve this problem. How to solve this problem?

Thanks in advance.

Read more »

 
 
 
 

By xuanquang1999, history, 3 years ago, In English,

Is there a way to do this if m, k <= 10^9?

PS: C here mean combination number.

Read more »

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

By xuanquang1999, history, 3 years ago, In English,

I'm trying to solve the following problem (from VOI 2005).

Given a sequence a with n numbers, find the minimum M such that there's a way to split sequence a into k non-empty continuous subsequence and the total sum of each subsequence does not exceed M.

Constrains: 1 <= k <= n <= 15000, |ai| <= 30000, ai may be negative.

The best solution I can come up for this problem is the following O(n^2*k) DP solution:

Call f[i][k] the minimum value M for the sequence that contain first i numbers, d[i] the sum of the first i number of sequence. Then we have the following formula: f[i][k] = min(max(f[j][k-1], d[i]-d[j])) (with 0 <= j < i)

Of course, with such big constrains, this solution is not fast enough. Is there a faster solution for this? Thanks in advance.

Read more »

 
 
 
 

By xuanquang1999, history, 3 years ago, In English,

I'm trying to solve 103 — Stacking Boxes on UVa online judge. My idea is first, sort all the box that no box can be nested in the previous box, then run O(n^2) LIS DP on it.

However, when I print the order and the sizes of all boxes, I found something weird:

The Bubble sort algorithm gave correct sorting order:

Code used Bubble sort

But std::sort gave wrong sorting order (more specific, box 5 should stay before box 1):

Code used std::sort

std::stable_sort also gave wrong sorting order:

Code used std::stable_sort

Did something go wrong with my implementation? Or something went wrong with std::sort and std::stable_sort?

Read more »

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

By xuanquang1999, history, 3 years ago, In English,

I'm having trouble at this problem on Vietnam SPOJ. The problem is: Given array a[1], a[2], ... a[n], count the number of pair (u, v) that u < v and a[u] > a[v]. Constrain: n <= 60000 and a[i] <= 60000.

I tried to this using Fenwick Tree. But I'm getting only 60 points (maximum points is 100). Is there anything wrong in my implementation?

Here's my code.

Read more »

 
 
 
 

By xuanquang1999, history, 4 years ago, In English,

I'm trying to solve Div1D on Codeforces Round 250 — The Child and Sequence. My idea is the same with the editorial: Build the maximum and sum segment tree, and for queries of type 2, I keep finding the largest number in the segment, mod it by x until there's no number in the segment larger or equal x. (All is done by segment tree). However, I got TLE on test 4.

My submission: 12348730

I can't find anything wrong with my solution, so that's why I need help on this. Can anyone help me with this? Thanks in advanced.

Read more »

 
 
 
 

By xuanquang1999, history, 4 years ago, In English,

Hello everyone, this is my editorial for Round #310. I decided to write one since the author of this round didn't have time to do it. Currently, there's only Div2A and Div2B available, and I'll try to write editorial for Div1A and Div1B soon (about Div1C and Div1D, microtony has already written a nice tutorial for them (you can check out here), and Div1E is too difficult for me).

UPD: Div2C-Div1A is available now!

UPD2: Div2D-Div1B is available now!

Div2A — Case of the Zeros and Ones

First, we can come up with a naive solution. While there's still some position i that 'remove-able' ((s[i] = '0' and s[i+1] = '1') or (s[i] = '1' and s[i+1] = '0')), we'll remove s[i] and s[i+1] from the string. However, in the worst case (contain all character '0' first, then character '1' or vise-versa), the complexity is O(n^2) and will surely got TLE.

We should optimize this solution by using stack. Push each character in string s to the stack, and while pushing, check if the top two element of the stack is ('0' and '1') or ('1' and '0') (or we can simply write abs(stack[top]-stack[top-1) = 1). If this happen, remove them from stack (top:=top-2). The answer is the number of character left in the stack.

Solution using Stack: 11816506

Sound a bit too complicated for Div2A, right? There must be a more simple solution. We should notice that if there's still some zero and one in the string, there must be at least one position that 'remove-able'. So, we can remove one character '0' and one character '1' from the string until one type of character run out. We can come up with more simple solution with these analysis: just count the number of character '0' and '1' in the string, and the answer is abs(cnt0-cnt1).

Solution with some analysis: 11830868

Both of the solution has complexity O(n).

Div2B — Case of Fake Numbers

To solve this problem, first, we should notice that after n action, the gear will turn back to the initial state. So, if solution exist, the number of action to get it must be less than n. We can get an solution: just keep performing the action until we get the require structure (answer is 'Yes') or the number of action goes equal n (answer is 'No'). Complexity is O(n^2).

My solution: 11816203

This solution is already fast enough to get AC. But we can easily optimize it further. We can notice that we will need k = (n-a[1]) mod n move to get a[1] equal to 0, so we can just calculate a[i] after k move (whick is (a[i]-k+n) mod n, with i mod 2 = 0 and (a[i]-k+n) mod n, with i mod 2 = 1) and check if this is the required structure. Complexity is now O(n).

The better solution: 11816999

Div2C-Div1A — Case of Matryoshkas

To make thing easier to explain, we will use 'Box' instead of 'Matryoshkas' (Now this problem's name should be 'Case of Box' :D)

Consider the following test:

7 3
2 1 2 6
3 3 4 5
1 7

The following image demonstrate the test:

We know that we can put box a in box b only if box b doesn't contain any other boxes or contained in any other box. So, that mean box b must be alone. So, it would be make sense if we put all the box, which still inside some other box, out (in an appropriate order). However, we don't have to do this with the sequence 1, 2, ..., x since nothing can be put in box 1, and we can just put that sequence of box in box x+1 later. For example, with the above test, the process is described in below picture.

This process take n-(k-1)-x moves.

Then, we can put sequence of box 1, 2, ..., x in box x+1, box x+1 in box x+2, ... box n-1 in box n. For example, with the above test, the process is described in below picture (again).

This process take n-x moves.

The final answer is (n-(k-1)-x)+(n-x) = 2*(n-x)-k+1.

My solution: 11821602

Complexity: O(n)

Div2D-Div1B — Case of Fugitive

Call b(lb, rb, jth) the j-th bridge to build has required length from lb to rb (inclusive). We know that b[j] = (li[j+1]-ri[j], ri[j+1]-li[j], j). Call c(len, ith) the i-th available bridge that has length of len, with c[i] = (a[i], i). We will also need array ans[i] to store the answer for the i-th bridge to build.

Now, we'll assign ans[i] = -1. Sort b in increase of lb, then increase of rb. Sort c in increase of len.

Now, we will iterate each element of c from left to right. For each c[i], we will consider all the bridge to build that has minimum length less or equal to c[i].len (while(b[j].lb <= c[i].len) ++j) and add them to the 'to_build' list. Then, choose the bridge in 'to_build' list that has the smallest rb and we'll get ans[b[j].jth] = c[i].ith (remember to check that c[i].len <= b[j].rb, too!). At the end, if there's still some ans[i] = -1, then there is no answer. Otherwise, say 'Yes' and print all ans[i].

We'll have O(n^2 + m log m) solution now. To improve this, we need to find the bridge in 'to_build' list that has the smallest rb in O(log n), which can be done by using C++ std::set to store the 'to_build' list.

My solution: 11830446

Complexity: O(n log n + m log m)

Read more »

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

By xuanquang1999, history, 4 years ago, In English,

Hello everyone. I have noticed the absence of round 273's editorial, so I decided to write one. This is the first time I write an editorial, so hope everyone like this!

I didn't know how to solve C and E yet, so it would be appreciated if someone help me with these problems.

Also, how to use LaTex in codeforces? I want to use this so my editorial would be more clear to read.

UDP: Actually, there's a (well-hidden) tutorial for this round, but it's written in Russian (with a English version using google translate in comment section). If you can read Russian, click here.

UDP2: Problem C is now available!

A — Initial Bet

Since the coin only pass from this player to other player, the coins sum of all player won’t change in the game. That mean, we’ll have 5*b = c1+c2+c3+c4+c5. We’ll put sum = c1+c2+c3+c4+c5. So, if sum is divisible by b, the answer will be sum/b. Otherwise, the answer doesn’t exist.

Be careful with the case 0 0 0 0 0 too, since b > 0, answer doesn’t exist in this case.

My solution: 11607374

Complexity: O(1)

B — Random Teams

If a team have a participants, there will be a*(a-1)/2 pairs of friends formed.

For the minimum case, the participants should be unionly – distributed in all the team. More precisely, each team should not have more than one contestant compared to other team. Suppose we’ve already had n div m contestant in each team, we’ll have n mod m contestant left, we now should give each contestant left in first n mod m teams.

For example, with the test 8 3, we’ll first give all team 8 div 3 = 2 contestants, the result now is 2 2 2. We’ll have 8 mod 3 = 2 contestants left, we should each contestant in the first and the second team, so the final result is: 3 3 2.

The maximum case is more simple, we should give only give one contestant in first m-1 teams, and give the last team all the contestant left. For example with above test, the result is 1 1 6.

Since number of the contestant in one team can be 10^9, the maximum numbers of pairs formed can be 10^18, so we should use int64 (long long in c++) to avoid overflow.

My solution: 11607784

Complexity: O(1)

C — Table Decorations

spiderbatman has a great idea for this problem. You can read his comment here.

The order of the balloons isn't important, so instead or r, g, b, we'll call them a[0], a[1], a[2] and sort them in ascending order. We'll now have a[0] <= a[1] <= a[2].

There's two case:

  • 2*(a[0]+a[1]) <= a[2]. In this case, we can take a[0] sets of (1, 0, 2) and a[1] sets of (0, 1, 2), so the answer is a[0]+a[1].

  • 2*(a[0]+a[1]) > a[2]. In this case, we can continuously take a set of two balloon from a[2] and a balloon from max(a[0], a[1]) until a point that a[2] <= max(a[0], a[1]). At this point, max(a[0], a[1])-a[2] <= 1, and since max(a[0], a[1]) - min(a[0], a[1]) <= 1 too, max(a[0], a[1], a[2]) - min(a[0], a[1], a[2]) <= 1. All we have to do left is take all possible (1, 1, 1) group left. Since we only take the balloons in group of 3, (a[0]+a[1]+a[2]) mod 3 doesn't change, so there will be at most (a[0]+a[1]+a[2]) mod 3 balloons wasted. We go back to the beginning now. The answer is (a[0]+a[1]+a[2]) div 3.

My solution: 11614150

Complexity: O(1)

D — Red-Green Towers

For more convenient, we’ll call a function trinum(x) = (x*(x+1))/ 2, which is also the number of blocks needed to build a tower with height x.

First, we’ll find h, the maximum height possible of the tower. We know that h <= trinum(l+r). Since (l+r) <= 2*10^5, h <= 631, so we can just use a brute-force to find this value.

Now, the main part of this problem, which can be solved by using dynamic programming. We’ll call f[ih, ir] the number of towers that have height ih, can be built from ir red block and trinum(ih)-ir green blocks.

For each f[ih, ir], there’s two way to reach it:

  • Add ih red block. This can only be done if ih <= ir <= min(r, trinum(ih)). In this case, f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih].

  • Add ih green block. This can only be done if max(0, trinum(ih)-g) <= ir <= min(r, trinum(ih-1)). In this case, f[ih, ir] = f[ih, ir] + f[ih-1, ir-ih].

The answer to this problem is sum of all f[h, ir] with 0 <= ir <= r.

We will probably get MLE now...

MLE solution: 11600887

How to improve the memory used? We'll see that all f[ih] can only be affected by f[ih-1], so we'll used two one-dimension arrays to store the result instead of a two-dimension array. The solution should get accepted now.

Accepted solution: 11600930

Complexity: O(r*sqrt(l+r))

E — Wavy numbers

Unfinished...

Read more »

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

By xuanquang1999, 4 years ago, In English,

Is there a way to do this?

Read more »

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

By xuanquang1999, 4 years ago, In English,
  • Statement:

Given a very large number X that has n digits, delete k (1 <= k < n <= 5*10^5) digits from it so that the remain part is as large as possible.

  • Input:

First line: Two numbers n & k.

Second line: Number X (without leading zero)

  • Output:

The largest number can be obtained after deleting k digits from it.

  • Sample test:

Input

4 2

1924

Output

94

I has met this problem more than five times in my life, but I can't find a solution for this. It would be appreciated if someone help me with this.

Read more »

 
 
 
 

By xuanquang1999, 4 years ago, In English,

I'm trying to solve the problem A of Codeforces Trainings Season 2 Episode 11. But I don't understand why did I got TLE on test 2, while I used O(n) solution. Can anyone help me explaining it?

My solution

Read more »