A month after the Vietnamese National contest have passed. This Friday (Dec 11, 2020), there will be the 2020 Vietnam Regional contest. We will also have an online mirror.

Details of Online Mirror:

• Time: 9am GMT+7
• Contest link

Details of Official Contest:

• Time: 8am GMT+7
• Contest link

Problems prepared by:

• ngfam_kongu
• chemthan
• I_love_Hoang_Yen
• I_love_tigersugar
• laoriu
• khuebeo
• Prof. Do Duc Dong

Contest difficulty won't be published before the contest. You can see our previous year contests below: (note that this year may be easier, more difficult or the same difficulty):

• 2020 Vietnam National; CF announcement
• 2019 Vietnam National; CF announcement
• 2019 Vietnam Regional; CF announcement
• 2018 Vietnam National
• 2018 Vietnam Regional
• 2017 Vietnam National
• 2017 Vietnam Regional
• Link to all ICPC Vietnam contests, some with solutions

UPD: The problems are now on Open Kattis

Hi,

This Sunday (Nov 15, 2020), there will be 2020 ICPC Vietnam National Contest on Kattis. This is the preliminary round before the Asia Vietnamese Regional. There will be online mirror after the contest.

Details of Online Mirror:

• Time: 1pm GMT+7
• Contest Link

Details of Official contest:

• Time: 8am GMT+7
• Contest Link

Problems prepared by:

• ngfam_kongu
• chemthan
• I_love_Hoang_Yen
• I_love_tigersugar
• laoriu
• ll931110
• khuebeo
• and some professors from Vietnam.

Contest difficulty won't be published before the contest. You can see our previous year contests below: (note that this year may be easier, more difficult or the same difficulty):

• 2019 Vietnam National; CF announcement
• 2019 Vietnam Regional; CF announcement
• 2018 Vietnam National
• 2018 Vietnam Regional
• 2017 Vietnam National
• 2017 Vietnam Regional
• Link to all ICPC Vietnam contests, some with solutions

UPD: For Vietnamese speaking folks, we will have a livestream at 8pm (GMT+7) where some problem authors will talk about solutions and other Q&A. Links to livestream will be put on VNOI page

UPD2: The problems are now on open Kattis

Hi,

We have added the problems from 2019 ICPC Asia Danang Regional on Kattis. I think the problems are very interesting and fun.

I have created a contest on Kattis on Sun, Dec 15th, 7pm GMT+7. But you can also create your own contests.

• Kattis contest on Sun, Dec 15th
• Onsite contest — do not look unless you want to see scoreboard
• Problems — if you want to create your own contest using these problems

Problems were prepared by:

• ngfam_kongu
• chemthan
• I_love_Hoang_Yen
• I_love_tigersugar
• laoriu
• ll931110
• khuebeo
• and some professors from Vietnam.

Hello world,

We would like to invite you to participate in the live online mirror of The 2019 Vietnam National Contest on Kattis. This is the prelim round for the 2019 Vietnam Regional Contest in Danang, but we believe there would be at least some interesting problems for everyone.

• Mirror link
• Contest link
• Time — 8am, Sunday, Nov 3, 2019, Vietnamese time
• Contest use ICPC rule.
• Teams are welcomed.

Problems are prepared by:

• ngfam_kongu
• I_love_tigersugar
• I_love_Hoang_Yen
• laoriu
• khuebeo
• ll931110
• minh141198
• cataphract
• Hoang Yen

Good luck & have fun!

Edit: contest will start in 7.5 hours.

Hi,

The ICPC Vietnam National 2018 was held recently. It is the prelim round before the ICPC Vietnam Regional 2018.

Open contest will be on Kattis. Start time: Sat — Nov 17, 2:00:00 UTC

I think it would be a good practice for teams participating in ICPC this year.

Problems are prepared by:

• Lang Trung Hieu ngfam_kongu
• Pham Van Hanh I_love_tigersugar
• Trung Nguyen chemthan
• Trung Nguyen I_love_Hoang_Yen (yes we have 2 different Trung Nguyen)
• Le Don Khue khuebeo
• Some problems are contributed by some universities in Vietnam.

Standing of real contest.

Edit: It seems you cannot ask clarification on Kattis. You can ask clarification here, I will try to answer.

UPD: Author's solutions are published here.

Hi all,

This Sunday (Nov 05, 2017), there will be ACM ICPC Vietnam National Round 2017. This is the qualification round for Vietnamese teams participating in ACM ICPC Vietnam Regional.

There will be online mirror on Kattis.

• Time: 8am Vietnamese time
• Normal ACM ICPC rules will be used.
• Standings will be frozen in last hour.

I hope that many of you will enjoy the problemset, especially the teams that will come to our Vietnamese regional. Good luck & have fun :).

UPD: Editorial in Vietnamese: http://acmicpc-vietnam.github.io/2016/regional/solutions/ACMICPCRegionalVietnam2016-Editorial.pdf

Hi all,

On Oct 15th, 7pm Vietnamese time, we will have Vietnamese regional 2016 replay on Kattis.

• The contest will last for 5 hours with normal ACM ICPC rules.
• After the contest we'll publish editorial in Vietnamese and official solutions.
• Teams are recommended.
• It is not rated.

If you are not afraid of spoilers, see standings here. Team from Seoul National Univ were #3 in ACM ICPC World final 2016-2017 and LINUX from VNU were #39 in World final 2016-2017. Can you beat them? :p

The problems were prepared by I_love_Hoang_Yen, ngfam_kongu, lythanh, khuebeo and some professors in Vietnam. The contest is uploaded to Kattis by I_love_tigersugar.

UPD 2: Round B is this Sunday (May 7th) — 5.00 GMT. Time

UPD: Round A is this Sunday Mar 5th — 5.00 GMT. Time

Hi,

GCJ Kickstart (previously called GCJ APAC) will have its Practice Round this weekend. Schedule.

For problem difficulty, you can see previous year's GCJ APAC.

This year, it has 6 rounds (you can see them in the Schedule above).

For university students, this is a good chance for applying to Google. If you have high rank in these rounds, you will automatically pass the 1st phone interview round (which might be difficult for competitive programmer, e.g. flashmt failed his phone interview =)). If you have good result, you will get contacted by recruiter. You can see more details in FAQ.

My team (me + flashmt + nguyenhungtam) was probably never noticed by anyone, but we were actually aiming for medal. And I think we performed ok in the final, ending up at #15, still need some more luck & brain to win a medal. Anw, I decided to share my story. Btw if you are Vietnamese, you can also read this.

Back story

In the ACM history, a Vietnamese team has never won any WF medal. 5 years ago, team of ktuan (only Vietnamese red target on Topcoder) had high hope, but ended up at #17. 4 years ago, team of ConanKudo also had high hope, but messed up in the first 3 hours and ended up at #17.

So I really wanted to win medal. And I've been planning for this World Final for several years..

Team formation

I've chosen flashmt as teammates for several years, but were not able to choose any third member. Since I only want to select Vietnamese, we have only few good options (darknstd, infrmtcs — both IOI silver medalist). After the WF 2015, I read this comment by fhlasek about the story of his team, and decided to pick an IMO guy instead. Thus, I picked nguyenhungtam who was IMO medalist but has very few experience with programming / algorithm and I trained him from that. It was a good choice, I had a lot of fun watching/trying to understand problem solving from Math people perspective, and we did much better with better mathematical imagination.

Regionals

At regionals, nguyenhungtam has few experience, so I was really afraid of losing ticket to WF. Anw, we won in Jakarta regional which guaranteed a ticket. We were #3 at Singapore regional, but I always believe we can do much better as nguyenhungtam improved very fast towards WF.

Strategy

Our strategy is flashmt will code mostly all problems while nguyenhungtam and I solve all the problems on paper. This is mainly because I usually fail to code simple things in important competitions (anw during this WF I implemented B & K, both had 1 wrong submission, but I think it is ok considering my current standard). And we also believe that the WF problemset requires more thinking, so 2/3 team time thinking is good.

And indeed, there are many positive side on this strategy:

• I think I had much more time solving problems.
• The algorithm needs to be very clear before we start implementing them.
• Since flashmt's coding skill is very good, leaving him the only one coding is definitely good enough.

My take on the WF problemset

I think the easier problems are ok, but maybe too many of them (8 easy problems..). I liked K. The judge solution for B is nice, but I think they are not very familiar with Divide & conquer DP optimization, thus this problem became copy-paste divide & conquer DP from our notebook. (I publicized our notebook here — you can use it at your own risk)

There were 5 hard problems F H I J M. I think H I J are too hard, M is hard to implement, so my team only had one choice of solving F: either we solve F and get medal or we don't solve F and don't get medal. I think the choice is very limited this year. Maybe if there was 1 medium problem instead of easy problem, there would be some choice for teams after solving easy problems.

Anw, my team strategy worked well. We always have something to code until we finished the 8th problem. And flashmt did not have too hard-to-debug bugs, so we were solving problems quite fast considering our level.

After this WF, probably I'll partially retired (probably still participate in CF rounds & big contests but mostly no training). If you have questions for me in comments, I'll gladly answer.

UPD: Special thanks to my girlfriend, ktuan, ConanKudo and ngfam_kongu. I inherited the spirit from ktuan by hearing stories about him, and ConanKudo and ngfam_kongu trained me to this level :)

With many regionals around the world finished, I think it is time to start collecting teams that are going to World Final this year. Please help me adding information to the tables :)

Europe

Asia

Latin America

Africa & the Middle East

North America

South Pacific

UPD: I changed file extension from jpg --> png and it worked. Thanks SarvagyaAgarwal, radoslav11

Hi,

Today when I updated my profile picture, I got this:

The image is broken in the panel on the right & when I comment, but it is shown correctly in my profile page.

Can admin take a look? :(

So if you have been coding C++ for a long time, you see people discover bugs in g++ every now and then, for example: this, that, here and there.

In this comment regarding IOI, andreyv said "On IOI they will most likely use the Linux distribution's default GCC, which was tested to build the numerous distribution's packages" and we should not worry about it.

But g++ is also widely used in ACM regionals, which is setup by some hosting university.

So, I have few questions:

1. Is there any way that we can avoid compiler issues when writing code? e.g. Avoid some specific/strange coding pattern? Pray to god?
2. How likely do you think that this can actually happen in a contest and affect someone?
3. Do you know / have been involved in preparing ACM contests & know if people carefully select compiler version?

Today when I opened CF problemset's standing, I saw this:

Previously I_love_Tanya_Romanova was #1 with 4000 problems, but now he has only less than 2k problems. What happened? Is it bug or new CF feature? Can some admin shed some light on this? Thanks

Of course, everyone loves Doge. That is why today, after miserably failing GCJ (yes, I have to rant here), I decided to write a Google Chrome extension that changes Codeforces to DogeForces. Here are some screenshots:

Why you should install this extension?

• It is cool.
• Everyone will now be red (in Dogeforces, everyone is the same, even admins or those who haven't participated in contests).
• Everyone will now have high rating and high contribution (at least in profile page).
• Everyone loves Doge.

And of course, functionalities of Codeforces still works (but cooler).

How to install:

• Get codes from my Github repo. If you don't know how to use git, just create a folder, and put all those files in that folder.
• Go to chrome://extensions/ and tick on "Developer mode"
• Click on "Load unpacked extension..." and select the folder that you just get from Github.
• Load Codeforces, and wait for a while for the extension to work.

Known issues:

• Doesn't work correctly with Russian version of the site.
• Doesn't update the profile panel on the right.

If you have any other problem(s), it means I had bugs somewhere, plz open Chrome developer console and comment here with every details you can get, and I'll try to fix it as quickly as possible.

You know how to use git/how to write Chrome extension, and also love Doge? Show your love by adding functionalities to the Extension & send me a pull request :)

Thank you for your attention, and plz enjoy DogeForces.

Many credit to choice for his amazing blogpost, especially for the DogeForces logo.

UPD1: v1.1. Fixed a bug that shows rating in comments on blog posts. Please download new version if you already downloaded before.

UPD2: v1.2. Fixed a minor bug that affects profiles without email.

UPD3: v1.3. Fixed bug that affects profiles without badge.

UPD4: v1.4. Fixed bug that caused showing rating in user comments page.

UPD5: v1.5. Setting pages now work correctly.

If you have written some programming problems, and have prepared test cases, you will probably experience the terrible feeling that some test cases may be invalid (meaning it does not agree with the constraints in problem statement): upper bound can be violated, your graph not satisfied connectivity requirements or is not at tree... It is reasonable to feel that way. Even experienced problem setters make mistakes sometimes (for example, in the prestigious ACM ICPC World final 2007).

It is strictly recommended to write a special program (called validator) to formally check each test to satisfy all requirements from problem statements. Validators are strictly required for problems on Codeforces. Polygon has built-in support of validators.

It is really easy to write a validator using testlib.h.

Example

Following is a validator that could be used for problem 100541A - Stock Market:

#include "testlib.h"

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int testCount = inf.readInt(1, 10, "testCount");
    inf.readEoln();
    
    for (int i = 0; i < testCount; i++) {
        setTestCase(i + 1);
        int n = inf.readInt(1, 100, "n");
        inf.readSpace();
        inf.readInt(1, 1'000'000, "w");
        inf.readEoln();

        inf.readInts(n, 1, 1000, "p");
        inf.readEoln();
    }

    inf.readEof();
}

#include "testlib.h"

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    int testCount = inf.readInt(1, 10, "testCount");
    inf.readEoln();
    
    for (int i = 0; i < testCount; i++) {
        int n = inf.readInt(1, 100, "n");
        inf.readSpace();
        inf.readInt(1, 1000000, "w");
        inf.readEoln();

        for(int i = 0; i < n; ++i) {
            inf.readInt(1, 1000, "p_i");
            if (i < n-1)
                inf.readSpace();
        }
        inf.readEoln();
    }

    inf.readEof();
}

The wonderful thing about this validator is that it is very simple and it is very difficult to write something incorrect.

More examples can be found at the Github repo

Available methods

The first line of your code should be registerValidation(argc, argv) which does some magic in the background, so that you can use the necessary methods.

So few minutes ago I answered this question on Quora. It felt like a good answer (because it has pictures), so I would like to share it again here.

If you don't see the images, just click the Quora link above

Many people tell you that solving lots of problems and you will become red on Topcoder/Codeforces one day. It is true, and is the only universally approved way in competitive programming community, but actually it is just half of the story. Let me first explain to you the 'science' of problem solving (which is not very scientific, since it was only developed by myself).

For each problem, in order to solve it, you must jump over a gap. It can be either a difficult implementation, or some hard-to-see observation, or difficult algorithm, etc.

For me, some problems are very easy (e.g. Codeforces div 2 A, B..), because the gap feel so small to me, and passing through them feels just like casual walking.

Some problems are very hard. The gap is just too huge, or there are many many gaps, and you can get stuck in the middle because you're too tired after maybe first gap.

Using this science, we can explain a lot of phenomenon in the competitive programming world:

• Some guys learn very fast, got to div 1 only after like a couple of weeks after he just started programming: Some people are born with high jumping ability (problem solving skill). They can jump over average gaps easily.
• The more you train, the better you become: Of course, if you jump around all day, you must be somewhat better at jumping through gaps, and thus being able to solve more difficult problems in less time, since you don't need lots of mental preparation or warm up excercise before jumping.

But.. it also means that, if you just solve too easy problems, you can still only walk through small gaps. You may walk through gaps faster, but you are still unable to jump.

So yes, the best strategy to improve your competitive programming skill is to practice a lot, but you must solve gradually harder problems, not just the easy ones. Get out of your comfortable zone and challenge yourself. For example, if you solve problems on Codeforces:

• Sort by number of people who solved it.
• Start with page 1
• Solve some problems. If you feel you can solve them in like 5-10 mins, immediately ignore the other problems, move on to page 2
• Continue until you feel challenged (e.g. need like an hour to solve / can not solve at all / ...).
• Try really hard, but if you fail, look at editorial, ask for solutions, ...

UPD: Found a solution to this, thanks to RamTararam. If you have same problem, just clear history. I'll keep this blog post here for a while for those who have same issue.

It's been a while since I can't open submissions from standing page in Chrome now.

A few days ago, I saw rng_58's comment, and see that I'm not the only one with this issue. Though my situation is reversed: I can only open submission in Firefox (while he can only do so in Chrome).

I thought that, like some bugs that we sometimes saw in Codeforces, this will eventually be fixed, but it's been quite a time now. So now I'm writing this blog to ask if any of you have same issues? Is there a fix for this? (Maybe update some plugins like Flash, etc..). I use Chrome for everything, so it's quite annoying for me to switch to Firefox just to see submissions..

Thanks.

Today I came across this article, in which "Peter Norvig said that one thing that was surprising to him was that being a winner at programming contests was a negative factor for performing well on the job".

Normally I don't care about these topics, but this is from Google — where they have good population of high rated competitive programmers and the claim is backed with data.

The article mentioned one point: "programming contest winners are used to cranking solutions out fast and that you performed better at the job if you were more reflective and went slowly and made sure things were right". Though I don't think this is true. For example, being competitive programmer taught me:

1. bugs can be everywhere & we must code carefully
2. many problems have amazing solutions, and it's not a good idea to start coding anything that comes to mind.

Some comments talked about how competitive programmers write unmaintainable code or appear arrogant. Having lots of friends who are competitive programmers and read lots of comments here, I believe that these are also not the case.

• Yes, amongst rude comments made on Codeforces, many are from reds, but many are also from yellows, purples, blues, greens... and I think majority of high rated people here are very reasonable & nice.
• I think most people have some moments when we come back to read our old code writen in contests, and have no idea what we did. Since we've been there, it's not natural to think that we would write such code when we know that we need to maintain them.

I understand that the points I made above are probably biased. So what do you think? Do you believe that being good competitive programmer correlates negatively with being good on the job?

Below is very short description of solutions to problem that I can solve. Because it is "short description", for most problems, there is no proof of correctness. Proving the solutions is up to you.

100541A - Stock Market

This is the most simple problem in the set.

Observations:

• If you buy stock, you're better to buy as much as possible.
• If you buy stock on the i-th day, then you will always sell every stock on some j-th day, where j > i and the price of the stock on the j-th day is maximal.

Now we have an algorithm that runs in time O(N):

• Initialize f(i) to be the maximum value of the stock price from i-th day to N-th day.
• For each value of i from 1 to N, try to buy stock on i-th day, and find the value that you will sell these stocks using f(i+1).

100541B - Sum

Observation:

• There's only small number of different values of [N/i]. In fact, we can prove that there's only O(sqrt(N)) different values:

Using the above observation, we have a O(sqrt(N)) algorithm:

i = 1
result = 0
while i <= N:
    value = N / i
    last = N / value    // This is the last value such that (N / last) still equals to (N / i)
    result += (last - i + 1) * value
    i = last + 1
print result

100541C - ATM withdrawal

First, there's no solution when N mod 1000 > 0. After dealing with this, we can divide N by 1000.

Obvious (and wrong) greedy solution:

• Let u = N mod 10. Using notes 1, 2, 3, 5, pay u.
• Divide N by 10
• Repeat the above 2 steps for c+1 times.
• For the remaining values, pay using 5*10^c.

This greedy is wrong with the following test: N = 110 (after dividing by 1000), and c = 1. It calculate the number of ways to pay N value incorrectly. (correct answer is 2: 110 = 50 + 30 + 30 = 50 + 50 + 10, while the greedy will find 1).

But we can fix this greedy solution:

• Let t = the note with maximum value. Before applying the above greedy, we pay X notes with value t, where X = (N — t) / t.

100541D - Treasure Box

Observation:

• After at most 100 transformations, X mod 100 will become some value that we already seen.

In other words, the sequences of transformation will look like this:

 + a₁ + a₂... + a_i + b₁ + b₂... + b_k + b₁ + b₂... + b_k + b₁ + b₂... + b_k + ...

So we can group b₁, b₂, ..., b_k together, and calculate the result in O(k).

100541E - ACM

Observation:

• There is only small number of primes (36 primes) below 150.

Algorithm:

• Build 36 segment trees. Each node in the k-th segment tree stores the power of the k-th prime in the product of in the corresponding segment.
• Using the segment trees, we can update / query for each prime in time O(log(N)).

Traps:

• You must use long long
• MOD can be equal to 1

100541H - Pencil Game

Let i, j be the first and last column of the result sub-rectangle. Let u, v be the first and last row of the result sub-rectangle.

By using basic algebraic transformations, we have:

2 * L = (j - i + 1) * (v - u + 1) * (N * (u + v) + (i + j))

Let W = j - i + 1 and H = v - u + 1. Note that W * H is our solution.

Because the number of factors of an integer is small, we can loop through all possible values of W and H (first generate all factors of L, then consider only the factors of L). For each pair (W, H), we can uniquely find u and i, and check if it is indeed a valid solution.

100541I - Space Tour

This is a dynamic programming problem. Note that the 4 different paths do not have a common point, so we can consider them separatedly. Use 4 different dp functions to calculate the length of each 4 path.

For example, the path that initially go to left direction can be calculated this way:

for i = 1..M:
    for j = 1..N:
        if a[i][j] == 1:
            f[i][j] = 1
            if a[i-1][j] == 1:
               f[i][j] = f[i-1][j-1] + 2

After calculating the 4 dp functions, we can loop through each starting position (i, j) and calculate the result if we start at this position.

100541J - Math Magic

This is another dynamic programming problem.

Let f(i, x, y, z, t) be the maximum score you can get if you used some tiles 1..i, and the colors at the four directions are x, y, z, t.

From f(i, x, y, z, t), you can calculate all values of f(i + 1, x', y', z', t') by trying all possibilities of adding the (i + 1) - th tile to one of the four directions.

This solution is a bit slow to get accepted. You can try following optimizations:

• Only consider reachable states (i, x, y, z, t).
• Only consider states where x <= y <= z <= t.

Traps:

• Result can be negative

Hi everyone!

If you still remember, 5 months ago I added the ACM ICPC Vietnam National 1st Round into Gym.

This weekend, we're going to add the 2nd round from our National contest. We hope that this will help ease your hunger for contests :)

• The contest was designed to be harder than last time
• It consists of around 10 problems, and lasts for 5 hours.
• Teams are welcomed.
• Normal ACM rules is used.
• To those who's going to ask if it is rate): No contest from gym is rated.

The gym contest is prepared by laoriu, khuebeo, ngfam_kongu and me, I_love_Hoang_Yen. The problem setters are Vietnamese professors and some ex-ACM ICPC competitors.

We hope that there's going to be at least one interesting problem for everyone. Please join & have fun with us! May luck be with you :)

UPD: Contest is over. This is scoreboard of real contest: link

UPD2: Solution to some problems: link

UPD3: It turns out that the author's solution for problem F is wrong. I'm very sorry for that and I'm trying to fix it. I hope that it didn't make too much impact for any team. The bug was found by team Orz xyz111 (apia, PoPoQQQ1, alpq654323). You are really awesome, not only solve the problem, but solved it despite the fact that the test might be wrong.

UPD4: Solutions of F has been rejudged. It looks like the mentioned team was the only team who was affected. I am very sorry for that.

Hi,

Today I tried to solve 286C - Main Sequence, which required to read & print 10⁶ ints.

There are already many blog posts that compares performance of cin, cout (with ios::sync_with_stdio(false) of course) vs printf, scanf. And the test results shown that for ints, cin and cout are equally fast (and sometimes even faster) than scanf, printf. But my submissions do not agree:

• scanf + printf: 9881086 --> AC 966ms
• scanf + cout: 9881146 --> AC 1434ms
• cin + printf: 9881138 --> AC 1684ms
• cin + cout: 9882075 --> TLE

Note: I used cout << endl; in my submissions, but it prints endl only twice, so that should not be a problem here.

As you can see, except from input/output, my code is exactly the same. Am I doing anything wrong here?

UPD: I found another problem that cin/cout failed:

• My submission with cin/cout: 9919391
• A previously accepted code that use cin/cout but now got TLE: 9919511. This problem has warning "Package for this problem was not updated...", but the code doesn't use anything fancy, and also the printf/scanf version passed system test in 436ms (time limit is 1000ms). So I'm guessing that it is indeed because of cin/cout.

So, most likely, ios::sync_with_stdio(false); does not work well with the GNU C++ 4.9.2 which is used in Codeforces.

I'm not sure why, but I've received lots of messages today, from many different people..

Guy 1:

Guy 2:

Guy 3:

Guy 4:

Translation: Hi beautiful, what are you doing here looking so beautiful? This is obviously Google translated.

Thank you all, but I thought it would be clear from my account name I_love_Hoang_Yen that I'm a guy, and the girl in my avatar is my girlfriend :p (it's normal in my country to set your lover as avatar..).

P.S. my girlfriend is also on Codeforces ^_^ Not sure what she'll think when she sees this ^_^

100540A - Army buddies

Let's restate the problem statement:

• You need to maintain a set of alive soldiers.
• You are asked to perform some queries [L, R]: remove all soldiers with index in range [L, R]. And then find the soldier with maximum index which is still less than L, and the soldier with minimum index which is still greater than R.

The most simple way to implement this is to use C++ set. For each query:

• Find one soldier whose index is in range [L, R].
• Remove that soldier
• Repeat until there is no soldier in range [L, R].

This implementation runs in O(N * logN), because:

• For each soldier, he is only removed once from the set.
• For each query, if we remove k soldiers, we need to do binary search (lower_bound) on the set k+1 times. So the total number of times we binary search is at most N + Q.

Code

100540B - Ball Stacking

Consider the figure in the problem statement. In here we have 4 columns:

• Column 1: 3, -5, -8, 3
• Column 2: 3, 2, 9
• Column 3: -8, -2
• Column 4: 7

Consider a possible configuration of choosing balls.

Let's call the number of balls chosen for at each column x_i, where i = 1..N. In the example, we have:

• x₁ = 4
• x₂ = 3
• x₃ = 0
• x₄ = 0

It is easy to see that x₁ ≥ x₂ ≥ ... ≥ x_N.

From this observation, we have the following DP:

f(j, k) = maximum value, if we consider the first j columns, and at column j, we choose at least k balls.

f(j, k) = max(f(j - 1, k') + a(j, 1) + a(j, 2) + ... + a(j, k)) for k' ≥ k

Code

100540C - Candys Candy

You can read this comment. Thanks terribleimposter

100540D - Diccionario Portunol

To solve this problem, you must first know about trie.

First, construct 2 tries. One for prefixes of Portugese words, and the other for suffixes of Spanish words.

For example, in the first example, the prefix trie for Portugese words will contain:

• m, ma, mai, mais
• g, gr, gra, gran, grand, grande
• un, und, undo.

Note that I intentionally removed the prefix "m" of the 3rd word, because it is repeated.

After building 2 tries, you can see that the answer is "near" (size of trie 1) * (size of trie 2). I said near, because there are some words that were counted more than once, for example: "grande" = "g" + "rande" = "gr" + "ande" = "gra" + "nde" = ...

So you need to find how many words are counted more than once. This can also be solved using the tries we just built.

Let denote by + the string concatenation operation, and let a, b, x, y be strings and w be a character.

Consider Portugese words: a + w + x and b + w + y. We can easily see that for each non-empty string a and y, this word is counted at least twice. To count these duplication, we need to count how many pairs of (x, b) exists for each w. For each character w, this value equals to the number of suffix of Portugese words starts with w, times the number of prefix of Spanish words ends with w.

See my code for more details.

100540E - Electrical Pollution

Let's denote by F(x) the anomalies produced by generator at point(x, x).

I have not solved this, but I have the following idea:

• Create a graph. For each equation of the form: F(x) + F(y) = a, add edge between vertex x and y.
• For each connected component of the graph, choose one vertex z, and represents all F(x) = const - F(z). After doing this, for components with cycles, you should be able to get values of all F(x).
• To answer queries, just use the values of F(x) calcualted above.

Since I haven't implemented this idea, I'm not sure if I've missed something.

100540F - File Retrieval

This problem requires Suffix Array.

First of all, concat all the strings in input, separated by some unique characters (For example, use characters with ASCII code 1 to F).

Build Suffix Array on this string, and calculate LCP array.

Now, to count the number of searchable set, observe the following facts:

• For each searchable set, there's a keyword K for this set.
• This keyword K corresponds to a prefix of a suffix in our Suffix Array.
• It's transparent that the searchable sets have consecutive suffixes in our Suffix Array, where K is their prefixes. Because of this, the corresponding LCP of these will be at least |K|.

So, we can iterate through all searchable set, by iterating through K, but we must do this while keeping the following in mind:

• For each searchable set, there can be more than one K. They can be substring of each other. To avoid duplication, we must store all the searchable sets in a hash table (for example, use C++ set).
• When we iterate, we use Suffix Array. For each position, we consider it as having the smallest value of LCP in our set.

There are some more implementation details, and it is hard to explain everything here. Please refer to code.

Code

100540G - Garden Fence

This should be a sweep line problem. During contest, I've tried rotating the points, but it did not work (probably because the function we're calculating is not continuous, so rotating can not work well?)

100540H - Hedge Mazes

This is a graph theory problem. To solve this problem, you must be familiar with [bridges](http://en.wikipedia.org/wiki/Bridge_(graph_theory) ).

Let's say we need to answer query A B. Find an arbitrary path from A to B. Then, you can see that this path is unique, if and only if all the edges on the path are bridges of the graph. Proving this is a bit tricky, though it is easy to understand why this is correct:

• If one edge on the path is not bridge, you'll be able to construct another path from A to B.
• If all edges on the path are bridges, obviously, you have only one path.

Based on the above observation, you can solve the problem as follows:

• First, remove all edges of the graph which are not bridges.
• Then, use disjoint set (also known as DSU) to maintain the connected components in this new graph.

For each query, you just need to make queries on disjoint set to check if 2 vertices belong to same connected component of the new graph.

My code

100540I - In Braille

This is a straight-forward implementation problem:

• For instruction of type B, just compare the input with each Braille characters to find the corresponding digit.
• For instruction of type S, just print the Braille characters corresponding to each digit in input.

Since the size of input is small, any naive implementation should run in time.

Code

100540J - Jupiter Attacks!

In this problem, you are asked to perform two types of queries:

• Modify one element of array
• Calculate hash value of a subarray.

The most straight-forward way to solve this type of problem, is to use some Data structures that can handle range update & query. I used segment tree. If you are not familiar with it, you can read more here and here or at many other places on the Internet.

In addition to Segment tree, you need to know how to do combine the Hash values of 2 consecutive segments. Let's say you have segment [u, v] and [x, y] where v + 1 = x. If you know hash(u, v) and hash(x, y), you can calculate hash(u, y):

hash(u, y) = hash(u, v) * B^{y - x + 1} + hash(x, y).

You can read my code to see how I implemented this Segment tree.

100540K - Kings Poker

This is again an implementation. Though, you need to handle corner cases very carefully. One downfall is that each number cannot appear more than 4 times. Let's call the 3 numbers in input a, b, and c.

• if a = b = c: Then, if a = 13, there is no solution, otherwise, the optimal solution is set containing three a + 1.

• if a, b, c are pairwise distinct: You can use the smallest pair: 1 1 2. This works because no number can appear more than 4 times.

• The last case is where a, b and c forms a pair. For this case, I used brute-force to check for every pair. If no pair is greater than this pair, this pair must be 13 13 12, and you can use the set 1 1 1.

See my code for more details.

100540L - Gates

L & M solution will be updated if I can solve them.

100540M - Game

Today when I tried to solve a problem, I found that I'm getting Runtime Error because of using nextProbablePrime() and isProbablePrime().

See:

• Accepted submission: 8859588
• Runtime Error submission: 8859569

The only difference is in Accepted submission, I used my own nextProbablePrime().

Previously, I read on Codeforces that MikeMirzayanov solved this issue: /blog/entry/10037. Though looks like it is broken again.. :(

100534A - Abnormal Coins

This problem is the easiest amongst the problems. Since you need to choose different polygon types, the optimal way (meaning you would spend minimum amount of coins) is choosing polygon with sizes 3, 4, 5, 6, ... in this increasing order.

Code