### I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, 6 weeks ago, ,

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.

Problems are prepared by:

Good luck & have fun!

Edit: contest will start in 7.5 hours.

Read more »

• +114

By I_love_Hoang_Yen, 13 months ago, ,

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:

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

Read more »

• +128

By I_love_Hoang_Yen, 2 years ago, ,

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 :).

Read more »

• +91

By I_love_Hoang_Yen, 2 years ago, ,

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, RR_PPAP, lythanh, beo_chay_so and some professors in Vietnam. The contest is uploaded to Kattis by prof.PVH.

Read more »

• +59

By I_love_Hoang_Yen, 2 years ago, ,

Yesterday I read ErdemKirez's blog and it reminded me of myself. I could not sleep for many hours last night thinking about all my failures in competitive programming and life. But now I think I survived, so I decided to write this..

## Backstory

When I started my years at school (age 5-6), I was different from other kids: I do weird stuff like remembering phone numbers and math.. On top of that, I was the smallest kid in the class. So obviously I became target for bullies. I still remember how it sucked being bullied and how it sucked more when I heard teacher told my mom about my bully: "Look at that sweet little girl, how can she be a bully?"

When I was in 2nd grade (Vietnamese edu system has 12 grades), a magical thing happened: I got highest score in my class. Suddenly the bullying stopped. I realized that when you are #1 and became teacher's favorite, you would not be bullied anymore. So I decided that I would always be #1 in my class.. That happened for few years until they introduced us with History and Geography.

Then when I was in 8th grade, the school needed some good student to participate in the City Olympiad in Informatics. So we were taught how to code in Pascal. I was enlightened: "Wow I can make the computer run programs, and do stuff with input and output magical things like ASCII arts :-O". Thus I started coding all day and entered City Olympiad in Informatics and won some prize.

## Highschool & National Olympiad

I managed to enter good high school. The entrance exams were Math and Vietnamese Literature but I made it! For competitive programming, we are probably the best high school in Vietnam, as we produced several IOI gold medalists like ll931110, skyvn97, natsukagami, etc.

I still coded all days in high school, but now I have friends from other National Olympiad teams to talk with about programming and algorithm. We had Yahoo at the time.

We had an OJ that had problems in Vietnamese: VOJ. As I coded all day I became #1 there in grade 11 and became quite famous: people started saying that I will go to IOI. Also I was in top 4 of National Olympiad, topped several online contests, so I was very confident.

Before I continue, I'll explain a bit more about how Vietnam select 4 students for IOI at my year (it was changed later): There are 2 rounds:

• National Olympiad. Top 30 qualified to next round.
• 1 day, 3 hours.
• 3 problems.
• No feedback.
• Time limit is not given. You should guess whether your code is fast enough.
• Score is equal to number of tests you get correct. Note that this is different from subtask in IOI. If you write greedy and it produced correct output for 99% tests, then you get 99% points.
• IOI team selection. Top 4 qualified to IOI.
• 2 days, 5 hours each.
• 3 problems per day.
• No feedback.
• Of course Time limit is not given. You should guess whether your code is fast enough.
• Score is equal to number of tests you get correct.

On the 1st day of the IOI team selection contest, I quickly read the 1st problem and found that it is a very simple Dijkstra problem. I started coding immediately (later the guy sat next to me wrote online "Crap, today I sat next to some crazy guy who started coding so fast and loud immediately after the contest start and I was so scared."). After I finished coding, of course it did not produce correct output for given sample. I draw the graph on paper and still had no idea how it can produce such output. Some guy in the contest hall asked the contest supervisor if the path can revisit the starting vertex and target vertex. The contest supervisor did not know. I was like WTF, but I realized that if I do that for the starting vertex then I can produce correct output. But I have no idea what to do with the target vertex. So it was like a 50% gamble. The other 2 problems were quite easy and had nothing special. After the contest I asked other contestants and it looks like amongst the 30 contestants I was the only guy who did not allow revisiting target vertex. F*ck.

So on 2nd day I was very scared and the 3 problems were much more difficult. I managed to solve 1st problem after 1 hour. I read both the other 2 problems, and found 3rd task impossible. So I spent all 4 hours coding 2nd task. It was very complicated task so I had bugs everywhere. After contest I asked other contestants and everyone solved 3rd tasks (after some reduction it became a simple problem with DFS tree) and no one solved 2nd task.

So of course I did not make it to IOI, but I still have 1 year left.

### Grade 12

This year I failed even more.

It started with the National Olympiad. I finished the first 2 problems quickly and had lots of time for 3 problem. I thought long and hard about that digit DP problem and found that it was very strange. If you read Vietnamese, it is this problem. I could not solve it, and later found that there was 9 people who solved it correctly and had perfect score. I was already scared and then I realized that I had integer overflow on my 2nd problem.

Anyway, I was still lucky and was the 30th guy who entered the IOI team selection contest. (there were like 10 people with same score as me, so I was actually 20-30).

On the 1st day of the contest, there were 3 easy problems. The 2nd problem had number of operation around 109 and it ran in around 5s, so I spent lots of time optimizing it (note that we did not know time limit). Later I found that they set time limit for 2nd problem to 10s, so no one got TLE. But for 1st problem they set time limit to something like 0.5s and everyone got TLE except for 1 or 2 guys who used heap instead of segment tree: time complexity is the same but constant factor is a little bit smaller.

On the 2nd day of the contest, I thought that since everyone had almost same score on 1st day, so I must try to solve 1 more problem than the others. Then I thought I was lucky when I read 1st problem of 2nd day: it was similar to a problem on VOJ that only I solved before. (For Vietnamese readers, it is this one ). I knew that in this problem it was a DAG instead of a tree and the cost function is max instead of sum, but I thought that I should be able to modify my old algorithm to work for this problem. Then almost 3.5 hours passed and I could not produce any working algorithm. I was so scared and I read other 2 problems, 2nd problem looked impossible and 3rd problem looked like a straight-forward but complicated one, so I started implementing it. I finished it in time but did not have time to test it (and of course there is no feedback during contests). I believed I made lots of bugs.. After contests I found that no one solved problems 1 and 2. Everyone solved 3rd problem, some wrote solutions for small cases of 2nd problem. No one touched 1st problem.

So of course I did not go to IOI, and it was all my fault. Programming was the only thing I was good at, the only thing that made me happy and I failed.

## University in ACM

I entered NTU Singapore for university. ktuan also study here. ktuan is the Vietnamese legendary competitive programmer: the only Vietnamese red target (while others have rating like <= 2500, he was > 3000), the only Vietnamese that went to GCJ Finals couple of time, and he also won #2 at FBHC Finals.

Anyway, couple of months before I entered university, ktuan asked me if I wanted to join his ACM ICPC team. He was very serious about getting ICPC medals so he wanted to start training immediately. I just failed IOI team selection so I wanted a break so I said no. Of course it is my most stupid "No" and I still regretted nowadays.

ktuan's team only got #17.

The following year I went to ICPC WF with my best friend ConanKudo, despite me making a bug in the regional when declaring array: I thought 20 * 30 = 60, so my arrays was obviously too small. In WF I was so scared of making stupid bugs and wrong algorithms again. Of course in ACM ICPC WF I made lots of stupid bugs, including: misunderstood the problem statement, integer overflow, implemented O(2N * N2) instead of O(2N * N) and got TLE, made wrong optimizations and got more WA. All of that for the easiest problem in the contest. You can see how many WAs I made for problem C here: WF 2012 scoreboard. Look at the top 20 and you can immediately see the guy who had +7. My teammates also performed badly and we only managed to solve 3 easy problems (B, C, D) after 3 hours of the contest. I felt so desperate almost cried. We went to WF hoping for medal and this is what I did.

Magically ConanKudo was able to calm me down and some magic happened so we were able to solve 3 more problems in the next 1.5 hours. "OMG maybe if we solve 1 more problem we can even get medal". But of course we did not have enough time for the implementation problem I and we only have some idea for problem A. We decided to code A anyway, filling what we could not solve with some stupid randomization and local search. Of course we did not solve it.

Again I felt so miserable. So far I failed on everything: not getting into IOI, failed in ICPC WF.

Then couple of months later my 1st girlfriend broke up with me.

I could not stand it. For several months I felt like hell. I tried not letting my emotion affect my life but some time even I realized that I was acting like a crazy psycho. That year I went to ACM regional with another friend technolt. Of course I failed regional again. And with my crazy behavior I wrecked my friendship with technolt and several other people too. I felt like I had no friend again. For a long time I woke up at 1pm or 2pm, went like a zombie to have lunch, went back home, do mostly nothing, had dinner, went back, do mostly nothing until like 4am.

In last week of November 2012, I felt that I was at the lowest point of my life. I felt so depressed. But there was no way my life could get any worse, so I thought that probably it can start getting better now.

I started dating Hoang Yen in early 2013 and it was a turning point in my life. But every time I logged in to CF it reminded me of all my failures, so some time in mid 2013 I decided that I hated my original account R_R_ so much that I created this account. (I know it was very wrong to have 2 accounts, and still use it sometimes, so I always feel very bad about it.).

## Last ACM

At some time during those sh*t happened, flashmt told me that a team that could not win regional should not hope for medal in ICPC WF. Probably it was true and my team in 2012 was quite weak that we were last team to qualify to WF in the regional. So I decided that I will participate in ICPC WF one last time with flashmt.

I got myself back to training, but there was a serious issue: flashmt and I were in different university. So I decided that I will study part time in NUS (National University of Singapore) to participate 1 last time with flashmt. We got another IMO medalist to join our team and went to WF.

I trained for 2 years with flashmt with the help of the current best Vietnamese competitive programmer RR_PPAP. It made me felt in love with contests again. Of course we did not win an ACM ICPC WF Medal but I felt that it was OK. Those 2 years training taught me lots of things, including dealing with failures. I realized that our trainings were more fun and more meaningful than the medal itself.

These days I have not been participating in contests — I'll get married end of this year so I feel like busy all the time. But I lost my red rating in last contest and I know that I will be back to get it back. Contests is a part of my life that I can't live without.

Read more »

• +353

By I_love_Hoang_Yen, history, 3 years ago, ,

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.

Read more »

• +104

By I_love_Hoang_Yen, history, 4 years ago, ,

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 tutanjokersharp. I inherited the spirit from ktuan by hearing stories about him, and ConanKudo and tutanjokersharp trained me to this level :)

Read more »

• +458

By I_love_Hoang_Yen, 4 years ago, ,

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

Region Country University Member 1 Member 2 Member 3
NEERC Russia Ural Federal University Um_nik Umqra Merkurev
NEERC Russia SPb State University Copymaster -XraY- ershov.stanislav
NEERC Russia Moscow Institute of Physics and Technology ifsmirnov Arterm zemen
NEERC Russia Moscow State University Zlobober sankear malcolm
NEERC Russia SPb ITMO University subscriber antonkov enot.1.10
NEERC Russia Nizhny Novgorod State University vepifanov KAN mike_live
NEERC Belarus Belarusian SU of Information and Radioelectronics teleport netman andrew.volchek
NEERC Russia Saratov State University Edvard dans kuviman
NEERC Russia SPb Academic University Nikitosh ComradePetr egor_bb
NEERC Russia Innopolis University savinov sokian map
NEERC Belarus Belarusian State University kostya_by shef_2318 IFLED
NEERC Russia Moscow Engineering Physics Institute Avitella Elshiko bdzl
NEERC Russia Northern (Arctic) Federal University CleRIC NVAL ?
NEERC Russia Moscow Aviation Institute yarrr shhdup Timus
CERC Poland University of Warsaw Swistakk Marcin_smu mnbvmar
CERC Poland University of Wrocław bardek Solaris matix2267
CERC Poland Jagiellonian University noh4h_ss krismaz zaj
CERC Slovakia Comenius University jablko baklazan michal27
CERC Croatia University of Zagreb IvL Mihaell ?
CERC Czech Republic Charles University in Prague Shulik simsa.st zaspagety
NWERC Finland University of Helsinki Laakeri Gomhog gtrrebel
NWERC United Kingdom Imperial College London dancho eudanip mihaipopa12
NWERC Netherlands Utrecht University Philae TimonKnigge RarebitFiend
NWERC Netherlands Radboud University ? ? ?
SEERC Ukraine Zaporizhzhya National Technical University 6eJIa9IzZzTeHb Life_is_good MrDindows
SEERC Ukraine Lviv National University RomaWhite witua Trumen
SEERC Ukraine Taras Shevchenko National University of Kyiv Furko Fdg mgch
SWERC Spain Universitat Politècnica de Catalunya albertnez angargo FerranAlet
SWERC Switzerland ETH Zürich ? ? ?

# Asia

Count Country/Region University Member 1 Member 2 Member 3
1 Vietnam University of Engineering and Technology — VNU skyvn97 kien_coi_1997 dnk
2 Singapore National University of Singapore I_love_Hoang_Yen flashmt nguyenhungtam
3 Bangladesh Jahangirnagar University nfssdq ndatta raihatneloy
4 Iran Islamic Azad University of Mashhad soshika Elk-Cloner yoones.rezaei
5 China Tsinghua University s-quark zhj dhh1995
6 China Shanghai Jiao Tong University TankEngineer rowdark AngryBacon
7 China Peking University lydrainbowcat sy2006 ?
8 China Beihang University sd0061 chffy InheritG
9 China Zhejiang University Sfiction J.T.J.L. Yukine_Chris
10 Iran Sharif University of Technology Haghani JeBeK matrix
11 Bangladesh North South University faiyaz26 forthright48 hasib
12 China Zhejiang Normal University ZJiaQ love_master qs1994
13 Vietnam Ho Chi Minh City University of Science binhminh410 _TMB_ PhuongUyen
14 Korea Korea University Myungwoo Cauchy_Function dlehdgh
15 Taiwan National Chiao Tung University aaaaajack leopan0922 lclan
16 Bangladesh Shahjalal University of Science & Technology Corei13 PlausibleDeniability J-C
17 China Beijing University of Posts and Telecommunications hiyot wzt_000 beegerous
18 China Tianjin University 452660407 wu6shen jinzhao
19 China Shanghai University curs0r fraud shu_mj
20 Iran Shahid Beheshti University shamir0xe farzad.shbfn nima.sh
21 Japan The University of Tokyo semiexp phidnight wolf_sothe
22 India Indian Institute of Technology Roorkee amankedia1994 kshitijbathla anubhav94
23 Hong Kong The Chinese University of Hong Kong Sampson alex20030190 CantGetAnyACWhyAmISoWeak
24 Philippines Ateneo de Manila University kylesky Hikari9 derpidc
25 China Fudan University flydutchman czy941030 Phronesis
26 India Indian Institute of Technology — Bombay harrypotter192 venkat82 nikhilvyas
27 India Indian Institute of Technology Kanpur Team alecsyde sahilgrover abhilak
28 India Indian Institute of Information Technology Allahabad shiva_r31 aditya_kakarot m17
29 Taiwan National Taiwan University step5 darkhh meteor
30 Japan Osaka University __math kyuridenamida ustimaw
31 Japan University of Aizu zukky sate
32 Japan Kyoto University asi1024 takise ojjiy5

# Latin America

Count Country University Member 1 Member 2 Member 3
1 Cuba Universidad de la Habana SandorGarcia Norge_V_Z abelramos
2 Brazil State University of Campinas augustomorgan ivanilos tiagob.reis
3 Argentina Universidad de Buenos Aires fredy10 miguelmaurizio SebP
4 Brazil University of São Paulo — SC bssanches tomasf danft
5 Brazil Federal University of Campina Grande fsouza manoel arysson
6 Brazil Federal University of Pernambuco mhss Godely dcms2
7 Brazil Federal University of Bahia johnjq rsalesc lbguilherme
8 Brazil University of São Paulo — SP ItsYanBitches gafeol gidelfino
9 Venezuela Universidad Simón Bolívar pulgares rubmary mathiassm
10 Mexico Escuela Superior de Cómputo galloska adonais ChOmPs
11 Peru Universidad Nacional de Ingeniería josue.0 dmansilla07 Victoralin10
12 Cuba Universidad de Oriente bestard epascual ?
13 Argentina Universidad Nacional de Rosario karupayun martinv mariano22
14 Mexico ITESM Campus Monterrey Diego1149 fredy.altamirano Carlos_Googles

# Africa & the Middle East

Count Country University Member 1 Member 2 Member 3
1 Egypt Alexandria University naggar AmrMahmoud OmaaarZ
2 Jordan Princess Sumaya University for Technology 2Nodes wentmay AU.Bahosain
3 Egypt Cairo University — FCI ziad.mohamed Baby_Steps Mohammad_Yasser
4 Syria Aleppo University kingofnumbers ? ?
5 Syria Tishreen University samiemad nodar963 majd.gda1
6 Syria Damascus University muaz-32 joudzouzou ?

# North America

Count Country University Member 1 Member 2 Member 3
1 USA University of Central Florida edorundo mkirsche sroyal
2 Canada University of Waterloo y0105w49 azneyes zxqfl
3 USA Virginia Tech PeterASteele pho ChrisWu
4 USA Harvard University scott_wu dnkywin random.johnnyh
5 USA Massachusetts Institute of Technology ecnerwal stevenkplus betaveros
6 USA Carnegie Mellon University nhrubin bluepichu wxyxinyu
7 USA Cornell University socketnaut victoreis JRossS
8 USA Stanford University superpear ? ?
9 USA California Institute of Technology agural ChingYunH sdhpzhtk
10 USA Rice University tuna_salad ? ?
11 USA University of Illinois at Urbana-Champaign NarakJung TiChuot97 victor_gaoxin
12 USA University of Wisconsin — Madison toppykung Ingkarat name
13 USA University of Southern California GodDammit JustindCheng windsfantasy6

# South Pacific

Count Country University Member 1 Member 2 Member 3
1 Australia The University of Western Australia gozzardam YouCantHandleMe
2 Australia University of New South Wales junkbot grundo SpiritsUnite

Read more »

• +402

By I_love_Hoang_Yen, history, 4 years ago, ,

UPD: I changed file extension from jpg --> png and it worked. Thanks sarvagya3943, 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? :(

Read more »

• +32

By I_love_Hoang_Yen, history, 4 years ago, ,

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?

Read more »

• +28

By I_love_Hoang_Yen, history, 4 years ago, ,

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

Read more »

• +37

By I_love_Hoang_Yen, history, 4 years ago, ,

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.

Read more »

• +142

By I_love_Hoang_Yen, history, 5 years ago, ,

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 the validator was written for the 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++) {
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() which does some magic in the background, so that you can use the necessary methods.

Read more »

• +182

By I_love_Hoang_Yen, 5 years ago, ,

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, ...

Read more »

• +563

By I_love_Hoang_Yen, 5 years ago, ,

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.

Read more »

• +33

By I_love_Hoang_Yen, 5 years ago, ,

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?

Read more »

Announcement of Easy One

• +380

By I_love_Hoang_Yen, 5 years ago, ,

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:

+ a1 + a2... + ai + b1 + b2... + bk + b1 + b2... + bk + b1 + b2... + bk + ...

So we can group b1, b2, ..., bk 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

Read more »

• +17

By I_love_Hoang_Yen, 5 years ago, ,

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, beo_chay_so, langtrunghieu 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, PoPoQQQ, 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.

Read more »

• +225

By I_love_Hoang_Yen, 5 years ago, ,

Hi,

Today I tried to solve 286C - Main Sequence, which required to read & print 106 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:

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.

Read more »

• +51

By I_love_Hoang_Yen, 5 years ago, ,

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 MLGuy 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 ^_^

Read more »

• +145

By I_love_Hoang_Yen, 5 years ago, ,

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 xi, where i = 1..N. In the example, we have:

• x1 = 4
• x2 = 3
• x3 = 0
• x4 = 0

It is easy to see that x1 ≥ x2 ≥ ... ≥ xN.

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 sandyeep

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) * By - 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

Read more »

• +67

By I_love_Hoang_Yen, 5 years ago, ,

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

See:

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.. :(

Read more »

• +44

By I_love_Hoang_Yen, 5 years ago, ,

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

Read more »

• +47

By I_love_Hoang_Yen, 5 years ago, ,

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, tuananh93, sillyboy
2. Alacrity (NUS, Singapore) flashmt, giongto35, yoh149
3. TaiDaJiaYou (NTU, Taiwan)
4. Java# (VNU, Vietnam) net12k44, VVan, ntit_co1
5. DCM (NUS, Singapore) infrmtcs, rais.fathin38, zeulb
6. .NET (VNU, Vietnam) Deception, tsunayoshi, meodorewan
7. Sanity’s Eclipse (SJTU, China)

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

My comments during the contest

Read more »

• +19

By I_love_Hoang_Yen, 5 years ago, ,

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?

Read more »

• +13