ko_osaga's blog

By ko_osaga, history, 4 days ago, In English,

Hi! In Korea Regional ICPC homepage, news about ICPC East Asia Pacific Semifinal has appeared. I didn't found any other articles about this, so I'll upload this to get some contribution.

There will be a semi-final competition in the East Asia-Pacific region between the Regional Contest and the World Final. The official title is undecided, but the semifinals will be held in Vietnam on December 21-23, 2020. Up to this year, we are selecting teams to advance to the world competitions, but starting next year, some will be selected at the regional competitions and some will be selected at the semifinals. Unlike the World Championships, the semifinals are expected to allow multiple teams, with an upper limit on the number of teams in each university. The East Asia-Pacific region includes Korea, Taiwan, Japan, Southeast Asia such as Vietnam, the Philippines and Indonesia, and Oceania such as Australia and New Zealand.

Original post

Great to see some fair team selection in East Asia!

Read more »

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

By ko_osaga, history, 7 days ago, In English,

Hello! I'm happy to announce XX Open Cup. Grand Prix of Korea.

List of relevant previous contests:

Enjoy!

Read more »

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

By ko_osaga, history, 4 weeks ago, In English,

From Friday 14:00 UTC+9 Korea Standard Time, I will stream solving ICPC World Finals 2018 J, Uncrossed Knight's Tour.

Stream link is https://www.twitch.tv/gs14004. Sorry for changing it from my previous account (I'm somehow unable to login with my previous account. I think it is hacked.)

I'll stream until I solve it, or I give up and sleep.

See you!

Read more »

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

By ko_osaga, history, 2 months ago, In English,

Hello!

International Olympiad in Informatics (IOI), the most prestigious programming contest in the world, is held in a beautiful city of Baku, Azerbaijan this year.

Wish the best luck to every contestant!

Day1: The contest had started on time, but the scoreboard is broken. It seems there is no mirror this year.

Day1 Contest Overview: Benq solved all Day1 problems in only 3.5 hours, congratulations! Full scorers for each tasks: 23(rect) / 170(shoes) / 6(split)

Day2 Contest Overview: The winner for Day2 is duality, but Benq still secures his consecutive IOI win. Congratulations! Full scorers for each tasks: 0(line) / 47(vision) / 2(walk)

Contest Results

  1. Benq 547.09
  2. 300iq 511.22
  3. duality 494.33
  4. TLE 491.46
  5. FizzyDavid 482.39

Country Ranking

  • 1 Russia 4G
  • 2 China 3G1S
  • 2 United States of America 3G1S
  • 4 Republic of Korea 2G1S1B
  • 4 Vietnam 2G1S1B

Congratulations to everyone who competed, and especially to our super awesome team gina0605 GyojunYoun onjo SebinKim !

Useful Links:

Read more »

Tags ioi
 
 
 
 
  • Vote: I like it
  • +195
  • Vote: I do not like it

By ko_osaga, history, 3 months ago, In English,

If there are any errors, please write it in the comment.

Rank CF Handle
1 Radewoosh Poland
2 ACRush China
3 Errichto Poland
4 aitch Sweden
5 V--gLaSsH0ldEr593--V Russia
6 cki86201 South Korea
7 ksun48 Canada
8 tourist Belarus
9 majk Czechia
10 qwerty787788 Ukraine
11 ecnerwala United States
12 marcin_smu Poland
13 zemen Russia
14 vepifanov Russia
15 yutaka1999 Japan
16 Um_nik Russia
17 Petr Russia
18 PavelKunyavskiy Russia
19 xyz111 China
20 ko_osaga South Korea
21 wxhtxdy China
22 ainta South Korea
23 maroonrk Japan
24 LHiC Russia
25 aid Russia

Read more »

Tags fhc
 
 
 
 
  • Vote: I like it
  • +105
  • Vote: I do not like it

By ko_osaga, history, 3 months ago, In English,

Hi all!

Did you know that SRM 763 is scheduled in 15:00 July 17, 2019 UTC+0? I didn't, and I bet you also didn't, so here is a helpful reminder.

Let's wait for hmehta to announce the writers.

And, don't forget the TCO19 Round 3B!

Read more »

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

By ko_osaga, history, 4 months ago, In English,

Hi! I was migrating KAIST RUN Spring Contest 2019 into CF Gym, and encountered following error:

For problem C, E, I made a copy of the original problem, as Gym system can't interpret test groups. Otherwise, they are all sane. They are packaged with verification, and user codeforces has write rights for all problems.

I believe this is beyond my scope to handle, MikeMirzayanov, could you please help?

Read more »

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

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

Update 2019/06/12: Me and MikeMirzayanov managed to upload the Div.2 contest into Gym. Huge thanks him for the great system, and also a kind help!

However, I decided not to just open it, but to give a training contest. The contest is scheduled in June 14 Friday, 09:00 UTC. Even considering some obvious bias from the setter, I'm personally very proud of the Div.2 contest :D I hope you participate and share the same joy with us! (and of course, please don't cheat!)

.

.

.

.

.

.

.

.

Update 2019/06/05: I managed to upload the Div.1 contest into Gym. Have fun! https://codeforces.com/gym/102201

Open Cup GP of Daejeon is scheduled at 2019/05/05 Sunday, 11:00 MSK. Daejeon is a city where KAIST is.

Division 1 problem set is identical with MIPT PreFinals Camp 2019 Day 6. It was held on March 15.

Division 2 problem set is identical with KAIST RUN Spring Contest 2019. It was held on May 1 locally. Like last year, it was an IOI-style contest, but as we are doing in OpenCup, subtask will be disabled. Some problems between Div1 and Div2 are shared.

Problems were created by ainta, InuyamaAoi, ko_osaga, kriii, kdh_9949. Some problems in Div1 were borrowed by Diuven, imeimi.

Problems were tested by arknave, dotorya, Namnamseo, tzuyu_chou, .o..

List of relevant previous contests:

Enjoy!

Read more »

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

By ko_osaga, history, 7 months ago, In English,

To jump on a bandwagon, I'll run a boring stream, where I'll virtual participate JOI Spring Camp 2019 Day2 (or Day1 if that's harder). The time will be 3/21 Thursday 7:30 PM UTC+9 (KST)

https://www.twitch.tv/koosaga

If this works out well, I'll maybe continue streaming after WF. I'll try to solve problems that is both hard and annoying, something like this.

See you!

Read more »

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

By ko_osaga, history, 11 months ago, In English,

Hmm.. Am I the only one not appearing in the scoreboard?!?

Read more »

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

By ko_osaga, history, 12 months ago, In English,

http://hsin.hr/coci

40 minutes left. Enjoy!

Read more »

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

By ko_osaga, history, 12 months ago, In English,

Update 2019/01/02: The problemset is finally uploaded to CF Gym. If you didn't participated before, this is a great chance to practice on one of Petr's best problem candidates. I hope you enjoy the contest. Happy New Year!

Division 1 Link

Division 2 Link .

.

.

OpenCup GP of Korea (third edition) is scheduled at 2018/10/14 Sunday, 11:00 MSK.

Both Div1 / Div2 problemset will feature Korean problems.

Problemsetters: ainta alex9801 Cauchy_Function HYEA jh05013 ko_osaga OnionPringles Togekiss .o.

Enjoy!

Read more »

Tags gp, of, korea
 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

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

Hello Codeforces!

In 2018/05/26 21:30 Korea Standard Time (UTC+9) we will hold an online mirror of 2018 KAIST RUN Spring Contest. This is an annual individual contest held by KAIST's algorithm club RUN.

Problems are available in English, and you should individually solve 11 problems in 5 hours. The problems will be prepared in Gym, so this contest is unrated. Grading rules are ICPC-style. There are no prizes in this contest, but if any top scorers come to KAIST, we will bring you to our favorite restaurants or pubs ( ͡° ͜ʖ ͡°)

This online mirror might not reflect the onsite contest fully, due to some technical limits. For example, the grading rules in main contests were IOI-style, every problems were 100 points with subtasks and we had no penalties, but we had some difficulties implementing it on CF environment :/

Problems were prepared by koosaga, HYEA, alex9801, etaehyun4, platinant. alex9801's rating is 2399, so he hopes to be called as "semi-red", not orange.

Special thanks to HYEA, who hoped to upload this contest to gym (and actually worked on it), and MikeMirzayanov, who is the maintainer of this great community and system!

In the online mirror for Korean participants (including some famous red/nutella coders), nobody was able to solve all problems — I challenge you to beat them! :D

The contest is now finished! Congratulation to winners!

  1. yjq_naive
  2. Reyna
  3. ulna
  4. gamegame
  5. the_art_of_war

Local open contest scoreboard

Tests, checkers, solutions (warning, over 400MB!)

Editorial

Problemsetters :

  • HYEA : P (Puyo Puyo), Y (Yut Nori)
  • ko_osaga : Q (QueryreuQ), T (Touch The Sky), U (United States of Eurasia), V (Voronoi Diagram), W (Winter Olympic Games), Z (Zigzag)
  • alex9801 : X (Xtreme NP-Hard Problem?!)
  • platinant : R (Recipe)
  • etaehyun4 : S (Segmentation)

Thanks to everyone who participated!

Read more »

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

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

Update 2018.11.01: Rezwan.Arefin01 made a very cool webapp which contains identical problemset, but with more usability. Thank you very much! You can check it here.

Note: There was some updates in 2018.10.05. See here for changes!

Hello! APIO 2018 is near the end, and IOI 2018 is in this September. I hope you are preparing it well!

I'm here to present my OI problem checklist :

I used this to train myself in IOI 2015~2016, and to train Korean IOI 2017 Team (probably 2018 too). For long it was in the "beta" phase, but I think it's now good enough to share!

This problemset contains about 300 ~ 400 hard and interesting problems, with appropriate judge links given. (If there is problem in judging, maybe ojuz can help that..)

Google Docs Link

I hope this can help anyone preparing for future OIs, and a complete answer to the question "How to excel at IOI-style contests" :D

Read more »

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

By ko_osaga, history, 18 months ago, In English,

Hello!

According to the official site, BOI 2018 will be held in this weekend. Good luck to all participants!

I wonder if the organizers are planning any online contests. I actually found this Kattis site, but I think this is for official participants. Any ideas?

Read more »

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

By ko_osaga, history, 19 months ago, In English,

WHERE IS IT?

Edit : Ok because of the delay we are unable to participate :/

Read more »

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

By ko_osaga, history, 19 months ago, In English,

No threads, so I decided to make it.

Let's discuss!

Read more »

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

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

World Codesprint 11 was held in May. They promised us to "expect 6~8 weeks" for prizes, and 7 months are passed. And I talked about this two times.

It's worth noticing that Bitcoin prices has become 5x from then.

Will I ever be able to receive their moneys someday? I don't want to participate in a contest where organizers don't keep up their promises.

Read more »

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

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

In a n x m chessboard with cells labeled (i, j) for 1 ≤ i ≤ N, 1 ≤ j ≤ M, there is a stone at (1, 1). A and B is playing a game.

A starts first, and they alternately move stone to adjacent cell (north / west / south / east). It's okay to move stones to previously visited cells, but it's prohibited to move stones to previously visited "edges". For example, if someone wants to move stone from (1, 1) -> (1, 2), they shouldn't have a record of visiting (1, 1) / (1, 2) or (1, 2) / (1, 1) cells consecutively. Player unable to make a move loses.

Who is the winner? 1 ≤ n, m ≤ 106

About 1 month ago, me and other guys tried to solve this problem but failed. I also googled about this problem, but wasn't able to find any resources about it :/ Here are some observations to share.

Hint originally written in statement
Observation 1
Observation 2
Observation 3
Observation 4

Could anyone help me to solve this?

Read more »

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

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

I never thought Kuhn-Munkres would strike me that hard...

How to solve F L? And what was intended for H?

Read more »

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

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

Round : https://www.facebook.com/hackercup/scoreboard/1799632126966939/

Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=2017%20Facebook%20Hacker%20Cup%20Finals&iso=20170614T1330&p1=234&ah=4

List of Participants : http://codeforces.com/blog/entry/50089

(Note that actual participants slightly differ from that list)

I'm pretty flattered for my first ever onsite competition (beside IOI) :D Good luck and have fun!

Read more »

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

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

I'm not a native English speaker, so I mostly learn English by books or internet. When I look up Collins English Dictionary about the meaning of "Editorial" :

"An editorial is an article in a newspaper which gives the opinion of the editor or owner on a topic or item of news."

That's something we call as "사설" in Korean. In Korea, people write editorial about our recent president impeachment, thoughts on foreign policies, or the Chinese food restaurant nearby their office. If someone uses that phrase to describe solutions, it will be really awkward.

In Codeforces, when we say "Editorial" it mostly means "Solution" — that is, mathematical facts. So, according to dictionary, this post is more likely to be called as "Editorial" than the usual one we know.

Then, why does CP community uses the word "Editorial" for referring solution? Does it have some other meaning related to "solution"? If not, is there some history for using that phrase?

Read more »

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

By ko_osaga, 3 years ago, In English,

Hello!

Recently I learned about FFT algorithm, and I was confused because of it's precision errors.

Suppose that I want to multiply two polynomials A(x) and B(x) modulo 10^9 + 7. (max degree <= 10^6) Then I have two options :

  • use NTT with modulo 119 * 2^23 + 1. With these I don't have to worry about precision errors, but I have to split the coefficients in something like (c0 + c1 * 32 + c2 * 32^2 + c3 * 32^3 .... c5 * 32^5). This is the best we can use, since if we use something over 32, (33-1) * (33-1) * 1000000 > modulo. So I have to split it into at least 6 pieces, which is horrible..

  • use FFT with complex numbers : Well... we don't have modulos, so I have to guess here. I've experimented with 10^6-digit long integers with all digits in 9. (basically I calculated (10 ** 1000000 — 1) ** 2) In first try, I grouped two digits together (coeff < 100), and it worked fine. In second try, I grouped three digits together(coeff < 1000) , which had precision errors. So I can guess that it will be okay to split under 100. Now 5 pieces. Which is... eh, improvement, but still horrible.

Regarding problem F in here or this (spoiler alert), It's clear that there is a demand for big modulos. However, grouping into something like 30 or 100 is not only dumb, but very slow and constant-heavy, and it should be avoided.

I concluded that NTT won't help me in this problem, and arrived in following questions :

  1. How can we estimate the precision error of FFT? (or, is there some kind of rule of thumb in here?)
  2. What is the common way to avoid this situation? Isn't there any other way than grouping with number lesser than sqrt(mod), or karatsuba?

FYI, this is the code used in my experiment : https://gist.github.com/koosaga/ca557138cabe9923bdaacfacd9810cb1

Read more »

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

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

After IOI, I was sorting out some APIO 2016 certificates for my schoolmates. But, umm... "Siver" medalist?

You should check if those kind of typo also happens to you :D

Read more »

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

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

http://www.spoj.com/problems/FAILURE/

Problem is simple : N points are given in Euclidean plane. For each points, you should find the smallest distance between itself and other points, in respect of euclidean distance.

I had no idea on the solution of this problem (except Delaunay triangulation. I hope there's a simpler solution), so I googled for the solution : https://github.com/anurag-jain/spoj-1/blob/master/MLE.cpp but I still have no idea why it's O(NlgN).

Can someone help me with this problem? T.T

Read more »

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