rng_58's blog

By rng_58, history, 11 days ago, In English,

Mujin Programming Challenge 2017 will be held on February 25th, 21:00 — 23:00 JST.

This is an online contest, and the top 30 people will be awarded prizes. The prize for the first place is $2000.

Please check the official site for details.

You will be asked to fill a questionnaire when you register, so please register at least several minutes before the contest.

UPD: Point values are 900(500) — 1300(300) — 1300 — 1800. The full scores correspond to C, D, E, F in AGC, and partial scores correspond to B, A.

Read more »

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

By rng_58, history, 12 days ago, In English,

If you are a contestant, you can be relaxed and you can do anything (except for cheating). It's perfectly fine if you just guess the solution and submit it without knowing why (though personally I don't find it very beautiful). However, if you are a writer, you need to prove your solution. Here is the list of things you have to prove:

1. Correctness.

Does your solution always return correct answers for all possible valid inputs?

  • GOOD: Strict proof.
  • BAD: My intuition tells that this is correct!
  • BAD: I tried really hard to come up with counterexamples, but I couldn't. It must be correct!

2. Time Complexity.

Does your solution always run in time for all possible valid inputs?

  • GOOD: It's O(n2) and the constraints say n ≤ 1000. It should work.
  • GOOD: For this problem we can prove that the slowest case is xxx. Experimentally, my solution works for the input xxx under the given TL.
  • BAD: I tried really hard to generate various testcases, and my solution passed all cases!

3. Randomized Algorithms.

Randomized algorithms are not hackish ways of solving problems. The writers should prove that for any valid input, the intended solution works correctly with very high probability. Please check here for an example of such proof. Another example is Rolling Hash: please check here. Note that, for example when we compute 105 hashes for strings of lengths 105, you need four hashes of prime modulo around 109, not two. (Practically two works but we can't prove that).

4. Precision.

Especially in geometry problems, we sometimes use epsilons. However writers should be careful about the use of epsilons.

  • GOOD: We know |b| and |d| are up to 104. Let's use eps = 10 - 9 for comparing two fractions a / b and c / d.
  • BAD: Let's use eps = 10 - 9! (without reasons)

When the intended solution uses complicated double operations (like sqrt, trigonometry, log, lots of fractions, etc.) such analysis may be hard. In this case, one possible way is to add constraints like "even if we move a point by up to 10 - 3, the answer doesn't change".

Read more »

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

By rng_58, history, 2 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +91
  • Vote: I do not like it  

By rng_58, history, 3 weeks ago, In English,

AtCoder Grand Contest 010 will be held on Saturday (time). The writer is yutaka1999.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 1000 — 1600 — 1600.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 3 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +140
  • Vote: I do not like it  

By rng_58, history, 4 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +89
  • Vote: I do not like it  

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

I barely qualified, so I do this again.

CF Handle Country
1. EgorRussia
2. scott_wuUnited States
3. RomaWhiteUkraine
4. PetrRussia
5. touristBelarus
6. jcccccccccccccccccccccsbChina
7. EryxPoland
8. ErrichtoPoland
9. qwerty787788Ukraine
10. dotoryaSouth Korea
11. TankEngineerChina
12. dreamoonTaiwan
13. peter50216Taiwan
14. Um_nikRussia
15. marcin_smuPoland
16. LhiCRussia
17. koosagaSouth Korea
18. KANRussia
19. RAVEmanUkraine
20. fhlasekCzech Republic
21. MerkurevRussia
22. -XraY-Russia
23. Al.CashUkraine
24. rng_58Japan
25. SergeyRogulenkoUnited States

Read more »

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

By rng_58, history, 5 weeks ago, In English,

AtCoder Grand Contest 009 will be held on Sunday (time). The writer is DEGwer.

Contest Link

Contest Announcement

The point values are 300 — 800 — 1100 — 1400 — 1600.

Note that the duration and the number of tasks is a bit unusual: 5 tasks in 2 hours.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 2 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +111
  • Vote: I do not like it  

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

Who is this?

Read more »

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

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

Sorry for late announcement, I completely forgot it.

AtCoder Grand Contest 008 will start soon! https://agc008.contest.atcoder.jp/

Read more »

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

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

Hello.

I'm planning to participate in a contest tonight. This is a team contest — and unlike ICPC, there is no limit to the number of computers. So, essentially this is an individual contest, and the score of a team is defined as the union of problems solved by the team members. I'm looking for my teammates in this contest.

The problem statements are provided only in Japanese. However, don't be afraid. If you become my teammate, I will describe the problems in English. (I may also solve a few problems myself, but I'm not sure).

The contest will start at https://www.timeanddate.com/worldclock/fixedtime.html?iso=20161224T22&p1=248, and the duration of the contest is 4 hours. If you are interested in it, please reply this post until 30 minutes before the contest (that is 80 minutes from now).

This is a non-serious contest, and I won't care the rank too much — the main purpose of this contest is to have fun. Some problems may be unusual.

Read more »

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

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

The onsite events of CODE FESTIVAL 2016 will start soon. I'll keep posting commentaries here. All times written here are Japanese Standard Time, which is UTC+9 or Moscow Time + 6.

[25th, Friday 21:25]

As the name of the contest may suggest, there are lots of events, including five contests:

  • CODE FESTIVAL 2016 Final

  • CODE FESTIVAL 2016 Exhibition

  • CODE FESTIVAL 2016 Elimination Tournament (3 rounds)

  • CODE FESTIVAL 2016 Relay

  • CODE FESTIVAL 2016 Grand Final

Some events are even overlapping so you have to choose one of them.

For those who can't attend the onsite events, there will be open contests. Please check the details at https://atcoder.jp/post/58 (here times are also written in JST). The Finals will start at Saturday 12:30, UTC+9.

[26th, Saturday 16:19]

Final Standings: https://cf16-final.contest.atcoder.jp/standings

The winner of Final is tourist. Congratulations!

The winner of Grand Final is W4yneb0t. Congratulations!

Read more »

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

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

Semifinal 1 will start in 43 minutes.

Broadcast: https://www.twitch.tv/topcoder_official

TCO Blog (I'm the blog writer): http://tco16.topcoder.com/blog/

Read more »

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

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

AtCoder Grand Contest 007 will be held on Saturday (time). The writer is doreamon.

Contest Link

Contest Announcement

The point values are 200 — 400 — 1000 — 1200 (600) — 1400 — 1500.

Let's discuss problems after the contest.

Read more »

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

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

AtCoder Grand Contest 006 will be held on Saturday (time). The writer is sugim48.

Note that this time the contest duration is 130 minutes (20 minutes longer than usual).

Contest Link

Contest Announcement

The point values are 200 — 400 — 800 — 1300 — 1500 — 1700.

Let's discuss problems after the contest.

Read more »

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

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

CODE FESTIVAL 2016 Qualification Round C will be held on Sunday Monday (time). The writer is sigma425.

Contest Link

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. Top 5 foreign students of this round will qualify. If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/code_fes_2016. Please check the detail of the tournament at http://codeforces.com/blog/entry/46647.

The contest duration is 2 hours, and there will be 5 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added one more problem and we hope this is interesting enough for choosing top 5 qualifiers. (Anyway, most probably the qualifiers will be determined by the speed of solving all problems). Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 400 — 800 — 1200. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

UPD: Fixed the date.

UPD: The top 5 were jcvb, w4yneb0t, AlexDmitriev, xyz111, and xyz2606. Congratulations!

UPD: Since wwwwodddd turned out to be a cheater, this account was excluded from the contest and banned from AtCoder. The qualifiers and the ratings were recomputed.

Read more »

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

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

CODE FESTIVAL 2016 Qualification Round B will be held on Monday (time). The writer is DEGwer.

Contest Link

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. Top 5 foreign students of this round will qualify. If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/code_fes_2016. Please check the detail of the tournament at http://codeforces.com/blog/entry/46647.

The contest duration is 2 hours, and there will be 5 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added one more problem and we hope this is interesting enough for choosing top 5 qualifiers. (Anyway, most probably the qualifiers will be determined by the speed of solving all problems). Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 500 — 700 — 1100. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

UPD: Among the top 5 foreign participants, Arterm has already qualified from round A, and matthew99, Reyna, Tachibana-Kanade are too young. Congratulations to Merkurev, polequoll, fqw, sevenkplus, and Zlobober! Note that this information is unofficial, and it is possible that some of them don't want to participate in finals (or ineligible).

Read more »

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

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

Let's discuss problems.

How to solve 8? I have no idea at all and finally decided to believe that we don't need nested addition/subtraction blocks, but it got WA. It seems there are harder cases.

How to solve 12? Essentially it reduces to the following: you are given a circle C and a point P. Find the movement of a point on C whose angular velocity is proportional to the distance from P. Is numerical integration accurate enough?

Read more »

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

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

AtCoder Grand Contest 005 will be held on Saturday (time). The writer is yosupo.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

Read more »

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

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

CODE FESTIVAL 2016 Qualification Round A will be held on Saturday (time). The writer is sugim48.

Contest Link

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. Top 10 foreign students of this round will qualify. If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/code_fes_2016. Please check the detail of the tournament at http://codeforces.com/blog/entry/46647.

The contest duration is 2 hours, and there will be 5 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added one more problem and we hope this is interesting enough for choosing top 10 qualifiers. (Anyway, most probably the qualifiers will be determined by the speed of solving all problems). Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 400 — 800 — 1200. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

UPD: Congratulations to tourist, endagorion, LHiC, Arterm, Kostroma, mmaxio, Um_nik, ainu7, malcolm, FatalEagle! (I don't know who is eligible and this is not the official information, please let me know if some of them won't come.)

Read more »

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

By rng_58, history, 6 months ago, In English,

Note: The contest was moved to Sunday in order to avoid collision with TCO Russia.

AtCoder Grand Contest 004 will be held on Sunday (time). The writer is sugim48.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 6 months ago, In English,

AtCoder Grand Contest 003 will be held on Sunday (time). The writer is DEGwer.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

Also, we've just announced Code Festival 2016!

Read more »

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

By rng_58, history, 6 months ago, In English,

We announce a new international onsite competition: Code Festival 2016. The contests will be held on AtCoder.

The top 20 foreign (non-Japanese) university students are invited to the Finals in Japan. (Even if you are not a student, you can participate in qualification rounds and parallel rounds of onsite contests. All of these contests are rated.)

The flight tickets and hotels for finalists are paid by organizers.

There will be three qualification rounds. Top 10 foreign students from round A and top 5 each from round B and C will qualify for the onsite contest.

Also, there will be many interesting events during the onsite competition.

More detailed information can be found at the official website.

Read more »

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

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

All testcases of atcoder problems will be posted here: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0

If you are interested in the rating system, please check rating.pdf at https://www.dropbox.com/sh/zpgcogxmmu84rr8/AADcw6o7M9tJFDgtpqEQQ46Ua?dl=0

Read more »

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