E869120's blog

By E869120, 14 months ago, In English

Dear Codeforces community.
According to IOI 2019 Results, I got the 25th place and got successful gold medals twice in a row.
Although it was pretty close to the gold-medal border (only 6.14pts / 600 difference) and it was lower performance than IOI 2018, which I participated when I was orange in Codeforces, I had many chances to get more points in this IOI, even for top 10. Since there are not so many people who have got two gold medals in IOI (and there were many requests like "I want E869120 to talk about how to get gold in IOI" like this comment and this comment). I want to write something about IOI, which may be useful for people who will participate in IOI next year and also some years later.


A. First of all

At first, I want to write some premise to avoid comments like "I hate this post because I have no ties to IOI at all", or "How can I get gold with a 10-day practice from gray coder?". This blog is for people who want to improve skills in IOI (or national selection camp), and also for people who want to teach people practicing for IOI. But, even if you are not familiar with IOI, you may gain benefit by reading this post, because there is a little correlation between IOI and Codeforces. :)
So, let's move on to the main subject.

I think that the minimum requirement needed to be a gold/silver medalist is as follows:

  1. Know famous algorithms like segment tree, union find, set, map, sqrt decomposition, Convex Hull Trick, suffix array, Dijkstra method, minimum spanning tree, Euler tour of a tree, divide and conquer, binary search, etc. Are there any algorithms that you have not yet understood among I stated above? If there are, please check and understand the algorithms.
  2. Have skills equivalent to rating 2200+ (for silver I think it is 1800+) in Codeforces. Even if you know a lot of algorithms, if you have no skills to think algorithms and implementation, you cannot solve a problem like Shoes, or 40pts of split. If you want to gain Codeforces / competitive programming skills, let's read another post.
  3. Understand how to solve interactive problems and output-only problems. If you are not familiar with interactive / output only problems, you should see past problems.
  4. Be good at speed-solving. To get many subtasks or partial scores, fast implementation is needed. I will write about how to improve speed-solving skills which are useful in IOI in this blog.
  5. Have a good strategy. I think that strategy is the most important part of IOI. I will write about an example of a good strategy in this blog.
  6. Be able to sustain maximum concentration and performance for 5 hours. I will write about a way to improve concentration by practicing in this blog.
  7. Be mentally strong and don't give up your hope from the first second of the contest to the last second of the contest no matter what happens. I will write about my way to get an unbeatable mind that can fight in IOI in this blog.

B. My concept about IOI

Some people said that "What is important for IOI is to gain skills to solve difficult problems by thinking long hours" in this comment. Yes, it is important for me, who aims top5 or top1 in IOI next year, or in some contest which there are not so many subtasks like Japanese national team selection camp. But I think that it's a bit different for people whose goal is "silver" or "gold" in IOI.



Solve all the subtasks that you can gain with your skills within 5 hours is very important. Some people think like "5 hours? Too long. It is 2.5x longer than normal Codeforces round! I'm sure that I can solve all the subtasks that I can gain". But it's not as easy as it sounds — because IOI has a lot of subtasks, mainly they are implementation-heavy. For example, problem vision has 8 subtasks! For a problem which has many subtasks, if you have a strategy like "First, implement the solution of $$$N \leq 300$$$ which I can find the solution within a minute. Second, think 10 minutes for the next subtask and implement the solution for $$$N \leq 5 \ 000$$$. Third, think 10 more minutes and solve in a special case for $$$A_i \leq 10$$$. Fourth, think the solution of the full score, which the constraint is $$$N \leq 100 \ 000$$$.", you have no time get all implementation done if you have no skills of speed-solving!

So, let's see statistics to see how much "not losing points" and "speed-solving" are important for IOI. Think about two cases down below.

(i) Suppose you solved all the subtasks which 110 or more people got in each year's IOI

Year Day1 P1 Day1 P2 Day1 P3 Day2 P1 Day2 P2 Day2 P3 Total Score Final Rank Medal
IOI 2019 100 40 50 53 66 24 333 77/327 Silver :)
IOI 2018 100 17 49 53 12 36 267 87/335 5 pts to Silver
IOI 2017 31 20 11 90 13 50 215 102/304 34 pts to Silver
IOI 2016 100 34 23 90 38 16 301 94/308 27 pts to Silver
So, to get silver, it seems like "solving all the subtasks which are solved by 110+ people" and "solving at least a single subtask which is solved by 60-100 people" are needed. So, how about gold?

(ii) Suppose you solved all the subtasks which 45 or more people got in each year's IOI
Year Day1 P1 Day1 P2 Day1 P3 Day2 P1 Day2 P2 Day2 P3 Total Score Final Rank Medal
IOI 2019 100 40 72 71 100 24 407 31/327 7 pts to Gold
IOI 2018 100 37 49 86 51 36 359 19/335 Gold :)
IOI 2017 83 100 27 97 51 50 408 10/304 Gold :)
IOI 2016 100 34 31 100 100 60 425 22/308 Gold :)
So, to get gold, it seems like "solving all the subtasks which are solved by 45+ people" is all you need. Note that the task order is the same as the IOI official results page for each year. (example) Also, since I could not get any information about what subtask did each person get, "the score when you got all the subtask which solved by 110+ people" is calculated as the 110th score for each problem. Same for the 45th.

So, how difficult is the subtask which can be solved by 110 people, or 45 people?
My opinion is this:

  • 110 people: Same as Codeforces difficulty 2100. If you are purple, you should solve within ~70 minutes. If you are orange, you should solve within ~40 minutes (since for many problems in IOI, implementation is heavy)
  • 45 people: Same as Codeforces difficulty 2600. If you are blue, almost impossible to solve. If you are orange, you should solve within ~2 hours. If you are red, you should solve within ~1.3 hours.

In conclusion, I think that not losing a point and speed-solving are very important parts of IOI, for people who aim to get a silver or gold medal.

C. How to practice speed solving?

As I stated above, I think that practicing speed-solving is a very important part of IOI. So how can you improve speed-solving?

Basis
If you think that you take too much time to solve Codeforces Div2 A, B or C problems (e.g. 4 minutes for Div2A, 8 minutes for Div2B, 15 minutes for Div2C if you are orange. ~1.5x for purple, ~2x for blue.), you should solve AtCoder Beginner Contest problems. My recommendation to gain fundamental skills is to solve 300pts or 400pts problems in AtCoder. Since AtCoder has many problems, you can practice a lot. I also think that doing a virtual contest is also important. That's because virtual contest makes you concentrate. When I was 8th grader, I made a virtual contest, which I selected ~5 problems from AtCoder whose difficulties are 300-400pts and tried to solve them within ~1 hour.

Practicing Speed Solving for IOI
I think that you can do two things to practice speed solving for IOI.

  • One is doing a virtual contest or IOI-like contest. If you do one or two virtual contests, you may realize how important speed solving is. (If you don't, you should read about my strategy of IOI, which led me to the stable acquisition of gold medals. Then, let's do one more virtual IOI-like contest with using my strategy.) There are a lot of IOI-like contests, for example, International Olympiad in Informatics (IOI), Japanese Olympiad in Informatics (JOI), Central European Olympiad in Informatics (CEOI), Baltic Olympiad in Informatics (BOI), info(1) cup, etc. So, you can do many IOI-like contests. I recommend doing this one at first.
  • Another one is solving ICPC problems with a clock/timer. Since many ICPC-problems are implementation-heavy and also most of the problems require some algorithms (≅ not ad-hoc problems) to solve them, you can also gain speed-solving skills which are vital for IOI. Unfortunately, most of the problems in the ICPC World Finals are very difficult. So, you can solve problems for regional contests or national qualification round. But how can you find the problems? For example, AIZU ONLINE JUDGE has a lot of ICPC problems. Also, if you want to practice speed-solving in AIZU ONLINE JUDGE, solving problem from PC Koshien (PCK) is a good idea. Both for ICPC and PCK, if you have no time to solve all of them, I recommend solving new one. If you did virtual contests of most of the IOI-like contest, or if you solved many IOI-like problems, it may be a good idea to do this.
  • If you want to get a gold/silver medal in IOI, you should do virtual contests of at least 5 recent years of IOI. With virtual contests, you can gain not only speed-solving skills that you can solve many subtasks within a short time but also your strategy of IOI.

D. My strategy of IOI

Firstly, my strategy is for people who have high-level skills in speed-solving. If you are not good at speed-solving and want to follow my strategy, you should read the previous section: "How to practice speed-solving?".
In addition, my strategy will not work for people who want to aim absolute winner. I think that getting absolute winner in IOI needs to take much risks.
I will explain in two parts: "base strategy" and "additional strategy".

Base strategy of IOI 2018
(i) First 1/2 of the contest
In the first half, I use ~50 minutes for each problem. For example, from 0:00 to 0:50, solve Problem 1. Then from 0:50 to 1:40, solve Problem 2. Finally, from 1:40 to 2:30, solve problem 3. For each problem, I did a strategy like this:

  1. Read problem for 2 minutes.
  2. Think of the solution for 3 minutes.
  3. Implement the solution and get all subtasks which I find the solution within 3 minutes. For me, the implementation takes 5-20 minutes.
  4. Think of the solution for 10 more minutes.
  5. If I could not find any better solutions, give up this problem and move on to the next problem. If I could find a better solution, implement it. If the implementation is heavy, it takes more than 50 minutes in total of this process. In this case, the duration that I can put on the second part will be reduced.

(ii) Second 1/2 of the contest
I try to find the easier subtasks among remaining and solve (or give up) them. Though it depends on how much time is remaining and the number of remaining problems, usually when I think for 50-60 minutes and cannot reach any of the solutions, I will give up the problem and choose another one. But how do I find the easier subtasks? The hint is on the scoring:
  • Mainly, if the scoring is very rough (e.g. Subtask #1: 5pts, Subtask #2: 10pts, Subtask #3: 35pts, Subtask #4: 50pts), the problem (full solution) is easy. It is true for IOI 2018 Combo, IOI 2015 Boxes with Souvenirs, IOI 2019 Shoes. Their subtasks’ scores are mostly multiple of 5. Conversely, if the scoring is not very rough, the problem is not so easy.
  • If the score of the last subtask is big (e.g. 40pts or more), the full solution of this task is usually very difficult. Though problem IOI 2017 Wiring is not so difficult while the last subtask is big, most of the problems whose last subtask’s score is big tend to be difficult in IOI. There are some examples: IOI 2019 Split, IOI 2019 Walk, IOI 2018 Meetings, IOI 2017 Toy Train.
  • If the scoring of the first subtask is low and relatively difficult, the full solution is likely to be difficult. For example, if the first subtask can be solved by just using if-statement and you can get 10pts, this problem is likely to be easy. Conversely, if the first subtask requires writing 100+ lines brute force and you get only 7pts, that problem is likely to be difficult. For example, IOI 2019 Walk is a difficult-case example. But this is just a tendency and not always true — for example, in problem IOI 2015 Towns, though only 111 out of 321 people got positive scores, this problem is not too difficult — 7 people solved it.

By the way, I used a bit different strategy for IOI 2019. That's because there were some issues like these:
  • In Day1, in problem rectangle, the sample input in official zip file was wrong. (It was fixed after ~1 hour after the contest starts)
  • In Day1, from ~0:55 to ~1:05 (from the beginning of the contest), we could not be able to access to the judge server. (504 gateway timeout)
  • In Day2, we could not download zip file because of the initial setting of PC (zip file was downloaded to root directory, where the contestant didn’t have access to), so I could not use PC for the first 15 minutes (after I raised my hand and called a staff, the problem on my PC was fixed)
  • Since most of the contestant (I think all) suffered from the previous problem, 40 minutes after the contest starts, all contestants’ PCs were restarted.

Since I could not gain many scores in the first 1 hour because of the issue, I changed the strategy a bit:
  • For the first 80 minutes, I got some subtasks of the problem which I thought the full solution was the most difficult. (In Day1, since I felt that split was easier than rectangle then, I attempted rectangle at first)
  • For the next 20 minutes, I solved some subtasks which were obvious, for the problem which I thought the full solution was the easiest.
  • Next, since I thought that getting at least one 100pts for each day was the key to winning a gold medal, I solved the easiest problem. (For day1 it took 60 minutes, and for day2 it took 95 minutes)
  • After getting 100pts, I got some subtasks of the remaining problem for 50 minutes. (For day2, since remaining time was already short, I used the all remaining time to solve output only task.)
  • If I had remaining time, I used the same strategy as IOI 2018 in the second half of the contest.

Additional strategy
On day2, there was an output only task. When I got 57pts of Problem 3 (walk), I had two choices: "Get 66pts on Problem 2 (vision) instead of getting 100, and get better score in output only task", or "Get 100pts on problem 2 (vision), and get lower score in output only task". I chose the second one because I thought that the key to winning was to get 100pts on problem vision. So, for each day, it’s important to ask yourself “what is the key to getting a gold medal?” in a critical moment.
Also, if you can estimate the border of gold, it is better. I think that you will be able to estimate the border of gold/silver if you solved past 5+ years IOI problems.

E. Results of strategy

In IOI 2019, I finally got the gold medal. But there is an interesting fact — in Day2, when just 2 minutes before the contest ends, I was in the silver-medal zone. My source code of output only bugged, while time is running out. In the contest duration 5:13:50 — I finished the debugging at 5:12:10, I submitted at 5:12:28 and 5:13:24, these submissions brought me to the gold medal. Unfortunately, I could not submit two more testcases. If I had time to submit them, my score might be 61pts. I also had an idea to get 85+ points in output-only tasks, so if I had time to implement it, I might have a chance to get ~10th place in IOI. But fortunately, I won a gold medal.
So, how I sustained my concentration for the whole 5 hours? How my mind was able to endure the last 5 minutes of IOI 2019? There is an effective way to gain concentration and mental toughness. I will explain in the next section.

F. How I succeeded to gain concentration and mental toughness

In IOI 2019, I got gold because of the last few seconds. But this action needs a lot of concentration and strong minds because it was one of the life-changing matches for me. Why did I succeed to gain such skills? Here is my way.

  • Do 10-hours virtual contest many times. It means double IOI. For example, choose six difficult IOI-like problems and get as many points as possible in 10 hours. Also, choose two-days IOI-like competition (e.g. CEOI) and solve them including day1 and day2 within 10 hours is OK. I did this kind of virtual contest for 4-5 times before IOI. If you do 10-hours virtual contest many times, you will get used to concentrating in long-hours contests. If you can concentrate in the 10-hours contest, it is sure that you can concentrate for 5 hours!
  • Know your limit and challenge to break your limit. One of the easiest ways to break your limit is real-marathon (running long distance) — because a lot of physical skills and mental skills are needed. For example, a week before a big competition (IOI or JOI selection camp), I run for ~20km as hard as I can. In the competition, I can think that "since nothing is harder than that running or real-marathon, I can do anything in IOI". Also, another advantage of running long distance before a big competition is that I can gain more physical strengths. Because 5 hours is long, if you have more physical strengths (especially endurance), there could be some advantage for you in IOI.

G. Conclusion

At first, I have to apologize for one thing — sorry for my poor English. If you have some trouble understanding my English, please write a comment and I will fix it. Thank you for your patience.
Lastly, I want to write some advice for challengers in Codeforces, based on my experience in IOI 2019.

  • Firstly, In International Olympiad in Informatics (IOI), some troubles may occur. It may be major problems like we cannot download the files. In Codeforces the round can be unrated, but in IOI the round cannot be unrated. So, your flexibility — ability to respond to the situation flexibly is important in IOI.
  • Secondly, in IOI and Codeforces, all seconds during competition have the same value. In the example of IOI, you have 5 hours. But the value of first 1 second in the contest, the value of 1 second just after 1 hour and 49 minutes has passed from the start of the contest, and the value of the last 1 second of the contest, are all the same. So, what is important is — don't waste even a single second in the contest. A person who makes light of a second loses. If you value every second during the contest and do everything you can during the limited time, you will win.
  • Lastly, though IOI competition lasts 10 hours including day1 and day2, it was at last 2 minutes I found the final bug, at last 82 seconds of the competition I entered the gold-medal zone, and at last 26 seconds of the competition, I made sure to get a gold medal. Sometimes this kind of things happen. The competition results will not be determined until the last minutes, the last second, and even the last 0.1 second. The person who never gives up until the last moment will win.

If you have some suggestions & comments & opinion & your strategy, please comment on my blog!
Thank you for reading!!!

Read more »

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

By E869120, 17 months ago, In English

Dear Codeforces community.
Finally red :)

Today, I want to share about some ways to practice competitive and gain your rating. I hope that this is helpful for those who is practicing competitive programming harder but rating is sluggish. There are 54,000+ people who participated in Codeforces contests actively, but sadly only a few people reach a red-ranked coders. For people who can't reach red, I will introduce my way to gain rating in some steps.

This blog is an extended and more detailed version of my previous tutorial blog, but 2 years and now are different. So there are many points that are different from blog which has written 2 years ago. Note: Some people who already read my previous tutorial blog may doubt, but do not doubt — I should say that the "from rating 1000 to 2000" part of this blog is not the copy of my previous blog and it's very different.

Since the size is very big, if I wrote contents to Codeforces blog directly, it might be too long. So, this time, I will share a 19-page PDF link of my tutorial blog. This time, my blog includes introduction, knowledge of some contests systems (AtCoder, TopCoder) and some convenient websites, some ways to practice for improve rating, and conclusion. Also, optimal practice method is differ by rating. So, this time, I will write in 4 steps: 1000 -> 1400, 1400 -> 1900, 1900 -> 2200, and 2200 -> 2400.



The link of my blog (PDF) is as follows:

[Tutorial] A way to practice competitive programming — from rating 1000 to 2400+


Please comment if you have suggestions, comments to my blog, and opinions on my way to practice.
Thank you for reading!

Read more »

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

By E869120, 18 months ago, In English

Hello, Codeforces!

Finally, the season of square869120Contest comes. I am filled with deep emotion when I think of the dawn of this contest :)

On April 14th, 20:00 JST, an innovative contest, square869120Contest #6 will be held. As usual, I'll invite everyone includes non-Japanese participants, and in previous contest, 20 non-Japanese participants joined in the contest. Hope in this year, much more will join :)

square869120Contest is a competition which is held by a twins: E869120 and square1001. This round is our sixth voluntary contest, counting from from our first round when we were 7-th grader. Now we are 11-th grader, but we are making much efforts to achieve continuous-growing of the contest, including some experience of writing problems of AtCoder Beginner Contests and others.



About square869120Contest (s8pc)
  • This contest is unrated and unofficial, and AtCoder doesn't have responsibility about the contents of the problems.
  • square869120Contest had been held 5 times before, and this is the 6th contest.
  • From 3rd contest, Both English and Japanese problem statements are prepared.
  • This contest is an IOI-style contest, and there are many partial scoring. It means even if you don't came up with a full-solution, to solve easier problem (e.g. lower constraints), you can get partial score. You can see previous square869120contests to know more about partial scorings.

Contest Information
  • Time: April 14th, 2019, 20:00 JST
  • Duration: 240 minutes
  • Number of tasks: 9 (Consists of 8 algorithm tasks and 1 marathon task)
  • Writer: E869120, square1001
  • Rated: No (unrated)
  • The first problem is as easy as (or possibly easier than) Codeforces Div2 A, and the last problem is as hard as Codeforces Div1-E. In addition, there are many partial scores. I think all participants can enjoy the contest.

Scoring
Problem A B C D E F G H I
Max. Score 200 300 400 600 800 1000 1200 1500 1500
  • Note: The last problem is a marathon-match-like optimization task.
  • Note: The max score of problem D has changed.





Past Problems

Feedbacks from participants of past s8pc participants
There 5 s8pc contests before. In cumulative total number of people, 1500 people registered in s8pc, and 876 people got 1 point or more, including 99 international participants. To some participants, I asked some impressions of s8pc, and some advice for newcomers.

yosupo (The winner in s8pc #5)
  • Since there are many kind of problems though the writers are same, s8pc is very fun contest!
  • But this contest is very consistent. For example, the last problem is always marathon-match like task.
  • Participate more!

WA_TLE (17th place in s8pc #4, runner-up in s8pc #5)
  • It was s8pc #4 when I first solved some problems by twins. At first, I wondered why they can make very good problems.
  • Actually, I am in good relationship with twins, as if I could think "we are triplets". s8pc problems are interesting!
  • Let's participate and enjoy!

zscoder (4th place in s8pc #4)
  • I think s8pc is a fun contest! The problems are interesting and also challenging. Some problems require interesting ideas to solve.
  • Also, there's the marathon problem every contest which looks interesting, though the time is probably too short for me to be able to work on it much considering that there are other hard problems to solve.
  • For newcomers, the problems also have many subtasks, and first half of problems are not so difficult. Thus you don't have to worry that you can't solve anything ;)

kotamanegi (13th place in s8pc #5)
  • In s8pc #5, because of proper difficulty and kind editorial, I learned very much in the contest!
  • I am very good at marathon-match like problem. For the problem "Collecting Gems in Fun" (the last problem of s8pc #5), as much as you think, as many point as you can get. This problem is very good for introducion of marathon-match.
  • Overall, s8pc is a high-level contest but enjoyable through many rating-clusters and many generations.
  • Let's participate in this contest!

Let's participate and have fun!


E869120, square1001

UPDATE

  • The max score of problem D has changed.
  • Finally, now, the contest will starts less than 24 hours. Participate more!
  • After the contest, let's discuss about the problems.
  • The contest is over. Unofficial Ranking and Statistics is now open!

Read more »

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

By E869120, 18 months ago, In English

Hello Codeforces!

Recently, in JOI 2018 Spring Camp, a young genius QCFium, wrote a naive $$$O(NQ)$$$ algorithm in the problem Examination, and got the perfect score. The code is as follows:

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Naive Solution as follows...

I thought that it was very surprising, but actually, even $$$N,Q \leq 100,000$$$, with the only 3 lines $$$O(NQ)$$$ naive algorithm actually got accepted. To check whether this speedup is actually effective or not, I wrote these two codes: one is with the 3-line speedup, and the other is without the 3-line speedup.

Code A (With speedup)


Code B (Without speedup)


As a result, in custom innovation (code-test) in Codeforces, Code A used 2074ms but Code B used 2292ms. Code A is faster by ~10.5%. Actually, a young genius QCFium said "The more simple the code is, the more relatively faster with 3-line speedup." So, it could be possible that with speedup, the calculating speed becomes x1.2 or x1.5.

So I have some questions to the community.
Is it possible to use this speedup in CodeForces official contests?
And is it legal to use it in IOI selection contests in your country? (Actually in Japanese Olympiad in Inforcatics, it is OK to use this speedup)

I am very appreciate for sharing your opinion.
Thank you for reading this blog.

Read more »

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

By E869120, history, 2 years ago, In English

Hello, Codeforces!

On Saturday, Octorber 6th, 21:00 JST, AtCoder Beginner Contest 112 will be held.

The contest information is as follows:

  • Duration: 100 minutes
  • The number of problems: 4
  • Scoring: 100 — 200 — 300 — 400
  • Rated: Yes (for people whose rating is 1199 or lower)

Good luck and have fun!
Let's discuss about the problems after the contest.

UPDATE
1. The contest is over. Thank you for your participation.
2. Japanese editorial is published now. Editorial — Wait a moment for unofficial English editorial.

Read more »

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

By E869120, history, 2 years ago, In English

Dear Codeforces community.

AtCoder Beginner Contest 106 will be held at Saturday, August 18th, 21:00 JST.

Here is some contest informations:

  • The contest is rated for participants whose rating is 1199 or lower.
  • The writers are: E869120 and square1001. We are 16-years-old twin brothers :)
  • Duration is 100 minutes.
  • There are 4 tasks in this contest.

Let's participate and enjoy for this contest, and discuss the problems after the contest.
Good luck and have fun!
---
E869120, square1001

UPDATE
The contest is over, and editorial is out!

Read more »

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

By E869120, history, 2 years ago, In English

AtCoder Beginner Contest 105 is ongoing now, from August 11, 2018, 21:00 JST.

The writers are DEGwer, drafear, square1001 and me.
The point values are: 100 — 200 — 300 — 400.

This contest will be unrated because of problems in English statement. At first, there is no English statement in problem A. 6 minutes after starting the contest, the English statement appeared, but it was too late. Sorry for inconvenience.

After the contest, let's discuss the problem.
Thank you for your participation.

UPDATE

Read more »

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

By E869120, history, 2 years ago, In English

Hello everybody!

I'm delighted to invite you to anniversary round AtCoder Beginner Contest 100, which starts at Saturday, June 16, 2018 at 21:00 JST. The time is as usual as previous round. (However, some of AtCoder contest start time is unusual...)

This is the fifth round for a Japanese twin-brothers: E869120 and square1001. I already held AtCoder Beginner Contest 064, 076, 088, 096, and this time, it's 100. Multiple-of-four again, again and again! (Where is the probability 1/1024 ???) Anyway, ultimate thanks for rng_58 for reviewed and refined my problems, chokudai for creating one of the best contest platform in the universe. It is obvious that I could not be able to host the contest without cooperation of these two people.

The round is rated for participants whose rating is strictly lower than 1200. High-skilled participants whose rating is >=1200 is also welcomed to participate as out of competition (unrated).

Scoring is 100 — 200 — 300 — 400, as usual. The contest duration is 100 minutes.

Let's participate in the contest, good luck and high rating! Also, hope to have a ultimate-great memory in the first 3-digit round!

Finally, AtCoder managed to hold the contest which the first-digit is not '0'. Since this contest is the 100th anniversary round, so some problem can be associated with anniversary. Wish AtCoder and other contest platforms will be continue till 4-digit round :)

UPDATE

1. Judge queue is clogging now.
2. Now, judge queue is fixed. Sorry for inconvenience.
3. Editorial Uploaded.

Read more »

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

By E869120, history, 2 years ago, In English

Hello, Codeforces!

On May 5th, 21:00 JST, AtCoder Beginner Contest 096 will be held.

The problems were prepared by square1001 and me (E869120). Thank you for chokudai, rng_58, evima to helping us to host the round on AtCoder!

You will be given 100 minutes and there are 4 problems with following scores: 100 — 200 — 300 — 400.

This contest is rated for all participants whose rating is less than 1200, but as usual, participants whose rating is more or equal to 1200 can take part out of competition.

Good luck and have fun!

UPDATE
  • The contest will start in less than a day.
  • The contest is over! Thank you for your participation! Let's discuss about the problems.
  • Editorial is out! Link

Read more »

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

By E869120, 2 years ago, In English

Square869120Contest #5 will be held on Sunday, April 15th, 20:00 JST.

About Square869120Contest

  • This contest is unofficial.
  • Square869120Contest has been held 4 times before, and this is the 5-th contest of Square869120Contest.
  • From the 3-rd contest, both Engish and Japanese statements are prepared.

Contest Information
  • Time: Sunday, April 15th, 20:00 JST
  • Duration: 240 minutes
  • Tasks: 9 (Consists of 8 algorithm tasks, 1 marathon task)
  • Writer: E869120, square1001
  • Rated: No (unrated)
  • The first problem is as easy as Codeforces Div2 A, and the last problem is as hard as Codeforces Div1-D,E problems. In addition, there are many partial scores. I think all participants can enjoy the contest.

Scoring
Task ID Max Score Partial Scores
A 200 100+100
B 300 70+140+90
C 500 90+100+310
D 600 120+160+320
E 800 40+160+190+410
F 1000 60+60+250+630
G 1200 80+320+[0 ----- 800, 1-point unit]
H 1400 210+320+870
I 1500 Marathon Task, 1-point unit

Past Contests
Square869120Contest is one of the unrated contest which have a long history. There's 4 previous contest, so you can solve them to practice this kind of contest.



Updates
1. Some of the partial scores has changed. Please check.
2. Some of the partial scores has changed. We think the point values are determined.
3. The contest is over. Thank you for your participation!
4. English editorial will be published on Thursday, 4/19/2018.
5. English editorial uploaded. Link

We are looking forward to your participation! Let's participate and enjoy!!!!!

Read more »

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

By E869120, history, 3 years ago, In English

Hello Codeforces!

On February 18th, 21:00 JST, AtCoder Beginner Contest 088 will start.

Announcement Page

The problems were prepared by square1001 and me (E869120). Thanks to chokudai and rng_58 to helping us to host the round on AtCoder!

You will be given 100 minutes, and there are 4 problems with the following scores: 100 — 200 — 300 — 400.

This contest is rated for participants whose rating is lower than 1199, but as usual, participants whose rating is more or equal to 1200 can take part out of competition.

Good luck and have fun!

UPD: The contest is over. Let's discuss about the problems.

Read more »

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

By E869120, 3 years ago, In English

Hello, CodeForces!

AtCoder Beginner Contest 081 (Link) and AtCoder Regular Contest 086 (Link) will be held on December 10th, 21:00 JST.

The writer is semiexp and someone.

Let's participate and enjoy. Let's discuss after the contest.

Read more »

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

By E869120, history, 3 years ago, In English

AtCoder Regular Contest 085 / AtCoder Beginner Contest 078 held on Saturday, 21:00 UTC+9.

Let's discuss about the contest.
Sorry for announcing too late. (Actually, no one write about this so I wrote this blog.)

Read more »

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

By E869120, 3 years ago, In English

Dear Codeforces.

This afternoon, I read the announcement of Codeforces Round #444, and I understood about the unrated incident, and the reality of the downvotes — The topic rating was -489.

Actually, I already wrote problems in 6 contests in AtCoder — 4 unofficial contests (Square869120Contest) and 2 official contest. At first, I thought that writing problems is also fun, and becoming the writer is also a honor.

But I saw about so many downvotes — even this may completely changed the writer's life. In reality, his contest has so many mistakes in a single contest, but I knew that the writer could be the worst contributor out of 20000 people.

So, today, I felt fear to writing problems and being the writer.

Human always have a probability to make some mistakes. Fortunately, there are no serious bug in my contests, and all official contests which I already wrote was rated. But any time any people can make mistake. So all of the writer always have probability to fail and get -500 downvotes, and finally they may die in competitive programming.

What is your opinion? I want to listen others' opinion.

E869120

Read more »

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

By E869120, 3 years ago, In English

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!

Rank Username A B C D WA/TLE Total
1 mamekin 00'54" 02'21" 07'30" 16'04" 0 16'04"
2 uwi 00'58" 03'00" 10'05" 19'40" 0 19'40"
3 dreamoon 01'29" 02'50" 07'28" 17'41" 1 22'41"
4 sugim48 00'37" 01'47" 05'11" 18'06" 1 23'06"
5 kobae964 00'59" 02'05" 06'38" 18'09" 1 23'09"
6 Warden 02'18" 04'49" 10'39" 23'31" 0 23'31"
7 TangentDay 00'37" 02'13" 06'13" 24'32" 0 24'32"
8 cyand1317 24'51" 24'51" 24'50" 24'50" 0 24'51"
9 femto16 01'26" 03'14" 08'45" 25'10" 0 25'10"
10 iehn 01'16" 02'25" 07'38" 27'26" 0 27'26"

Read more »

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

By E869120, 3 years ago, In English

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.)

For example, the standard time in Beijing is UTC+8, so around 65% of contest starts at 22:00 or later, and ends at 24:00 or later. A large amount of participants are students, and I think 24:00-03:00 is too late time for student. If they saw systemtest and rating change, the sleeping time could be one hour later.

The other example is in New York. The standard time is UTC-5, so around 95% of contest starts at 12:00 or earlier, and ends at 14:00 or earlier. I think it is too early time, and the time overlaps for most people because of school or working. They can wake up more earlier, but I think morning is busy time for the most, so it's difficult to make time to participate a single contest in morning.

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.

This system in my suggestion is like TopCoder. (Contest time is not too biased)

I think this made some good effects and bad effects as follows:
  • 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.

This is just my suggestion, but I think this is also a strategy to increase users and to make codeforces more active.

Thank you for listening.

Read more »

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

By E869120, history, 3 years ago, In English

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.

Read more »

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

By E869120, 3 years ago, In English

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

RankCompetitorTotal Point
1yosupo1126.37
2Petr743.11
3tourist733.44
4sky58722.65
5nika710.03

2. Division 2
RankCompetitorTotal Point
1r3gz3n782.27
2mariandz781.66
3Trias757.82
4geek_geek750.79
5sachintcthope739.68

Congraturations to winners!

Read more »

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

By E869120, history, 3 years ago, In English

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.

This is a mystery of CF Judge Queue. Why these things can be occur?

UPD 1: Now Codeforces Judge is moving again.
UPD 2: Now Judge Queue is moving as usual, and solutions are judged within 5 minutes after submissions. Thank you for Codeforces!

Read more »

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

By E869120, 3 years ago, In English

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.

AtCoder
  • 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.

TopCoder
  • 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.

In order to solve problems, you should make a Bingo like example.
In addition, most of these problem is easy, especially concept. So you should see editorials if you can't reach idea 10 minutes.

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)

In addition, I think that you should mind fast-solving in latter problems. (After solved 15-30 problems)
In order to mind fast-solving, you should use timer. You should count from "opening problem statement" to "getting AC". If you can, I think that you should make a spreadsheet of problem, solved and time.


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.

Judge Concept Imprementation Fast solving Level
Codeforces Div2 C 50% o 50% 1500-1800
TopCoder Div1 Easy o x o 1500-2000
AtCoder ABC/ARC-D 50% o 50% 1400-1600

I suggest these two ways to improve rating as far as see the table:

  • 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.

My rating increased sharply when I started TopCoder Div1Easy, and solved ~50 Div1Easy problems. This is why I suggest TopCoder Div1 Easy for concept-practice.
In addition, you should use timer for practicing fast-solving. You can use competitiveprogramming.info to solve TopCoder Div1Easy, and you can make spreadsheet like following picture to solve TopCoder. (This is example of Div1Med that I am using.)



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.)
I think making library is good because you can shorten the time that writing RMQ class, BIT class, etc.
And to overcoming your weakness, I suggest that analyze your time in contest and practice, scoring and make a spreadsheet as follows:



2. Rating 1900 --> 2000
This step's range is only 100, but I think this is difficult as far as see A mystery of CF rating distribution. There are many people in [1900, 2000), but there aren't many people in 2000+. In Div1, there are many concept-main problems. So I think these two are useful for practice:

  • 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.

These problems are so difficult, so I suggest that you should give up and see the editorials if you can't get any idea though you try over 80-150 minutes. In addition, ARC-E is difficult for 1900, so I think you don't have to mind fast-solving.


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!

Read more »

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

By E869120, 3 years ago, In English

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:

Time elpased Upvotes / Downvotes
0 min 0
15 mins +7
18 mins -3
60 mins +16
8 hours 0
9 hours +2
14 hours -19
18 hours -7
24 hours -30
36 hours -50

I hoped that the incident won't got worse, but it was worse very much. The number of downvotes in the incident was:
Funny story Myst. Vol 4 (deleted) Myst. Vol 3 (deleted) Myst. Vol 2 Myst. Vol 1 s8pc editorial Total
-60 (0 -> -60) -47 (+25 -> -22) -25 (+50 -> +25) -51 (+114 -> +63) -25 (+154 -> +129) -10 (+19 -> +9) -218

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.

Tutorial Funny story Myst. Vol 2 Myst. Vol 1 Total
-20 (+180 -> +160) -15 (-60 -> -75) -20 (+63 -> +43) -20 (+129 -> +109) -75 (Total -293)

Funny Story with "20"!?
I think this incident is so serious, and I never heard a bigger downvote incident than it in CodeForces. I really want who made 10 fake account and downvoted me. Making fake account is also an immoral thing, so please comment this blog if you make 10 fake account.

By the way, thank you for reading!

Read more »

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

By E869120, 3 years ago, In English

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.

However, there was some surprising thing about it.
Look at following graph:

Note: The distribution graph has Logarithmic scale. Every time the scale increases by 1, the value doubles (2 times).

The surprising things are following:
  • 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.

Read more »

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

By E869120, 3 years ago, In English

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 pn be the place of people who has rating n.
  • The number of people in range [1000, 1050) is p999p1049, the number of people in range [1050, 1100) is p1049p1099, ...

However, there was some surprising thing about it.
Look at following graph:

  • 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.

Why these things can be occur?

UPD: The graph was extended.
UPD2: The average rating was calculated.
UPD3: The distribution and searchings about codeforces contribution is Here.

Read more »

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

By E869120, 3 years ago, In English

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.

For example:
 abcde -> zzzzz(changed)
bbbbb
ccccc
ddddd
Mr.X: cprpr
In this example, Mr.X's index changed from 4 to 3.

Adittionally, The maximum and minimum value of Mr.X's index can find for this way:
  • Minimum: When all characters of '?' in the list are 'z'.
  • Maximum: When all characters of '?' in the list are 'a'.
Since possible index of the handle name of Mr.X is "Range", you can solve this problem with only minimum-value and maximum-value.


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.
So, you can get 120 points in this way.

Let's think about "What buildings should be visible". (The number of should-visible buildings must be greater than K)
There are N buildings along the line, so you have to think only 2N ways.

You can use greedy method to solve the following problem:
  • You are given the index of buildings that should be visible.
  • Find the minimum cost.
The greedy method is here:
 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)
You can solve this problem (Max point) with brute-force method and greedy method.
The complexityis O(2N).


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).
The complexity is O(M) + O(M) = O(M).


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.
The answer of node i is average of {dp[i], dp[i], ..., dp[i], dp2[i]}. dp[i] comes p - 1 times. The complexity is O(N) + O(N) = O(N).


Thank you for looking this page.
I hope that you can use the commentary to solve the problem of s8pc or review the contest.

Please wait for a while for editorial between problem E to H.

Read more »

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

By E869120, 3 years ago, In English

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.

Read more »

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