I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, history, 12 months ago, In English

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:

Details of Official Contest:

Problems prepared by:

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

UPD: The problems are now on Open Kattis

Read more »

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

By I_love_Hoang_Yen, history, 13 months ago, In English

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:

Details of Official contest:

Problems prepared by:

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

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

Read more »

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

By I_love_Hoang_Yen, history, 2 years ago, In English

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.

Problems were prepared by:

Read more »

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

By I_love_Hoang_Yen, 2 years ago, In English

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 »

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

By I_love_Hoang_Yen, 3 years ago, In English

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:

Standing of real contest.

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

Read more »

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

By I_love_Hoang_Yen, 4 years ago, In English

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 »

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

By I_love_Hoang_Yen, 4 years ago, In English

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.

Read more »

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

By I_love_Hoang_Yen, history, 5 years ago, In English

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 »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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

Read more »

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

By I_love_Hoang_Yen, 6 years ago, In English

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 enot110
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 danilka.pro 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 bidzilya
NEERC Russia Northern (Arctic) Federal University CleRIC NVAL ?
NEERC Russia Moscow Aviation Institute yarrr mingaleg 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 etal
SWERC Switzerland ETH Zürich ? ? ?

Asia

Count Country/Region University Member 1 Member 2 Member 3
1 Vietnam University of Engineering and Technology — VNU I_love_tigersugar 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 BaconLi
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 lythanh _TMB_ Equanimity
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 meijun
20 Iran Shahid Beheshti University shamir0xe farzad.shbfn nima.sh
21 Japan The University of Tokyo semiexp phidnight EnumerativeCombinatorics
22 India Indian Institute of Technology Roorkee amankedia1994 kshitijbathla anubhav94
23 Hong Kong The Chinese University of Hong Kong Sampson alex20030190 Nezzar
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 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 old_arysson
6 Brazil Federal University of Pernambuco mhss Godely dcms2
7 Brazil Federal University of Bahia johnjq Roberio lbguilherme
8 Brazil University of São Paulo — SP yancouto gafeol gidelfino
9 Venezuela Universidad Simón Bolívar lmn0x4F 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 CarlosGoogles

Africa & the Middle East

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

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 ecnerwala stevenkplus betaveros
6 USA Carnegie Mellon University nhrubin bluepichu wxyxinyu
7 USA Cornell University saketh 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 sping128 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 SustainedScreaming
2 Australia University of New South Wales junkbot grundo SpiritsUnite

Read more »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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:

Screenshot

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 »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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 »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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

Screenshot

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 »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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 »

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

By I_love_Hoang_Yen, history, 6 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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.

Image and video hosting by TinyPic

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.

Image and video hosting by TinyPic

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.

Image and video hosting by TinyPic

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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

Read more »

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

By I_love_Hoang_Yen, 7 years ago, In English

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

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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

By I_love_Hoang_Yen, 7 years ago, In English

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 »

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