rng_58's blog

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

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

Contest Link

Contest Announcement

The point values will be 300 — 700 — 700 — 1000 — 1400 — 1600.

Let's discuss problems after the contest.

UPD: Now the editorial (check page 5) is ready.

I'll add some quick comments here.

A.

Spoiler

B.

Spoiler

C.

Spoiler

D.

Spoiler

E.

Spoiler

F.

Spoiler

Read more »

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

By rng_58, history, 12 days ago, In English,
x = 0;

while(x < 1){
    y = x;
    x += rand(); // returns a real number between 0 and 1, uniformly at random
}

What is the expected value of y?

It's not very hard, but the result is surprising.

Read more »

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

By rng_58, history, 2 weeks ago, In English,
CF Handle Country
1. kevinsogoPhilippines
2. touristBelarus
3. vepifanov (7 years in a row!)Russia
4. marcin_smuPoland
5. simonlindholmSweden
6. mnbvmarPoland
7. EndagorionRussia
8. drinklessRussia
9. -XraY-Russia
10. zemenRussia
11. semiexpJapan
12. SnukeJapan
13. SpyCheeseRussia
14. TeaPotRussia
15. SnapDragonCanada
16. ZloboberRussia
17. moejy0viiiiivChina
18. s-quarkChina
19. hogloidJapan
20. EgorRussia
21. KANRussia
22. AhyangyiChina
23. rng_58Japan
24. LHiCRussia
25. ifsmirnovRussia
26. ivan.popelyshevRussia
27. LewinUnited States
28. PavelKunyavskiyRussia
29. aitchSweden

Read more »

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

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

This year I haven't decided whether I'll participate (the flight won't be paid). Anyway, here is the top 25:

CF Handle Trip to Moscow
1. touristEasy
2. Um_nikEasy
3. rng_58Hard
4. krijgertjeMedium
5. W4yneb0tMedium
6. MilaninEasy
7. PetrEasy
8. dreamoonHard
9. EryxMedium
10. LHiCEasy
11. Alex_2oo8Easy
12. moejy0viiiiivHard
13. aidEasy
14. I_love_Tanya_RomanovaEasy
15. jcccccccccccccccccccccsbHard
16. fqwHard
17. shikHard
18. izbanEasy
19. maksayEasy
20. ilyakorEasy
21. SwistakkMedium
22. snukeHard
23. MicerenHard
24. mnbvmarMedium
25. KANEasy

Read more »

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

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

AtCoder Grand Contest 015 will be held on Saturday (time). The writer is DEGwer.

Contest Link

Contest Announcement

The point values will be announced later.

Let's discuss problems after the contest.

By the way, the writer is currently flying.

Read more »

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

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

1. Tsinghua (Win: 40%, Gold: 90%, Medal: 100% after some rounding)

  • CF max: 3441, 3203, 2967 (agg = 3516)
  • Open Cup: 1, 1, 11, 9 (median = 5)
  • China Final: 1
  • MIPT: 1, 1, 1, 2, 4, 1, 4

2. Warsaw (Win: 15%, Gold: 75%, Medal: 95%)

  • CF max: 3122, 2962, 2826 (agg = 3237)
  • Open Cup: 2, 3 (median = 2.5)
  • Petrozavodsk: 4, 2, 4, 3, 2, 2, 1, 2

3. SPb ITMO (Win: 15%, Gold: 50%, Medal: 90%)

  • CF max: 2880, 2870, 2860 (agg = 3104)
  • Open Cup: 7, 3, 2, 1, 13, 1, 2, 1, 3, 7, 13, 8, 8, 12, 3, 2, 1, 12 (median = 3)
  • Petrozavodsk: 4, 1, 3, 1, 6, 5, 3, 7, 5
  • MIPT: 6, 2, 3, 1, 5, 2, 1

4. SPb SU (Win: 10%, Gold: 40%, Medal: 85%)

  • CF max: 3170, 2951, 2936 (agg = 3281)
  • Open Cup: 9, 21, 18, 5, 3, 4, 9, 9, 6, 1, 2, 2, 7, 1, 4, 23, 20, 4 (median = 5.5)
  • Petrozavodsk: 7, 3, 6, 5, 8, 1, 4, 5, 1
  • MIPT: 2, 4, 2, 3, 1, 10, 8

5. Seoul (Win: 5%, Gold: 40%, Medal: 85%)

  • CF max: 3174, 2919, 2760 (agg = 3250)
  • Open Cup: 4, failed, 4 (median = 4)

6. MIPT (Win: 5%, Gold: 30%, Medal: 75%)

  • CF max: 2928, 2757, 2756 (agg = 3063)
  • Open Cup: 16, 29, 27, 28, 7, 24, 17, 15, 9, 15, 17, 3, 9, 4, 10 (median = 15)
  • Petrozavodsk: 1, 5, 5, 5, 1, 6, 6, 1
  • MIPT: 3, 6, 5, 4, 6, 3

7. MIT (Win: 5%, Gold: 30%, Medal: 75%)

  • CF max: 2900, 2637, 2540 (agg = 2981)
  • Open Cup: Equivalent to 2.5 in NAIPC

8. KTH (Gold: 10%, Medal: 60%)

  • CF max: 2761, 2637, 2273 (agg = 2870)
  • Open Cup: 2, 17, failed, 7 (median = 12)
  • MIPT: 5, 5, 16, 7, 7, 2

9. Fudan (Gold: 5%, Medal: 55%)

  • CF max: 2543, 2367, 2327 (agg = 2667)
  • Open Cup: 6, 13, 9, 6, 13, 18 (median = 11)
  • China Final: 5
  • MIPT: 12, 3, 7, 15, 13, 4, 5

10. New South Wales (Gold: 5%, Medal: 50%)

  • CF max: 3073, 2429, 2006 (agg = 3082)
  • Open Cup: 6, 8, 16 (median = 8)
  • MIPT: 14, 9, 10, 16, 2, 5, 7

11. Tokyo (Medal: 50%)

  • CF max: 2762, 2694, 2424 (agg = 2903)
  • Open Cup: 29, 5, 10, 12, 14, 29 (median = 13)
  • MIPT: 11, 10, 6, 8, 15, 6, 6
  • Barcelona: 1, 1, 1, 2, 3, 1, 1

12. SJTU (Medal: 50%)

  • CF max: 2707, 2609, 2582 (agg = 2874)
  • Open Cup: 26, 3, 18, failed, 21, 12, 10, 20, 26, 14 (median = 19)
  • China Final: 2
  • MIPT: 8, 7, 4, 10, 3, 9, 10

I won't be surprised if the following teams get a medal:

13. NTU (Medal: 45%)

  • CF max: 2772, 2341, 2220 (agg = 2808)
  • Open Cup: 11, 15, 21, 10, 2 (median = 11)

14. Waterloo (Medal: 45%)

  • CF max: 2925, 2908, 2703 (agg = 3100)
  • Open Cup: Equivalent to 12.5 in NAIPC
  • Barcelona: 3, 2, 4, 1, 1, 3, 2

15. Perm SU (Medal: 40%)

  • CF max: 3037, 2850, 2578 (agg = 3127)
  • Open Cup: 6, 18, failed, 3, failed, 9, 18, 7, 24, 15, 14, 16, 16, 7, 21, 16, 21, 17 (median = 16)
  • Petrozavodsk: 8, 12, 10, 14, 10, 10, 2, 6, 6
  • MIPT: 4, 8, 11, 5, 20, 7, 9

16. Peking (Medal: 40%)

  • CF max: 2920, 2566, 2338 (agg = 2965)
  • Open Cup: 21, 3 (median = 12)
  • China Final: 6

17. Helsinki (Medal: 35%)

  • CF max: 2721, 2280, 1516 (agg = 2745)
  • Open Cup: 15, failed, 9, failed, 16, 4, 17, 11, 30, 18, 2, failed, 8 (median = 16)
  • Petrozavodsk: 3, 26, 25, 11, 11, 7, 10, 2, 9
  • MIPT: 10, 16, 14, 6, 23, 17, 3

18. BSUIR (Medal: 30%)

  • CF max: 2825, 2625, 2466 (agg = 2943)
  • MIPT: 7, 13, 8, 11, 9, 13, 12

===

  • Expected win of top 7 = 0.95
  • Expected gold of top 10 = 3.75
  • Expected medal of top 18 = 11.05

And I guess Tokyo Institute of Technology will be around 25th, Keio will be around 40th.

Read more »

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

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

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

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1400 — 2400. Note that the contest duration is unusual (130 minutes).

Let's discuss problems after the contest.

Read more »

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

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

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

Let's discuss problems.

B is very nice. Until the end of the contest, I thought it was a marathon task. Then yutaka1999 told me the following: for an odd prime p, a[p] = 2 - p%4.

And I like geometry tasks like J.

Read more »

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

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

There are lots of important tournaments in this season, and we moved some AtCoder contests to avoid collision. Please check https://atcoder.jp/.

We'll add more ARC/ABCs in May.

Read more »

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

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

AtCoder Grand Contest 013 will be held on Saturday (time). The writer is maroonrk.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1600 — 2000. Note that the contest duration is unusual (150 minutes).

Let's discuss problems after the contest.

Read more »

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

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

AtCoder Grand Contest 012 will be held on Saturday (time). The writer is camypaper.

Contest Link

Contest Announcement

The point values are 300 — 700(200) — 1000 — 1000 — 1000 — 2000.

Let's discuss problems after the contest.

Read more »

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

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

Let's discuss problems.

Does anyone have an idea for D?

Read more »

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

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

There will be ARC 070 this Saturday, and interactive problems may be used there.

You can try an example of interactive problem on AtCoder here: https://practice.contest.atcoder.jp/tasks/practice_2

Here is my solution for 100 points:

#include <fstream>
#include <string>

using namespace std;

int main(void){
	int N,Q,i,j;
	
	scanf("%d%d", &N, &Q);
	
	string s;
	for(i=0;i<N;i++) s += (char)('A' + i);
	
	for(i=0;i<N;i++) for(j=0;j<N-1;j++){
		printf("? %c %c\n", s[j], s[j+1]);
		fflush(stdout);
		char ans;
		scanf(" %c", &ans);
		if(ans == '>') swap(s[j], s[j+1]);
	}
	
	printf("! %s\n", s.c_str());
	fflush(stdout);
	
	return 0;
}

Read more »

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

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

AtCoder Grand Contest 011 will be held on Sunday (time). The writer is semiexp.

Contest Link

Contest Announcement

The point values are 300 — 400 — 800 — 900 — 1300 — 1700 (?).

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 4 months 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  
  • +174
  • Vote: I do not like it  

By rng_58, history, 4 months 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, 4 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +91
  • Vote: I do not like it  

By rng_58, history, 5 months 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  
  • +106
  • Vote: I do not like it  

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

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

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

UPD: The contest is at https://www.facebook.com/hackercup/round/1799632126966939/.

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  
  • +194
  • Vote: I do not like it  

By rng_58, history, 5 months 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, 6 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +111
  • Vote: I do not like it  

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

Who is this?

Read more »

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