Hello Codeforces!

I'm quite excited to invite you to AtCoder Beginner Contest 076 which will held on Saturday, October 28th 21:00 JST and lasts for 100 minutes.

The round problems are created by me (E869120) and square1001.

This contest will have four problems and it is rated for contestants whose rating is below 1200. The same as before, contestants whose rating is more than or equal to 1200 can take part out of competition.

The scoring is: 100 — 200 — 300 — 400.

I hope you can have fun during the contest. Good luck and have fun, wish you high rating!

See you tomorrow!


UPD 1: The editorial is here. Thank you for participating!

UPD 2: Congratulations for the winner!

Dear Codeforces.
Today, I wrote about a mystery of Codeforces contest start time.

1 — Background

There are many codeforces users from many countries. In spite of this, recently I feel Codeforces contest time is too biased and it's difficult to participate or enjoy for some country. For example, Codeforces Round #434 started at 13:05 UTC, Round #433 started at 12:55 UTC and Round #432 started at 14:35 UTC. It have only around 3 hours difference between "the earliest of the 3" and "the latest of the 3".
This is also an answer of "why I wrote this blog".

2 — Codeforces Time Distribution Graph

First, to investigate actual codeforces time, I searched recent 100 contests time and made a distribution graph.

3 — Problem

Recently, I found that Codeforces Contest times are biased and they're difficult to participate for some people:

• Around 9000 out of 30000 (30%) active users are difficult to participate because they're too late time. (China, Japan, South Korea, etc.)
• Around 3000 out of 30000 (10%) active users are difficult to participate because they're too early time. (United States, Brazil, Canada, etc.)

4 — My Suggestion

I think it is better that codeforces do this:

• ~20 or ~30 percent of contest should move in range 06:00-12:00 UTC. It's better time for Chinese, Korean, Japanese, etc. (It is also possible time for Indians, etc.)
• ~15 or ~20 percent of contest should move in range 21:00-03:00 UTC. It's better time for American, Canadian, Brazilian, etc.

• It became just a little bit more difficult to participate Codeforces contest for Indian, Russian, etc.
• It became more easier greatly to participate Codeforces contest for Chinese, American, etc.
• On the whole, I think active users would increase because it seems that there are many people who didn't cannot participate because of time.

AtCoder Regular Contest 083 (Link) and AtCoder Beginner Contest 074 (Link) has started, and ends at 13:40 UTC.

This time, no one wrote the announcement page and I felt that many people want to discuss about it, so I wrote this page for discussing and talking.

After the contest, let's discuss about the problem.

TopCoder SRM 720 will starts in ~8 hours.

Time: 8/24 07:00 EDT, 8/24 11:00 UTC, 8/24 14:00 MSK
Duration: 75 minutes coding phase + 5 minutes intermission + 15 minutes challenge phase

You can check the future contests from calendar.

Let's discuss after the contest.

Final Results

1. Division 1

Today, Codeforces Judge is stooped, and now judge queue length is very long.

• Judge is stopped more than 13 hours. This is as long as CF normal round x6.
• 5000+ submissions are In Queue.

Dear Codeforces Community.

Today I want to share some ways to practice competitive programming and getting rating. I think this is helpful for those who is practicing competitive programming hardly but rating is sluggish. (By the way, on July 17th, I have a project of competitive programming said CombNaf in Japan. I did a lecture about this. Great thanks to the CombNaf's organizer is nafmo2.)

I will write this by 4 steps: rating 1000 --> 1250, 1250 --> 1500, 1500 --> 1750, 1750 --> 2000, in Codeforces Rating System.

Before writing about each step, I wrote it as premise: You don't have to do this way. This is just a way to practice. Ways to practice is different among people, so I think this may not the best, but I hope this is useful.

Step 0: Some types of contest (A knowledge)

In order to explain step 1-5, I wrote about the types of programming contest.

Codeforces

• This judge. There are Div.1 problems and Div.2 problems. The number of contest is mainly 5-6.
• The problems of Div.2 said Div2 A, Div2 B, Div2 C, Div2 D, Div2 E,... in order.
• The problems of Div.1 said Div1 A, Div1 B, Div1 C, Div1 D, Div1 E,... in order.
• Problems are sorted by difficulty in each contest.

• There are ABC (AtCoder Beginner Contest) / ARC (AtCoder Regular Contest) / AGC (AtCoder Grand Contest) in AtCoder, but in this blog I will explain about ABC / ARC.
• There are 4 problems in ABC and ARC.
• Each problem in ABC is said ABC-A, ABC-B, ABC-C, ABC-D, and each problem in ARC said ARC-C, ARC-D, ARC-E, ARC-F.
• Problems are sorted by difficulty.
• In each contest, ABC-C and ARC-C is the same problem, and ABC-D and ARC-D is the same problem.

• There are Div.1 and Div.2, and there are contest for each division.
• In Division 2, there are three problems, which is said that Div2 Easy, Div2 Medium, Div2 Hard.
• In Division 1, there are three problems too, which is said that Div1 Easy, Div1 Medium, Div1 Hard.
• Easy is the easiest question of three, and hard is the hardest question in these three as naming.

Step 1: Rating 1000 --> 1250

In order to gain rating from 1000 to 1250, you should solve at least one problem in Div.2 contest in Codeforces. In AtCoder, 300 points problem is the level of rating 1100-1250. So I suggest these two ways:

• Solve Div2 A 50 problems. When you solved 50 problems, you might be able to solve >80% of Div2 A.
• Solve ABC-C in AtCoder. There are many educational problems in AtCoder Beginner Contest.

Step 2: Rating 1250 --> 1500

In order to gain rating from 1250 to 1500, you have to solve at least 2 problems faster in Div.2 contest. In addition, the level is as same as TopCoder Div2 Med and AtCoder ABC-D. (ABC-D is little high level for 1250) In addition, there is many educational problems in AtCoder, there is some point to do fast-solving practice in TopCoder, and Codeforces is the target judge. So I suggest these three ways:

• Solve Div2 B 50 Problems. (Most of problems are good quality)
• Solve Div2 Med 50 Problems. (The quality of problem is good, but Java Applet is inconvenience...)
• Solve ABC-D / ARC-D in AtCoder. (A little high level for 1250)

Step 3: Rating 1500 --> 1750

In order to gain rating from 1500 to 1750, you have to solve at least 3 problems faster in Div.2 contest. There are a lot of concept problems in Div1 A = Div2 C, and in Div2 only contest you have to solve as fast as possible. I made a table of judge and points to see what to solve easier.

• Solve Div1 Easy and Codeforces Div2C as the same period. I think if you solve <50 problems for each type, your rating will increase strongly, but I suggest you should solve until satisfied yourself.
• First solve ABC/ARC-D in AtCoder until solve 80% of ARC-D. Second solve Div1 Easy in TopCoder for concept-practice or fast-solving practice.

Step 4: Rating 1750 --> 2000

This is the last step that I can write. In order to gain rating 1750 to 2000, first you must go up to Div1, and you have to compete a little better in Div1. You have two steps, so I divided into two range.

1. Rating 1750 --> 1900
You should solve Div2C faster and stably. So I suggest that practice these two:

• Overcome your weakness (For example, DP problems, Graph Theory, Imprementation, etc.)
• Make your library (For example, RMQ, BIT, Segment-Tree, etc.)

• Codeforces Div1 B. In the story, the goal is becoming 2000+ in Codeforces. So practicing in Codeforces is the best too to get rating in CF.
• AtCoder ARC-E. ARC-E is 600-900pts in AtCoder, and this is level of rating 1900-2200. In addition, these problem is very like to Codeforces.

Step 5: Extra corner

In extra corner, I suggest two ways to compete well in Codeforces. This is also out of the problem-practice, but I think this is effective. (I did this and I feel this is effective.)

• Do Virtual Contest / Virtual Participation in Codeforces. This is a way of get use to contests.
• Take a rest for 10 minutes before real contests. This is a way to not get panic in the contest. It is also important in the contest on the mental side.

Conclusion

I suggest that five steps to practicing competitive programming. Ways to practice is different from a person to a person, so I don't think you must do this way. But this is one of the effective way I guess. (I think this is not the best because the way to fit is different among people.) I hope it will be useful even a little. (Also, sorry for my poor English.)

Please comment if you have suggestions and questions of this entry, and my way to practice.

Thank you for reading!

Recently, I realized a funny incident.
The incident was happened for two days.

Day 1 (June 28, 2017)

In this day afternoon, I realized 3 out of 7 my blogs was downvoted, though there is no blog in recent actions. It is sad, but some of this is so funny: The number of downvotes in all 3 blog was "-10".

1: A mystery of CF rating distribution (Link)


2: A mystery of CF contribution distribution (Link)


3: A mystery of correlation between rating and contribution (Link)


All of these are -10 votes differ! Why!?!?!?

The second story in this day is at night, which is a bit happy.
There is much upvote in a comment, though there is no recent action! (In addition, the differ is "+10".)

(Also, I felt suspicious about this because I think tomorrow maybe happen an incident about "10".)

Day 2 (June 29, 2017)

As I expected, an incident happened in day 2 afternoon.
There is some downvotes in other blog, which is 2 months ago and of course there isn't the blog in recent actions.

4: Square869120Contest #4 Editorial (A-D) (Link)

OH! SOMETHING HAPPENS! I expected -10 votes as previous three so the blog post rating is going to +19 -> +9, but this is +10. Interesting. (Note: All of -9 downvotes happened in 5 hours.)

=============== AFTER 4 HOURS ===============

Finally, the blog's rating decrase by 1. As I expected, the number of downvote was "10".

Summary

The incident is so mysterious and funny. A mystery about the elected number: "10".

In one sentence conclusion: "+10, -10, everywhere!".

Thank you for reading.

UPD: Thank you for gongy to react my funny story and write a blog. (Link) Thank you very much.

Update (Day 3)

Finally, the blog rating was temporary +16, but this was -50 at the end of Day 3.
In addition, the blog's rating change is really interesting as follows:

The next episode (July 22th)

The incident seems to be end, but this happened again. At 7/22 20:00 JST, suddenly, most of my blog downvoted! I thought why this reason is, so I decided to update this blog.

By the way, thank you for reading!

Recently, I'm interested in CF rating and contribution distribution, and I searched this.
I already searched about mysteries of rating distribution (Blog), so I wrote here about contribution distribution. (Thank you for comments)

Method of Searching

• Here is the leaderboard of top contributor.
• I searched the rank of contribution -51, -46, -41, -36,..., -1, 4, 9, 14,..., 164, 169, 174, 179. I searched the number of contributors too.
• Then, I make the distribution graph.
• Each range of the graph is [-inf, -50), [-50, -45), [-45, -40),... , [175, 180), [180, inf]. Each value of x-axis of the graph is the minimum value in range. For example, if the value of axis is 15, this means the range is [15, 20).
• The minumum value of range [-inf, -50) is inf, but in distribution graph this value is -1000.

• Obviously, the number of people who have contribution [100, 105), [105, 110), [110, 115) is especially larger than [90, 95), [95, 100).
• The number of people decreases greatly from contribution [10, 15) to [15, 20). The difference is approximately 2.5 times.
• The number of people who have contribution [-50, -45) , [-45, -40), and [-40, -35) are nearly the same.

Why these things can be occur?

UPD1: rng_58's contribution became 180, so the graph was extended. Wonderful.
UPD2: The distribution graph is extended because some user's contribution was changed.

Recently, I'm interested in the rating distribution and I searched this.

Method of searching

• Searching the place of people (in active users) who has rating 999, 1049, 1099, 1149, 1199,... , 3049, 3099.
• Let p_n be the place of people who has rating n.
• The number of people in range [1000, 1050) is p₉₉₉ — p₁₀₄₉, the number of people in range [1050, 1100) is p₁₀₄₉ — p₁₀₉₉, ...

• The number of people who have rating [1900, 1950) is especially larger than [1800, 1850), [1850, 1900). ( twice larger approximate )
• The initial rating is 1500, but rating [1350, 1400) is about twice larger than rating [1450, 1500).
• The average rating is about 1450. This is lower than the initial rating: 1500.

Hello, everyone.
I'm sorry for writing editorial too late.
I hope that you can use the commentary to solve the problem of s8pc or review the contest.
Please write comments where you do not understand, impressions, and discussions.

This is the square869120contest #4 (in AtCoder) editorial.
Writers were square1001 and E869120.

Since I think that there are also many people who have not yet seen the problem and forgotten it, I will attach a link to the problem statement.

A — Atcoder Handles

In this problem, the possible index of the handle name of Mr.X will be a "Range". (Example of "Range": {4,5,6,7}, {3,4,5,6,7,8,9,10})
Proof:

• The handle name of Mr.X doesn't include '?' — This means there is only one possibility of his name.
• If one of the others name (in the list) changes, the index of Mr.X will change no more than one.
• So, every index between "Minimum" to "Maximum" is possible.

 abcde -> zzzzz(changed)
 bbbbb
 ccccc
 ddddd
 Mr.X: cprpr 

• Minimum: When all characters of '?' in the list are 'z'.
• Maximum: When all characters of '?' in the list are 'a'.

B — Buildings are Colorful

Let's consider the case of N = K.
You can solve this problem with greedy method if N = K is true. (a[i] is the height of building i)

 long long ret = 0, Y = 0;
 for (int i = 0; i < n; i++) {
  if (Y >= a[i]) { ret += ((Y + 1) — a[i]); Y++; } // When previous building (After change) is lower than this
  else { Y = a[i]; } // Else
 }
 //The answer is ret.
 

• You are given the index of buildings that should be visible.
• Find the minimum cost.

 Let L be the maximum value of building's (that in front of this, After changed) height:
 If the building don't have to be visible, this building's height will not be increased.
 If the building have to be visible, this building's height will be max(This building's height,  L)
 

C — Calendar 2

You can solve this problem in O(N) in BFS or DFS algorithm, but you can only get 100 points in this way.

Let's consider to split the calendar every M rows. (Because this calendar have Periodicity per M squares, if m in the problem statement is divided by 7, M will be m / 7)
"The calendar between i * M + 1-th row to (i + 1) * M-th row" and "The calendar between (i + 1) * M + 1-th row to (i + 2) * M-th row" are the same.
So, you can solve this problem following way:

 Let "number of connected white parts between small calendar between 1st row to M-th row" be A
 Let "number of connected white parts between small calendar between 1st row to M * 2-th row" be B
 The answer is (B - A) * (N / M) + (2 * A - B).
 

D — Driving on a Tree

You can use the Tree-DP method in this problem.
This is a typical problem which use "Every-Direction Tree DP Algorithm" (It says "全方位木DP" in Japanese and translated directly, actually I don't know English word of the algorithm). The similar problem is 790B.
Let's consider the rooted tree which the root is node 1.

Let dp[i] be the expected value of number of moves which only go down (= to children of the node) and starts on node i
=== This value can find with Tree-DP algorithm in O(N).
Let dp2[i] be the expected value which starts on node i and go to the parent of the node first.
=== This value can find with Tree-DP algorithm (From the root of the tree to leaves) in O(N).

• Let the parent of node i be j.
• Let the degree of node i be p.
• 

In Apr/09/2017, there was a contest in Atcoder.
The contest name is "Square869120Contest #4". Click here

How was it?
Please write and discuss here about impressions and "qustions about solutions".

Thank you for everyone.
It is also advisable to solve those who are not participating or unsolved problems as past problems.

=========================================================================================================
past Square869120Contest
Square869120Contest #4:Click here
Square869120Contest #3:Click here
Square869120Contest #2:Click here
Square869120Contest #1:Click here

Update: If you can, please answer the questionnaire for the improvement to s8pc-5.

Square869120Contest #4 will be held on Sunday (4/ 9) 11:00 UTC. (20:00 JST / 14:00 MSK)

About Square869120Contest
・This contest is unofficial.
・Square869120Contest has been held 3 times before, and this is the 4th contest of Square869120Contest.

About Contest
・The contest are prepared by 9-th grade students, E869120 and square1001.
・Let's participate and enjoy!

Information
・Time: April 9th (Sunday), 20:00 JST (11:00 UTC)
・Duration: 200 minutes (3 hours 20 minutes)
・Number of Tasks: 8 Problems
・Writer: E869120 and square1001
・Rated: No [unrated]
・Language: Japanese / English
・This contest has many partial points, so if you can't get perfect score, you can get many partial points!

Past Square869120Contests
・Square869120Contest #3 (English / Japanese)
・Square869120Contest #2 (Japanese)
・Square869120Contest #1 (Japanese)

Update: The penalty of WA / TLE (or something unsuccessful submission except Compile Error), changed from 10 min to 0 min, so you don't have to worry about WA penalty!