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

Let's discuss problems after the contest.

Also, we've just announced Code Festival 2016!

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3673 |

3 | Um_nik | 3493 |

4 | apiadu | 3397 |

5 | 300iq | 3317 |

6 | maroonrk | 3250 |

7 | Benq | 3230 |

8 | LHiC | 3229 |

9 | TLE | 3223 |

10 | ecnerwala | 3216 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 192 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 168 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 162 |

9 | 300iq | 155 |

10 | rng_58 | 153 |

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

Let's discuss problems after the contest.

Also, we've just announced Code Festival 2016!

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.

- Round A: September 24th, 21:00 JST.
- Round B: October 10th, 13:00 JST.
- Round C: October 23rd, 21:00 JST.
- Onsite Round: November 26th-28th

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

More detailed information can be found at the official website.

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

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

Let's discuss problems after the contest.

UPD: Thank you for participation. Editorial (English at the bottom)

AtCoder Grand Contest 001 will start soon (time).

Note that you need to click the blue button here to register.

Let's discuss problems after the contest.

**The contest duration is changed to 110 minutes.**

The contest has finished. How was the contest?

Congratulations to cgy4ever for winning!

Editorial: https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf (English is at the bottom)

**UPD: The rating is updated.**

Hello!

We made a new programming contest website called AtCoder. I'm the admin of AtCoder.

The first international contest called AtCoder Grand Contest 001 will be held on this Saturday (Time), and we are planning to hold a lot of contests regularly. This time the problems were written by snuke. We invite you to participate in our contests!

See AtCoder's Website for detailed information.

CF Handle | Country |
---|---|

1. xyz111 | China |

2. kevinsogo | Philippines |

3. tourist | Belarus |

4. TooDifficuIt | China |

5. ksun48 | Canada |

6. eatmore | Russia |

7. yosupo | Japan |

8. ffao | Brazil |

9. simonlindholm | Sweden |

10. marcin_smu | Poland |

11. s-quark | China |

12. gs12117 | South Korea |

13. mnbvmar | Poland |

14. xllend3 | China |

15. Savlik5 | Czech Republic |

16. semiexp | Japan |

17. rng_58 | Japan |

18. jcvb | China |

19. andrewzta | Russia |

20. Merkurev | Russia |

21. Nore | France |

22. scott_wu | United States |

23. Arterm | Belarus |

24. wuzhengkai | China |

25. Xhark | South Korea |

26. pashka | Russia |

I was an admin of TopCoder for about 4 years. Recently I came back as a competitor and I participated in four SRMs. Here are my performances:

It was an easy DP, but I started to implement something stupid and wasted time. When I finished coding around 5 minutes before the end of the contest, the server was slow and I couldn't compile my solution. Though the match was unrated, I should have solved it earlier.

My solution failed because of precision errors (in Linear Programming). I should have used long doubles instead of doubles (and passed in the practice room).

Failed systest because of two (!) stupid mistakes: incorrect array size and integer overflow.

Missed cases with a.size() == 1. Failed systest again.

It's really important to keep participating in TopCoder matches. Now I can't solve anything!

CF Handle | Country |
---|---|

1. bmerry | South Africa |

2. Petr | Russia |

3. TooDifficuIt | China |

4. rng_58 | Japan |

5. AlexDmitriev | Russia |

6. Um_nik | Russia |

7. I_love_Hoang_Yen | Vietnam |

8. eatmore | Russia |

9. Al.Cash | Ukraine |

10. snuke | Japan |

11. ACRush | China |

12. kcm1700 | South Korea |

13. scott_wu | United States |

14. uwi | Japan |

15. Merkurev | Russia |

16. doreamon | Taiwan |

17. simonlindholm | Sweden |

18. kelvin | Taiwan |

19. KAN | Russia |

20. azukun | Russia |

21. Zlobober | Russia |

22. yosupo | Japan |

23. krismaz | Poland |

24. yeputons | Russia |

25. Shik | Taiwan |

If you think the new website is difficult to use, please bookmark this post.

https://www.topcoder.com/members/YOUR_HANDLE_HERE/details/?track=DATA_SCIENCE&subTrack=SRM

Profile: https://competitiveprogramming.info/topcoder/handle/YOUR_HANDLE_HERE

*One day you came up with a brilliant solution during a contest, implemented it very carefully, and submitted it confidently. The verdict was ...... WA.*

Probably most of you have experienced this sad situation. You can start debugging if you know the reason of WA, but what do you do otherwise? I frequently have trouble with this situation, so I'd like to ask your opinion. What should we do when we get WA?

Here are several possibilities:

**1. Reread your code.**

This is the simplest way of debugging. You may find some stupid typos.

**2. Try various manual testcases.**

Examples may not be very strong. Try some small tricky cases against your code.

**3. Recheck the correctness of your algorithm.**

Have you proved your solution? Is the proof correct?

**4. Reread the statement.**

You may have misunderstood the statement. Read it again to make sure that you understood the task correctly.

**5. Stress-testing.**

Write a straightforward solution, create lots of testcases by yourself, and compare both solutions. This is a very strong way to debug your solution, but time consuming.

**6. Change the coder.**

When you compete as a team, ask someone else to solve the problem instead.

**7. Doubt the judge.**

Judges are humans. They are not 100% correct.

**8. Give up.**

You may have other tasks to solve. Simply give up the current task and try something else.

GCJ will start in less than 24 hours.

Live Stream: https://www.youtube.com/watch?v=rh_EYIu7Ztc

Unfortunately I don't have time to edit this table, but rowdark will participate, and izrak won't.

Participants:

GCJ Handle | Country | CF Handle | CF Rating | TC Handle | TC Rating | R2 Rank | R3 Rank | Previous Finals |
---|---|---|---|---|---|---|---|---|

Gennady.Korotkevich | Belarus | tourist | 3503 | tourist | 3766 | 1 | 3 | 2014 (1st) |

vepifanov | Russia | vepifanov | 2963 | Kankuro | 3232 | 33 | 10 | 2011 (8th), 2012 (4th), 2013 (17th), 2014 (8th) |

qwerty787788 | Russia | qwerty787788 | 2947 | qwerty787788 | 2899 | 24 | 20 | |

rng..58 | Japan | rng_58 | 2941 | rng_58 | 3468 | 3 | 1 | 2010 (7th), 2011 (1st), 2012 (19th) |

yeputons | Russia | yeputons | 2783 | yeputons | 3092 | 103 | 19 | |

Merkurev | Russia | Merkurev | 2758 | Merkurev | 2546 | 39 | 21 | |

bmerry | South Africa | bmerry | 2722 | bmerry | 3295 | 60 | 11 | 2008 (3rd), 2009 (10th), 2010 (21st), 2012 (6th) |

peter50216 | Taiwan | 0O0o00OO0Oo0o0Oo | 2637 | peter50216 | 2974 | 2 | 24 | |

TankEngineer | China | TankEngineer | 2634 | OierRobbin | 2636 | 23 | 26 | |

AngryBacon | China | AngryBacon | 2619 | AngryBacon | 62 | 16 | ||

tkociumaka | Poland | tomasz.kociumaka | 2613 | tom612pl | 2717 | 8 | 2 | |

dzhulgakov | Ukraine | dzhulgakov | 2607 | dzhulgakov | 3168 | 142 | 14 | 2008 (44th), 2009 (5th) 2012 (9th), 2013 (13th), 2014 (9th) |

simonlindholm | Sweden | simonlindholm | 2570 | 20 | 8 | |||

semiexp. | Japan | semiexp | 2507 | semiexp | 3005 | 6 | 27 | |

pashka | Russia | pashka | 2488 | pashka | 2862 | 11 | 15 | 2008 (84th), 2009 (17th), 2010 (8th), 2011 (7th) |

ishraq | Australia | izrak | 2482 | izrak | 2086 | 85 | 18 | |

betaveros | Taiwan | betaveros | 2463 | betaveros | 2181 | 384 | 17 | |

Romka | Belarus | Romka | 2452 | _Romka_ | 2474 | 446 | 28 | 2014 (10th) |

iwi | Japan | iwiwi | 2427 | iwiwi | 3100 | 7 | 6 | 2008 (59th), 2010 (9th), 2014 (15th) |

tczajka | Poland | tomek | 2393 | tomek | 3204 | 18 | 7 | 2003 (4th), 2004 (4th), 2006 (6th) |

JAPLJ | Japan | wrong | 2367 | wrong | 2465 | 67 | 22 | 2013 (23rd) |

wuzhengkai | China | wuzhengkai | 2343 | wuzhengkai | 2575 | 135 | 23 | 2014 (23rd) |

fagu | Germany | fagu | 2306 | fagu | 2259 | 126 | 12 | |

kevinsogo | Philippines | kevinsogo | 2236 | kevinsogo | 136 | 9 | ||

Xhark | South Korea | Xhark | 2132 | Xhark | 1677 | 35 | 4 | |

linguo | UK | linguo | 36 | 5 | 2008 (74th), 2010 (22nd), 2011 (22nd) |

Recently IMO 2015 has ended. Problem 6 was the hardest one and solved by only 11 contestants, but for competitive programmers this task wasn't that hard. If you are interested in it, I think it's worth trying even if you haven't solved any IMO problems.

The problem statement is here.

I wrote some hints in white characters.

Hint 1: How is it related to competitive programming?

Hint 2: Doesn't it look like bitmask DP?

Hint 3: Run the following program.

*mask* = 0;

for(*i*=1;;*i*++){

*mask*» = 1;

*mask*| = (1«(*a*_{i} - 1)); // here the newly set bit must be 0 before this operation

}

Hint 4: The number of '1' bits in *mask* is non-decreasing while the program is running.

So, the number of '1' bits will be constant at some moment: call it *b*.

Then, the sum of (*a*_{j} - *b*) is the difference of sum of positions of set bits in *mask* when *i* = *m* and *i* = *n*.

I'm currently at the airport now, and I have some free time before boarding. Here's my prediction of this year's WF:

- SPb ITMO
- Moscow SU
- U Zagreb
- Tsinghua
- MIT
- U Tokyo
- U Warsaw
- Lviv NU
- Shanghai Jiao Tong
- Jagiellonian
- SPb SU
- University of California at Berkeley

After the contest, let's see if my predictions are good :)

Among top 25 participants of round 3, 23 are in the finalists group. Here are their handles:

Name | Country | TC Handle | CF Handle |
---|---|---|---|

Gleb Evstropov | Russia | GlebsHP | GlebsHP |

Ryuta Kawai | Japan | anta | anta |

Jakub Pachocki | Poland | meret | meret |

Gennady Korotkevich | Belarus | tourist | tourist |

Alexey Shmelev | Russia | ashmelev | ashmelev |

Michael Kever | Russia | mikhailOK | cerealguy |

Евгений Капун | Russia | eatmore | eatmore |

Petr Mitrichev | Russia | Petr | Petr |

Makoto Soejima | Japan | rng_58 | rng_58 |

Borys Minaiev | Russia | qwerty787788 | qwerty787788 |

Marek Sokołowski | Poland | mnbvmar | mnbvmar |

Fernando Fonseca | Brazil | ffao | ffao |

Won-seok Yoo | South Korea | ainu7 | ainu7 |

Gaoyuan Chen | China | cgy4ever | cgy4ever |

Artem Rakhov | Russia | RAD. | RAD |

Robbin Ni | China | OlerRobbin | TankEngineer |

Ikumi Hide | Japan | tozangezan | tozangezan |

Mikhail Mayorov | Russia | 2rf | mmaxio |

Nicholas Jimsheleishvili | Georgia | nika | ? |

Dmytro Soboliev | Ukraine | sdya | sdya |

Yanpei Liu | China | ? | AngryBacon |

Chan Min Kim | South Korea | kcm1700 | kcm1700 |

Alexander Milanin | Russia | Milanin | Milanin |

In this problem you just need to implement what is written in the statement. Make a variable that holds the position of Liss, and simulate the instructions one by one.

The optimal path of Liss is as follows: First she starts from the root of tree 1. Walk up the tree to the top and eat a nut. Walk down to the height *min*(*h*_{1}, *h*_{2}). Jump to the tree 2. Walk up the tree to the top and eat a nut. Walk down to the height *min*(*h*_{2}, *h*_{3}), ... and so on.

In this problem, there are many simple algorithms which works in *O*(*n*). One of them (which I intended) is following:

You should prepare 2 vectors. If *s*[*i*] = '*l*', you should push i to the first vector, and if *s*[*i*] = '*r*', you should push i to the second vector. Finally, you should print the integers in the second vector by default order, after that, you should print the integers in the first vector in the reverse order.

This algorithm works because if Liss divides an interval into two intervals *A* and *B* and she enters *A*, she will never enter *B*.

The main idea is DP. Let's define *dp*[*x*] as the maximal value of the length of the good sequence whose last element is *x*, and define *d*[*i*] as the (maximal value of *dp*[*x*] where *x* is divisible by *i*).

You should calculate *dp*[*x*] in the increasing order of x. The value of *dp*[*x*] is (maximal value of *d*[*i*] where *i* is a divisor of *x*) + 1. After you calculate *dp*[*x*], for each divisor *i* of *x*, you should update *d*[*i*] too.

This algorithm works in *O*(*nlogn*) because the sum of the number of the divisor from 1 to *n* is *O*(*nlogn*).

Note that there is a corner case. When the set is {1}, you should output 1.

There are many *O*(*Q* * *N* * *logN*) solutions using segment trees or other data structures, but probably they will get time limit exceeded.

We can solve each query independently. First, let's consider the following DP algorithm.

*dp*[*c*] := the maximal value of a sequence whose last ball's color is *c*

For each ball *i*, we want to update the array. Let the *i*-th ball's color be *col*[*i*], the *i*-th ball's value be *val*[*i*], and the maximal value of dp array other than *dp*[*col*[*i*]] be *otherMAX*. We can update the value of *dp*[*col*[*i*]] to *dp*[*col*[*i*]] + *val*[*i*] × *a* or *otherMAX* + *val*[*i*] × *b*. Here, we only need to know *dp*[*col*[*i*]] and *otherMAX*. If we remember the biggest two values of *dp* array in that time and their indexes in the array, *otherMAX* can be calculated using the biggest two values, which always include maximal values of dp array other than any particular color.

Since the values of dp array don't decrease, we can update the biggest two values in *O*(1). Finally, the answer for the query is the maximal value of *dp* array.

The complexity of the described algorithm is *O*(*QN*).

First, let's consider a simpler version of the problem: You are given a start state and a goal state. Check whether the goal state is reachable from the start state.

Define *A*, *B*, *C*, and *D* as in the picture below, and let *I* be the string of your instructions. *A* and *B* are substrings of *s*, and *C* and *D* are substrings of *t*.

It is possible to reach the goal state from the start state if there exists an instruction *I* such that:

- 1
*A*is a subsequence of*I*. - 2
*B*is not a subsequence of*I*. - 3
*C*is a subsequence of*I*. - 4
*D*is not a subsequence of*I*.

So we want to check if such string *I* exists. (string *s*1 is called a subsequence of *s*2 if it is possible to get *s*2 by removing some characters of *s*1)

There are some obvious "NO" cases. When *D* is a subsequence of *A*, it is impossible to satisfy both conditions 1 and 4. Similarly, *B* must not be a subsequence of *C*. Are these sufficient conditions? Let's try to prove this hypothesis.

To simplify the description we will introduce some new variables. Let *A*', *B*', *C*', and *D*' be strings that can be obtained by removing the first characters of *A*, *B*, *C*, and *D*. Let *c*1 and *c*2 be the first characters of *A* and *C*.

Suppose that currently the conditions are satisfied (i.e. *D* is not a subsequence of *A* and *B* is not a subsequence of *C*).

- If
*c*1 =*c*2, you should perform the instruction*c*1 =*c*2. The new quatruplet will be (*A*',*B*',*C*',*D*') and this also satisies the conditions. - If
*c*1 ≠*c*2 and*B*' is not a subsequnce of*C*, you should perform the instruction*c*1. The new quatruplet will be (*A*',*B*',*C*,*D*) and this also satisies the conditions. - If
*c*1 ≠*c*2 and*D*' is not a subsequnce of*A*, you should perform the instruction*c*2. The new quatruplet will be (*A*,*B*,*C*',*D*') and this also satisies the conditions.

What happens if all of the above three conditions don't hold? In this case *A* and *C* have the same length and *A* = *c*1*c*2*c*1*c*2..., *B* = *c*2*c*1*c*2*c*1. In particular the last two characters of *A* and *B* are swapped: there are different characters *x* and *y* and *A* = ...*xy*, *B* = ...*yx*. Now you found a new necessary condition! Generally, if *A* and *B* are of the form *A* = ...*xy* and *B* = ...*yx*, the goal state is unreachable. If the last instruction is *x*, Vasya must be in the goal before the last instruction, but then Vasya will go further after the last instruction. If the last instruction is *y*, we will also get a contradiction.

Finally we have a solution. The goal state is reachable from the start state if and only if *D* is not a subsequence of *A*, *B* is not a subsequnce of *C*, and *A* and *C* are not of the form *A* = ...*xy*, *C* = ...*yx*. The remaining part is relatively easy, so I'll leave it as an exercise for readers.

For this problem there are slides: Please check here.

UPD: Thank you for pointing out mistakes. They are fixed.

Tutorial of Codeforces Round #162 (Div. 2)

Hello!

I'm Squirrel Liss. I became the hero of today's contest. The writers of the contest are snuke, hogloid, DEGwer, and rng_58. I'd like to thank Gerald for helping preparation, Delinur for translation, and MikeMirzayanov for the Codeforces system. The point values will be standard: 500-1000-1500-2000-2500 for both divisions.

I will encounter many difficulties about stones, nuts, and sequences... Please help me!

Since 07:30 PM MSK is late here, the contest will be moved to 05:00 PM MSK. Please check the schedule in your time zone in timeanddate.com: http://timeanddate.com/worldclock/fixedtime.html?iso=20130120T22&p1=248&ah=2

UPD: Announced the detail of the contest.

The top five contestants in div1 were:

- 1: Petr
- 2: AleX
- 3: scott_wu
- 4: Zhukov_Dmitry
- 5: al13n

And in div2:

- 1: kesongyu
- 2: Moor
- 3: Qwaz
- 4: tsunayoshi
- 5: step4

Congratulations!

Also congratulations al13n and Komaki for solving div1 E problem.

The authors were

- D2 A: rng_58
- D2 B: snuke
- D1 A/D2 C: DEGwer
- D1 B/D2 D: DEGwer
- D1 C/D2 E: hogloid
- D1 D: rng_58
- D1 E: snuke

UPD: Tutorial was added here.

Announcement of Codeforces Round #162 (Div. 1)

Announcement of Codeforces Round #162 (Div. 2)

My solution depends on the following hypothesis. Can anyone prove this?

~~Sorry, the image doesn't work for some reason. \sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} d(ijk) = \sum_{gcd(i,j)=gcd(j,k)=gcd(k,i)=1} [\frac{a}{i}][\frac{b}{j}][\frac{c}{k}] Now it works.~~

Sorry, please type "http://rng.gozaru.jp/cf.png" directly to the address bar.

Finally proved: "http://rng.gozaru.jp/b.pdf"

Today I participated in Facebook Hacker Cup Round 3. 100 people participated and top 25 will advance to the onsite round in California.

The contest has started. I glanced at titles of problems and samples, and decided to solve "Divisor Function Optimization" first. It was a number theory problem, so I was confident that I can solve this problem. However, after thinking for a while, I noticed that I need to calculate all primes <= 2^250000! (of course, it turned out to be wrong later.) It seemed to be impossible, so I read the other two problems.

"Trapezoids". My first implession was (I don't know whether it's correct or not): convert trapezoids to rectangles in 2D plane and do some sweep line algorithm. It looked hard to implement, so I decided to skip it.

"Unfriending". Try all local-maximal subsequences that can be removed? It's quite easy! I implemented and debugged... oh, I didn't read the problem correctly!

Meanwhile a few people solved "Trapezoids", but let's return to "Divisor Function Optimization". I missed one condition! b/a <= 25! Then it's quite easy, just solve for each prime independently and calculate the product. (there's some more details, e.g. precalculating product of primes, but I'll omit details here.)

I implemented, debugged, and passed all examples. I tested maximal case (actually it wasn't): (a = 250000, b = 10000) * 100000 times. It worked in 13s, which means 260s for 20 max data, so I decided to submit.

I downloaded the input file carefully, saved it on my computer, and executed my program: "./a < divisor_function_optimization.txt | tee divisor.out" But my program worked very slowly.

30 seconds left...

Case #19: 49898798639490 49944512088364...

Looks very dangerous.

Finally 8 seconds before the deadline,

Case #20: 49843150065040 49981240725189

I clicked "submit" button very quickly.

Then my sad story comes. I saved output file in D:/facebook folder, but the browser shows different folder! I don't have time to find D:/facebook!

...I got upset and immediately went to bed.

Two lessons:

1) When time limit is tight, use computer as quickly as possible.

2) Check current folder of the browser before the program terminates!

I started to learn Russian recently. I'll write blog in Russian here to improve my Russian skills. Today I introduce myself.

Я изучаю** **русский. Я рнг_58.

Я японец. Я учащийся.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/09/2020 11:15:20 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|