Hi.

Thanks to kostka, this weekend you can participate virtually in an old edition of Polish olympiad: POI XVIII, stage 2. There are two days of a contest, Saturday and Sunday, 9-14 CET (check your timezone here). An hour after the contest ends on Sunday (so, 15 CET), I will talk about problems from both days in a stream. You can watch me on Youtube and Twitch.

Create an account in Szkopul first, link. The statements will be both in Polish and English, or the link to the English version will be provided as an announcement.

If you can't participate, I still recommend you to read the problems and try to solve them yourself before my stream.

Hi. I'm finally done with organizing Algorithmic Engagements, and I have time to go back to my streams!

Other Twitch programming streamers usually just do their job/project and they stream that. I'm going to do a similar thing. So, apart from my lectures and problem-solving streams, I will do a weekly longer stream, maybe around 6 hours.

My first Boring Programming Stream will be on Wednesday Tuesday (10am to 4pm CET, youtube link with countdown) and some of the things I might do are:

• Writing editorials for my old problems.
• Adding timestamps to my lectures on Youtube.
• Planning the next lecture (or Facebook posts).
• Reading the "Segment tree beats" blog (I know that tree, but I've never read examples and tasks given there).
• Learning how to edit videos.
• Reading Codeforces comments and maybe helping someone with a problem.
• Learning how to use OneNote for drawing.
• Choosing graphics (banner and thumbnails) for my channel.
• Answering people's questions and comments.

This is something that I would do anyway, and it isn't confidential (unlike preparing problems), so I can stream it and allow people to hang out with me. Feel free to suggest something via discord or in the comments below this blog, but please notice that I will mainly do things that I need/want to do.

Cheers.

My Youtube channel: https://www.youtube.com/errichto.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Competitive Programming Discord: https://discordapp.com/invite/UzaURu7.

Wednesday evening (check your time zone) I will stream solving an AI bot problem on Codingame, https://www.codingame.com/ide/challenge/xmas-rush. As usually, I will talk a lot about what I'm doing. The goal is to show you how to approach this kind of problems.

Link to the stream on Youtube (and currently just the countdown): link.

If you want to chat with me before or after the stream, visit the Competitive Programming discord, link.

Hi. I'm back from USA!

I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: https://www.youtube.com/watch?v=7hFWrKa6yRM. Watch me live (and ask questions), or just watch the video later. This will be part 1, and I will do part 2 in a few days (maybe Tuesday).

UPDATE — part 2 is coming on Thursday, same time. Link: https://www.youtube.com/watch?v=gXxu-Cr4b4c.

There are no prerequisites this time. I recommend reading the materials below in advance, and trying to solve problems 1 and 5. If you are strong, just read problems and see if you can't solve something (maybe problem 8?).

Technique "Exchange Arguments"

If we're given n items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do O(N²) dynamic programming. The dp should be dp[pref][used] — best possible result (balance) if we chose used items so far (in the prefix pref).

"Strange/tricky comparator" checks which of the two elements should be earlier, usually just solving the problem for N = 2.

Instruction

I recommend this blog also for red users. Read the theory and problems below, try to solve them. For solutions and extra insight/tips, watch my stream on Monday or watch the video later. If you aren't familiar with EV or summing problems, see part 1 first: http://codeforces.com/blog/entry/62690.

I will stream a lecture on Monday at 14:00 CEST — https://www.youtube.com/watch?v=HDk6zQw0Rdo (also Twitch). I will go through theory and problems from this blog.

Expected Value theory, part 2

We roll a 6-sided die. Remember, EV of square of the number of pips is something different than square of EV:

Two events are independent if the result of one doesn't affect the distribution of p-bilities of the other. Results of throwing two dice (or throwing one die twice) are independent, but the amount of rain and the strength of wind are dependent.

part 2: https://codeforces.com/blog/entry/62792

Watch my lecture-stream tomorrow (Thursday) at 14:00 CEST — https://www.youtube.com/watch?v=qdlPY37MBPo https://www.youtube.com/watch?v=U_h3IjreRek. I will go through theory and problems from this blog. The only prerequisite is knowing what is probability. The next (harder) part on Monday.

The video will be available later, with timestamps for each problem — so you don't have to watch everything.

Definition of EV

Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$ with p-bility 2%. On average, it gives us 0.1·10 + 0.02·20 = 1.4, so we are worse off after buying the ticket. The computed average is called the expected value.

The expected value (EV, expectation) is the average value of an event/experiment. For example, EV of the number of pips rolled on a 6-sided die is 3.5:

Linearity of EV (super important theorem):

If you use Facebook, you might want to check out my new page https://www.facebook.com/errichto. I will post some short problems, puzzles I know/heard (maybe also not-algo puzzles, who knows), mention upcoming contests or cool problems from recent ones, sometimes share my thoughts about an algorithm or a contest. Kind of a blog, but likely with shorter but more frequent posts. Cheers!

PS. next Competitive Programming stream will be on Monday, div2 C-D problems from recent CF rounds, 12pm CEST.

Hi.

There is a new game where you can win $10k for writing the best bot for a 2-player game Terminal: https://terminal.c1games.com. There are some smaller local competitions, mainly for universities. In short, it's a tower-defense game where you build towers to defend against minions sent by your opponent, and at the same time you attack with minions too.

I have some experience with games like this (we had a few 24-hour game-bot competitions in Poland), so I think I can share some knowledge and intuition. I will stream on Wednesday (1pm CEST), Friday and Sunday. You can see the exact time on my Youtube channel as a scheduled event. If you miss it, you can watch a video later.

I talked with contest organizers and they encourage the stream, but ofc. you shouldn't expect to hear something enough to get top1.

See you.

Hello again.

Next stream will start tomorrow (Wednesday) at 2pm CEST (your timezone), solving problems from POI 22, round 1 (link). It will be on my Youtube channel.

I did two streams this weekend that you can now find on my youtube channel. The first with quite easy Codeforces problems that I solved from scratch (I haven't seen them before), also implementing them. The second one with a bit harder Topcoder problems that I've solved before, but I didn't necessarily remember the solution now — and for those I only described the solution, without implementation. The streams were fine but there are a lot of things to improve.

I wanted to see two things:

1. Can I stream? Am I able to try to solve a hard problem and at the same time talk in English, that isn't my native language? So so. It wasn't a disaster, but I hoped to be better, more efficient. I think I'm not able to stream solving hard problems from scratch, without knowing the solution already. Not if I want to keep it educational and spend time explaining everything.
2. Do people like it? Yes, apparently they did :)

I watched some of Petr's streams and I would say he shares his thought process, basically saying out loud what he thinks about. But he doesn't explain things. It's an interesting thing but I don't see learning from that. Still, I think it's the best possible format of streaming an actual contest, where you shouldn't waste time. I also think that I would do it much worse: I'm worse in CP and in English proficiency.

$$

I want to try streaming competitive programming. The goal is to make it educational so I will be talking a lot, also answering (at least some) questions.

I'm planning three completely different streams to see what format to use:

1. Solving random easy-medium problems.
2. Solving old problems from Polish olympiad.
3. Post-contest stream, assuming I'm a setter or tester of a contest. Similar to what scott_wu, ecnerwala and stevenkplus did.

Any thoughts, ideas?

The first stream will most likely be on Sunday, starting around 7-8pm CEST. I will use Twitch and talk in English only. These first streams should show me and you whether it's cool and useful, and whether I like doing it.

Also, I will try to make the video accessible later.

--- UPDATE ---

The first stream will start on Saturday at 10am CEST (check your timezone) here: https://www.twitch.tv/errichto. I will solve some div1 A-C problems, not necessarily from Codeforces.

--- UPDATE 2 ---

The second stream on Sunday evening, with problems from POI 22, round 1. You can try to solve them yourself first — link. I will do problems from POI in a few days.

I will start today at 19:35 CEST (check your timezone) and I will talk about hard problems from this year TCO qualification rounds. If I do well in SRM today, I can start with problems from the round first. So, the main topic is hard DP problems, I guess. I prefer to stream on Youtube today, but I have some difficulties. I will announce here where the stream will happen. If someone has experience with Youtube live, please write to me.

I will stream on Youtube: https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg.

--- UPDATE 3 ---

SRM was moved by one hour, so my stream will start at 20:35 CEST.

I initially wrote a longer comment on Radewoosh's blog but realized the following part is a completely separate thing.

Wanting to get contribution is a good thing.

It's an incentive to literally contribute to the community. This is how rankings work. People dream to be top10 rating one day and it motivates them to work harder. The "top contributors" list has the same goal: to incentivize people to help others.

I don't mind if someone says "you want to get to top10 contribution" to me, and I joke with friends about it (also about Swistakk and Radewoosh). The bad thing is that a comment like this can be seen by others and make them less motivated (maybe unconsciously) to contribute. You likely don't realize how much the feedback matters. Preparing contests isn't more profitable than working in a company, but it's so rewarding to know some people liked your problems that it motivates you to do it again. It should be similar for writing educational blogs.

The contribution isn't a perfect measurement and for example fcspartakm has so incredible impact on the whole CP world (he works on Polygon) that he deserves to be top10 easily. There are so many people contributing locally too. kostka recently organized a relatively cheap camp for polish representation for IOI (and a few people next in line). He invited me and a few others as organizers and paid us, did most of the problems-related job himself anyway. We got some money (a payment/salary as agreed earlier), he didn't. He spent week+ of his time and some money on gasoline, and he didn't get anything. It's good to appreciate people like that. While an upvote is a nice easy thing, remember that you can always let them know that you appreciate their job and commitment.

(And I'm not saying you should start spamming some people now, because that would be annoying for them ;p )

So remember: saying "you just want contribution" basically means "you just want people to find your comment/blog useful". It's a very stupid insult. Btw. I have some predictions about the first comment under this blog xd

What do you think about Topcoder's policy regarding (not) revealing the author before the round? This time I was allowed to announce I'm an author (btw. do participate in SRM 727!) but it was generally forbidden so far. Should it stay that way? Cons of announcing the author:

1. Every problem setter has their own style of problems. Some people will skip rounds of some setters because they don't like some type of problems. So one should carefully choose rounds in order to maximize their rating.
2. Knowing the problem author might help you in solving a problem, e.g. when you know this author loves flows.
3. Rounds of new setters aren't that attractive so they might get fewer participants.

My opinion is that one's rating doesn't matter much so (1) isn't important. Similarly, I'm fine with the fact that you can read problems in CF but decide not to participate — it doesn't affect me much.

If we want to deal with (2), we would also have to forbid any personal references in the statements. I wouldn't want that.

The last thing (3) is actually fine in my opinion. The author should try their best to prepare nice problems and his/her reward will be high participation in his/her next round.

Pros of announcing:

1. Hopefully more participants in general. As an author, I want my round to get many participants and thus I announce it on CF and I invite my friends on facebook or in person. Let's also note that usually a problem setter and thus his/her friends are highly rated — in some way they make the contest more prestigious and indirectly increase the participation in the future.
2. I don't have to hide from friends that I'm preparing a round. While it's normal to not show statements, solutions, etc., it's very hard to ensure that nobody sees that I use topcoder software or that I'm current coding in Intelli (what implies Java that I use only for TC). I'm talking mainly about programming camps where I'm usually not alone in a room. On the other hand, I once talked with Petr about this and he gave a good counterargument: a setter is paid for their work and there might be some requirements, also about keeping something secret.
3. As a participant, I'm more eager to attend rounds of some authors. If I like their problems, I'm more likely to skip classes or stay awake until 3am. Thus, I prefer to know.
4. Other platforms reveal everything and nobody complies.

My opinion is that authors or particular problems should be secret only for big important contests like IOI, acm regionals and WF, TCO. We usually know who authors are there but every detail matters there and thus we shouldn't know the exact author of each problem. And reasons about high/low participation don't matter there.

What is your opinion?

I wrote two comments to create a voting, but I think discussing arguments is much more important.

Hello, Codeforces!

I’d like you to invite for CodeChef April Lunchtime that will start in less than 3 hours (check your time zone here). The contest will last 3 hours.

Setters: Errichto, 300iq, and big help from PraveenDhinwa. Main tester: Lewin. Editorials: mgch. Translators: 300iq (Russian), huzecong (Mandarin) and VNOI team (Vietnamese). Language verification: arjunarul.

There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).

You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score. The contest should be a bit easier than a Div1 Codeforces round. Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.

I wish you great fun and no frustrating bugs. Hope to see a lot of you on the leaderboard!

Good evening.

I’d like you to invite for CodeChef April Cook-Off that will start at 21:30 IST of 23rd April 2017 (check your time zone here) and will last 2.5 hours.

Problems are prepared by me and kingofnumbers. Testers are mnbvmar and PraveenDhinwa (who is also an editorialist). Translators: huzecong, Team VNOI, CherryTree (Mandarin, Vietnamese and Russian respectively).

There is no registration required, anybody with a CodeChef handle can participate.

We want cook-off contests to attract even the strongest competitors. You will be provided 5 problems, with difficulty div2-A through div1-E. We expect even the best to struggle to solve all the problems.

I wish you great fun and no frustrating bugs. See you on the leaderboard!

Additional announcement: we look for setters, testers and editorialists, especially for a setter for the coming lunchtime contest. You can reach me by PM on Codeforces.

Hello, Codeforces!

The CodeChef April Challenge will end in less than 4 days. You can still join and reach the top of the leaderboard. There are 9 binary/subtask problems and 1 approximation problem (a tie-breaker).

I was a tester and an author of some problems. Other problem setters are: gautam27, Frank Chen, cgy4ever, Sereja, and PraveenDhinwa who is also an editorialist. Translators: CherryTree (Russian), Team VNOI (Vietnamese) and huzecong (Mandarin). Language verifier: arjunarul.

There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page). Prizes for first two places are 400$ and 300$.

I wish you great fun and no frustrating bugs. See you on the leaderboard!

Hi. I recently overcomplicated one easy-ish geometry problem and encountered the following difficulty.

Let's say I have a set of linear functions f(x) = ax + b and two types of online queries:

1. Given a and b, insert a new linear function.
2. Given x₀, print the maximum value f(x₀).

I can handle both queries in logarithmic time by using BST and maintaining the convex hull of linear functions. Can I do the same (easily?) using set in C++? The problem is that the second query requires lower_bound that is able to say whether a linear function is on the left or on the right from the optimal one. I think it's impossible because it depends on the neighboring (after sorting CH by slope) functions.

During a contest, I implemented something in O(log²) — a lower_bound that runs an internal lower_bound to find the next linear function in the set. Later I came up with an idea to extend a linear-function struct to also store a copy of the next function in the set. It requires some extra work but should work and should be O(log), right? Do you see any easier way?

Hello Codeforces!

I’d like you to invite for CodeChef March Lunchtime that will start at 19:30 IST of 25-th March 2017 (check your time zone here) and will last 3 hours.

I'm a setter. Testers: kingofnumbers, CherryTree. Translators: CherryTree (Russian), huzecong (Mandarin) and VNOI team (Vietnamese). Language verification: arjunarul.

There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).

You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score. The contest should be a bit easier than a Div1 Codeforces round. Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.

I wish you great fun and no frustrating bugs. Hope to see a lot of you on the leaderboard!

Code: 25627790

Code: 25627860

Code: 25627873.

Code: 25627885.

Code: 25627898.

Code: 25627911.

Code: 25627924.

Hello.

The round 1 of VK Cup 2017 will take place on March 18 at 18:35 MSK (check your timezone here), along with standard div1+2 Codeforces Round #405. The contest "VK Cup 2017 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, while other ones will have one more chance in the Wild Card Round 1 in April. Those who don't participate in the VK Cup can take part in the Codeforces Round #405 individually (problems will be available in English too). All three rounds last 2 hours, and all are rated.

I want to thank: KAN for his help in the contest preparation, MikeMirzayanov that we are here, AlexFetisov for testing, the VK company for this nice annual contest.

I'm a setter and I hope (and expect?) that you will enjoy the problems. During the contest, remember that you can read many problems and try to solve those that fit you most.

I wish you great fun and no frustrating bugs.

div2: 500-1000-1500-2000-2500
div1: 500-1000-1500- 2250 -2500
vk-cup: 250-500-1000-1500- 2250 -2500

The contest is over. See the editorial here. Congratulations to all who advanced to the next round, and congratulations to winners of each contest.

Specifically, the winners of VK Cup Round 1 are:

1. Zlobober, zemen
2. LHiC, V--o_o--V
3. Arthur, kefaa
4. map, Babanin_Ivan
5. felix, Trumen

The winners of parallel rounds are:

Div. 1:

1. -XraY-
2. Laakeri
3. Lewin
4. dotorya
5. RAVEman

Div. 2:

1. rupxup
2. YES_RPG
3. T0RRES
4. HXLLL
5. Len

I'm sorry for letting some slow solutions pass in the Rectangle Strips problem. I tried really hard to prepare tests there but apparently didn't succeed.

Hi everybody.

Deadline24 is an international programming marathon, organized continually since 2009 by Future Processing. During the contest, the teams of three tackle algorithmic problems.

The marathon is composed of two phases. The qualifying round starts on March 12. For 5 clock hours, the teams will be solving tasks and generating responses assessed by the verification server. This stage of the competition is remote. Then, the best teams of the qualifying round will meet at the 24-hour finals held on April 22-23, 2017, in Katowice (Poland).

The teams can sign up until March 9, 2017 (23.59 CET). Registration is available on the contest website www.deadline24.pl.

You can get familiar with the type and difficulty level of the tasks in the Qualifying round by competing in the GYM contest on this Thursday and will last 5 hours (check your timezone here). It will be a replay contest of the Qualifying Round 2016. The contest will appear in Codeforces GYM soon. Because of technical limitations, the scoring and final ranking system of that replay contest is not identical to the one used during the qualifying round — don't forget to visit the contest website (www.deadline24.pl) to read full rules (e.g. submitting time matters and you submit output files instead of codes).

I'm not one of organizers but I competed in some of previous editions and I enjoyed finals a lot. Now I was asked to help a bit with the GYM replay. On behalf of the organizers, I want to thank Mike Mirzayanov for his help in promoting the competition on CF.

Don't forget that the registration ends on Thursday! Good luck in the qualifying round.

UPD: the GYM contest will start with the delay of 30 minutes. Sorry for the inconvenience.

Hello Codeforces!

I'd like to invite you to CodeChef March Challenge that has just started and will last 10 days.

Let's see a colorful bunch of names. Testers: CherryTree and Errichto. Editorialist: pkacprzak. Translators: CherryTree (Russian), Team VNOI (Vietnamese) and huzecong (Mandarin). Language verifier: arjunarul. Contest admin: PraveenDhinwa.

Problem authors are: xennygrimmato, Errichto, PraveenDhinwa, kingofnumbers, Fekete, Alex_2oo8, Ioser.

There is no registration required, anybody with a CodeChef handle can participate. Top participants can win CodeChef laddus (details on the contest page). Unusually, there are extra prizes for top 10 women programmers (irrespective of their ranks) in form of 300 Laddus for the occasion of the International Women's Day. UPD: There is also money prize 400$ for the winner and 300$ for the second place.

You will be provided 10 problems of really various difficulty. While we hope everybody will solve a few simpler problems, we also think that hardest ones will be a challenge for the best. There are 9 problems with subtasks and 1 approximation problem (I personally hope to see a lot of submissions there). We hope you will enjoy the contest and learn something new and valuable.

I wish you great fun and no frustrating bugs. See you in the leaderboard!

EDIT: Updated info about prizes.

Hello Codeforces! Did you miss Limak?

I’d like you to invite for CodeChef February Lunchtime that will start at 19:35 IST / 17:05 MSK of 25-th February 2017 (check your time zone here) and will last 3 hours. The contest starts 5 minutes later than usually to allow you to catch a breath after the AtCoder Mujin Contest that ends at 17:00 MSK.

I am an author of problems and editorials, while niyaznigmatul is a tester. I want to thank PraveenDhinwa (who is a contest admin) and suraj_sharma for their technical help. Translators: CherryTree (Russian), huzecong (Mandarin) and VNOI team (Vietnamese). Language verification: arjunarul.

There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).

You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score. The contest should be a bit easier than a Div1 Codeforces round. I honestly think that all problems are interesting and valuable — some for beginners and some for experiences competitors (IMO one particular problem is so new and beautiful). Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.

I wish you great fun and no frustrating bugs. Hope to see a lot of you in the leaderboard!

EDIT: The time of start corrected to "19:35 IST / 17:05 MSK".

EDIT2: Bump, the contest starts in 24 hours.

EDIT3: The contest is over. I hope you enjoyed problems. You can find editorials here.

And congratulations to Petr, uwi and savinov for getting the top 3 places!

#include <vector>
int main() {
	std :: vector<int> w;
	for(int x : w);
}

The code above runs forever on my machine, after being compiled with g++ a.cpp (it first prints some warning), the same on ideone: http://ideone.com/5FodQO. Why? EDIT: As yeputons noticed, this bug was already reported by Mike Mirzayanov.

And the following code gives me RTE without any warning if compiled with g++ -O2 a.cpp — is it a compiler bug as well?

#include <bits/stdc++.h>
using namespace std;
struct Big {
	vector<int> w;
	Big(int x) {
		while(x) {
			w.push_back(x % 10);
			x /= 10;
		}
	}
	Big operator - () const {
		return Big(0) - *this;
	}
	int get(int i) const {
		if(i < (int) w.size()) return w[i];
		return 0;
	}
	Big operator - (const Big & other) const {
		Big ans(0);
		ans.w.resize(100, 0); // ans.w.resize(max(w.size(), other.w.size())); // gives RTE too
		puts("a");
		for(int i = 0; i < (int) ans.w.size(); ++i)
			ans.w[i] = get(i) - other.get(i);
			// ans.w[i] = (i < (int) w.size() ? w[i] : 0)
			//	- (i < (int) other.w.size() ? other.w[i] : 0); // gives RTE too
		puts("b");
		return ans;
	}
};
int main() {
	//Big(0) - Big(57); // this line works fine
	-Big(57);
}

You can download my codes to all problems here.

I will write a full editorial in the next few days. Now you can read hints and short solutions.

750B - New Year and North Pole

750C - New Year and Rating

750D - New Year and Fireworks

750E - New Year and Old Subsequence

750F - New Year and Finding Roots

Also, the solution description of this problem is split into parts hidden in ,,spoiler'' tags. At any moment you can stop reading and try to finish the solution on your own.

750G - New Year and Binary Tree Paths

750H - New Year and Snowy Grid

750A - New Year and Hurry

Do you see what is produced by the following piece of code?

int total = 0;
for(int i = 1; i <= n; ++i) {
	total += 5 * i;
	printf("%d\n", total);
}

We iterate over problems (a variable i denotes the index of problem) and in a variable total we store the total time needed to solve them. The code above would print numbers 5, 15, 30, 50, ... — the i-th of these numbers is the number of minutes the hero would spend to solve easiest i problems.

Inside the loop you should also check if there is enough time to make it to the party, i.e. check if total + k <= 240.

simple C++ code:24067296
shorter but harder C++ code: 24067301
python: 24067479

750B - New Year and North Pole

Our goal is to simulate Limak's journey and to check if he doesn't make any forbidden moves. To track his position, it's enough to store one variable denoting his current distance from the North Pole. To solve this problem, you should implement checking three conditions given in the statement.

Updating dist_from_north variable is an easy part. Moving t_i kilometers to the North increases the distance from the North Pole by t_i, while moving South decreases that distance by t_i. Moving to the West or East doesn't affect the distance from Poles, though you should still check if it doesn't happen when Limak is on one of two Poles — you must print "NO" in this case.

Let's proceed to checking the three conditions. First, Limak can't move further to the North if he is already on the North Pole "at any moment of time (before any of the instructions or while performing one of them)". So you should print "NO" if direction == "North" and either dist_from_north == 0 or dist_from_north < t[i]. The latter case happens e.g. if Limak is 150 kilometers from the North Pole and is supposed to move 170 kilometers to the North — after 150 kilometers he would reach the North Pole and couldn't move further to the North. In the intended solution below you will see an alternative implementation: after updating the value of dist_from_north we can check if dist_from_north < 0 — it would mean that Limak tried to move North from the North Pole. Also, you should print "NO" if dist_from_north == 0 (i.e. Limak is on the North Pole) and the direction is West or East.

You should deal with the South Pole case in a similar way. Limak is on the South Pole when dist_from_north == M.

Finally, you must check if Limak finished on the North Pole, i.e. dist_from_north == 0.

There were two common doubts about this problem: 1) "Limak is allowed to move 40 000 kilometers to the South from the North Pole and will be again on the North Pole." 2) "Moving West/East may change the latitude (equivalently: the distance from Poles) and this problem is hard 3d geometry problem." Both doubts make sense because they come from misinterpreting a problem as: Limak looks in the direction represented by the given string (e.g. to the North) and just goes straight in that direction (maybe after some time he will start moving to the South but he doesn't care about it). What organizers meant is that Limak should be directed in the given direction at any moment of time, i.e. he should continuously move in that direction. It's a sad thing that many participants struggled with that. I should have written the statement better and I'm sorry about it.

C++ code: 24067685
python code: 24067669

750C - New Year and Rating

We don't know the initial or final rating but we can use the given rating changes to draw a plot of function representing Limak's rating. For each contest we also know in which division Limak was.

Red and blue points denote contests in div1 and div2. Note that we still don't know exact rating at any moment.

Let's say that a border is a horizontal line at height 1900. Points above the border and exactly on it should be red, while points below should be blue. Fixing the placement of the border will give us the answer (because then we will know height of all points). Let's find the highest blue point and the lowest red point — the border can lie anywhere between them, i.e. anywhere between these two horizontal lines:

Small detail: the border can lie exactly on the upper line (because rating 1900 belongs to div1) but it can't lie exactly on the lower line (because 1900 doesn't belong to div2).

The last step is to decide where exactly it's best to put the border. The answer will be 1900 + d where d is the difference between the height of the border and the height of the last point (representing the last contest), so we should place the border as low as possible: just over the lower of two horizontal lines we found. It means that the highest blue point should be at height 1899.

There is an alternative explanation. If Limak never had rating exactly 1899, we could increase his rating at the beginning by 1 (thus moving up the whole plot of the function by 1) and everything would still be fine, while the answer increased.

To implement this solution, you should find prefix sums of rating changes (what represents the height of points on drawings above, for a moment assuming that the first point has height 0) and compute two values: the smallest prefix sum ending in a div1 contest and the greatest prefix sum ending in a div2 contest. If the first value is less than or equal to the second value, you should print "Impossible" — it means that the highest blue point isn't lower that the lowest red point. If all contests were in div1, we should print "Infinity" because there is no upper limit for Limak's rating at any time (and there is no upper limit for the placement of the border). Otherwise we say that the highest blue point (a div2 contest with the greatest prefix sum) is a contest when Limak had rating 1899 and we easily compute the final rating.

O(n) code in C++: 24069564
code in C++, with binary search: 24069586

750D - New Year and Fireworks

A trivial O(2ⁿ) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for t_i, a backtrack with memoization has much better complexity. Let's understand the reason.

Parts of the firework move by t_i in the i-th level of recursion so they can't reach cells further than from the starting cell. That sum can't exceed n·max_t = 150. We can't visit cells with bigger coordinates so there are only O((n·max_t)²) cells we can visit.

As usually in backtracks with memoization, for every state we can do computations only once — let's think what that "state" is. We can't say that a state is defined by the current cell only, because maybe before we visited it going in a different direction and now we would reach new cells. It also isn't correct to say that we can skip further simulation if we've already been in this cell going in the same direction, because maybe it was the different level of recursion (so now next step will in in a different direction, what can allow us to visit new cells). It turns out that a state must be defined by four values: two coordinates, a direction and a level of recursion (there are 8 possible directions). One way to implement this approach is to create set<vector<int>> visitedStates where each vector contains four values that represent a state.

The complexity is what is enough to get AC. It isn't hard to get rid of the logarithm factor what you can see in the last code below.

If implementing the simulation part is hard for you, see the first code below with too slow exponential solution. It shows an easy way to deal with 8 directions and changing the direction by 45 degrees — you can spend a moment to hardcode changes of x and y for each direction and clockwise or counter-clockwise order and then keep an integer variable and change its value by 1 modulo 8. You can add memoization to this slow code yourself and try to get AC.

too slow O(2ⁿ) approach (TLE): 24070543
the same code with memoization (AC): 24070548
faster memoization without logarithm (AC): 24070567

750E - New Year and Old Subsequence

It's often helpful to think about an algorithm to solve some easier problem. To check if a string has a subsequence "2017", we can find the find the first '2', then to the right from that place find the first '0', then first '1', then first '7'. If in some of these 4 steps we can't find the needed digit on the right, the string doesn't have "2017" as a subsequence. To additionally check if there is a subsequence "2016", after finding '1' (before finding '7') we should check if there is any '6' on the right. Let's refer to this algorithm as Algo.

It turns out that the problem can be solved with a segment tree (btw. the solution will also allow for queries changing some digits). The difficulty is to choose what we want to store in its nodes. Let's first use the Algo to answer simpler queries: "for the given segment check if it's nice".

There is only one thing that matters for segments represented by nodes. For a segment we want to know for every prefix of "2017" (e.g. for "20"): assuming that the Algo already got this prefix as a subsequence, what is the prefix we have after the Algo processes this segment. Let's see an example.

TODO

750F - New Year and Finding Roots

750G - New Year and Binary Tree Paths

Iterate over L and R — the length of sides of a path. A "side" is a part from LCA (the highest point of a path) to one of the ends of a path.

For fixed LCA and length of sides, let the "minimal" path denote a path with the minimum possible sum of values. In each of the sides, this path goes to the left child all the time:

If the LCA is x, the smallest possible sum of vertices on the left side of the minimal path has the sum of vertices:

We can find a similar formula for the minimum possible sum of the right side S_R. For fixed L, R, x, the total sum of any path (also counting LCA itself) is at least:

From this, with binary search or just a division, we can compute the largest x where this formula doesn't exceed the given s. This is the only possible value of LCA. Larger x would result with the sum exceeding s. Smaller x would result in too small sum, even if a path goes to the right child all the time (so, the sum is maximized). Proof: every vertex is strictly smaller than the corresponding vertex in the "minimal" path for the computed largest possible x:

So, from L and R we can get the value of LCA.

Let's assume that the computed value of LCA is 1. For any other value we know that the value of vertex on depth k would be greater by (x - 1)·2^k compared to LCA equal to 1, and we know depths of all vertices on a path, so we can subtract the sum of those differences from s, and assume the LCA is 1.

The sum of vertices from 1 to a is 2·a - popcount(a). Proof: if the binary representation of a has 1 on the i-th position from the right, there will be 1 on the (i - 1)-th position in the index of the parent of a and so on. So this bit adds 2ⁱ + 2^i - 1 + ... + 1 = 2^i + 1 - 1 = 2·2ⁱ - 1, so everything is doubled, and we get "-1" the number of times equal to the number of 1's in the binary representation of a. Thus, the formula is 2·a - popcount(a).

If endpoints are a and b, the sum of vertices will be 2·a - popcount(a) + 2·b - popcount(b) - 1 (we subtract the LCA that was counted twice). Since popcounts are small, we can iterate over each of them and we know the left value of equation:

Here, s' is equal to the initial s minus whatever we subtracted when changing LCA from the binary-searched x to 1.

The remaining problem is: Given binary lengths L and R of numbers a and b, their popcounts, and the sum a + b, find the number of such pairs (a, b). This can be solved in standard dynamic programming on digits.

To slightly improve the complexity, we can iterate over the sum popcount(a) + popcount(b) instead of the two popcounts separately. The required complexity is or better.

750H - New Year and Snowy Grid

Let's solve an easier problem first. For every query, we just want to say if Limak can get from one corner to the other. He can't do that if and only if blocked cells connect the top-right side with the bottom-left side — this is called a dual problem.

On the drawing above, the top-right side and bottom-left side are marked with blue, and blocked cells are black. There is a path of blocked cells between the two sides what means that Limak can't get from top-left to bottom-right corner. The duality in graphs changes the definition of adjacency from "sharing a side" to "touching by a corner or side" — the black cells on the drawing aren't side-adjacent but they still block Limak from passing through. Similarly, if Limak was allowed to move to any of 8 corner/side-adjacent cells, black cells would have to touch by sides to block Limak from passing through.

The idea of a solution is to find CC's (connected components) of blocked cells before reading queries, and then for every query see what CC's are connected with each other by temporarily blocked cells. To make our life easier, let's treat the blue sides as blocked cells too by expanding the grid by 1 in every direction. Then for every query, we want to check if new blocked cells connect the bottom-left CC and top-right CC.

Before reading queries, we can find CC's of blocked cells (remember that a cell has 8 adjacent cells now!). Let's name those initial CC's as regions. When a temporarily blocked cell appears, we iterate through the adjacent cells and if some of them belong to initial regions, we apply find&union to mark some regions as connected to each other (and connected to this new cell that is a temporary region of size 1). This can be done in where k is the number of temporarily blocked cells. This solves the easier version of a problem, where we just check if Limak can get from one corner to the other — if the two special regions are connected at the end then the answer is "NO", and it's "YES" otherwise.

What about the full problem? Limak wants to move to the opposite corner and back, not using the same cell twice. If you treat a grid as a graph, this means checking if there is a cycle passing through the two corners (a cycle without repeated vertices). It's reasonable to then think about bridges and articulation points. An articulation point here would be such a cell that making it blocked would disconnect the two corners from each other — it's a cell that Limak must go through on both parts of his journey. Our dual problem becomes: check if the two sides are almost connected i.e. it's enough to add one more blocked cell to make the connection (that cell must be an articulation point). The previously described solution needs some modification.

We did F&U on regions adjacent to temporarily blocked cells. If some region was connected with some other region in the current query, let's call it an interesting region — there are O(k) of them. If we preprocess the set of pairs of regions that are initially almost connected (it's enough to add one more blocked cell to make them connected), we can then for a query iterate over pairs: a region connected to the bottom-right side and a region connected to the other side, and check if this pair is in the set of almost-connected regions. There are O(k²) pairs and if any of them is almost-connected, we have an almost-connection between the two sides and we print "NO", because Limak can't avoid revisiting cells.

My code: 50164800.

Hello everybody!

On December 30 at 14:05 UTC/17:05 MSK (check your time zone here) Codeforces will host the New Year's contest Good Bye 2016. The contest is combined for both divisions, lasts 2.5 hours and contains 8 problems. Thanks to Harbour.Space and Barcelona ACM-ICPC Programming Bootcamp 2017 sponsoring the contest, winners can expect really cool prizes:

• 5 best participants (not ACM ICPC veterans) will win free participation in Hello Barcelona programming bootcamp.
• 30 best participants (not ACM ICPC veterans) will receive a 30% discount for participation in Hello Barcelona programming bootcamp.
• 100 best participants will receive t-shrits by organizers and Codeforces.

Hello Barcelona programming bootcamp in collaboration with Moscow Workshops ACM ICPC is a competitive programming training camp to be held between February 6-14, 2017 at Harbour.Space University in Barcelona. Note that lecturers and coaches are: GlebsHP, MikeMirzayanov, Endagorion, Michael, Jacob and snarknews, so the camp must be valuable. The registration is open up to January 20th, 2017.

More information can be found here: http://in.harbour.space/icpc/

I'm an author of problems. I want to thank several people. MikeMirzayanov for creating Codeforces and Polygon and for allowing me to prepare this contest. GlebsHP for his help in everything (hope to work with you again!). mareksom for testing (other testers TBA). My sister for drawing. I also want to thank the Hello Barcelona organizers for providing nice prizes for you.

I'm proud of the problem set and I think that everybody will find something interesting for themselves. I tried to keep statements shorter than usually so it may be a good idea for you to read more problems and choose one that fits you. Obviously, problems will be about the New Year and a little polar bear whom you might know. Since you will face one interactive problem, please read the Interactive Problem Guide in advance.

Don't forget to register. I wish you great fun and no frustrating bugs.

UPD1: The points drop will be adjusted to the round length. It means that for submitting e.g. at the end of the contest gives the same percent of points as in usual 2-hour rounds. Also, I remind you that there will be an interactive problem (as mentioned above).

UPD2: In 750F - Новый год и поиск корня the interactor was printing neibhours in format "k t1 ... tk" instead of "k\nt1 ... tk" (in one line instead of two lines). It's my fault and I'm sorry for the inconvenience. If you were heavily affected, please write to me or GlebsHP. And thanks for noticing/guessing, Gassa!

UPD3, WINNERS

1. Petr
2. tourist
3. rng_58
4. mnbvmar
5. Kostroma
6. Rafbill
7. Egor
8. ainta
9. al13n
10. molamola.

Congratulations!

Thanks for participating. If you want to know intended solutions, see the editorial (it isn't completely ready yet though). See you next time and have an awesome New Year!