### Errichto's blog

By Errichto, 13 days ago, ,

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.



•
• +240
•

By Errichto, 3 weeks ago, ,

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.

--- UPDATE 3 ---

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

•
• +973
•

By Errichto, 2 months ago, ,

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

•
• +460
•

By Errichto, 9 months ago, ,

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.

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

•
• +178
•

By Errichto, 18 months ago, ,

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, gainullin.ildar, and big help from PraveenDhinwa. Main tester: lewin. Editorials: mgch. Translators: gainullin.ildar (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!

•
• +51
•

By Errichto, 18 months ago, ,

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.

•
• +85
•

By Errichto, 18 months ago, ,

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!

•
• +38
•

By Errichto, 19 months ago, ,

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 x0, print the maximum value f(x0).

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(log2) — 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?

•
• +43
•

By Errichto, 19 months ago, ,

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!

•
• +72
•

By Errichto, 19 months ago, ,

Code: 25627790

Code: 25627860

Code: 25627873.

Code: 25627885.

Code: 25627898.

Code: 25627911.

Code: 25627924.

Tutorial of VK Cup 2017 - Round 1

•
• +51
•

By Errichto, 19 months ago, ,

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:

The winners of parallel rounds are:

Div. 1:

Div. 2:

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.

Announcement of VK Cup 2017 - Round 1

•
• +286
•

By Errichto, 19 months ago, ,

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.

•
• +161
•

By Errichto, 19 months ago, ,

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: spectral, Errichto, PraveenDhinwa, kingofnumbers, Fekete, Alex_2oo8, I_love_PHP.

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!

•
• +82
•

By Errichto, 20 months ago, ,

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!

•
• +61
•

By Errichto, 20 months ago, ,
#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);
}


•
• +77
•

By Errichto, 22 months ago, ,

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

hint

750C - New Year and Rating

hint1
hint2

750D - New Year and Fireworks

hint1
hint2
solution

750E - New Year and Old Subsequence

hint1
hint2
hint3
hint4

750F - New Year and Finding Roots

part1
part2
part3
part4
part5

750G - New Year and Binary Tree Paths

hint1
hint2
hint3
hint4
hint5
hint6

750H - New Year and Snowy Grid

hint1
hint2

# 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 ti kilometers to the North increases the distance from the North Pole by ti, while moving South decreases that distance by ti. 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(2n) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for ti, a backtrack with memoization has much better complexity. Let's understand the reason.

Parts of the firework move by ti 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)2) 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(2n) 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

Tutorial of Good Bye 2016

•
• +168
•

By Errichto, 22 months ago, ,

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.

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 - New Year and Finding Roots 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

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!

Announcement of Good Bye 2016

•
• +556
•

By Errichto, 2 years ago, ,

Both a participant and a contest organizer sometimes wants to stress test their solution with the brute force. Sometimes random tests are quite weak and one needs many thousands (and sometimes millions) of them to become sure about the correctness. The thing is that running a program is quite slow itself, what may hurt if the computation part is fast. On my laptop running a C++ program with empty main() one thousand times takes 1.3s, what doesn't satisfy me. How to make it faster?

I recently prepared a problem with a binary grid (SRM 699, div1-hard TwoSquares) and I wanted to be very careful about the correctness. I wrote slow solutions in C++ and the intended one in Java. Only then I realized how slow usual stress testing is. If they all were in one language, I would quite easily get everything into one program with classes (structs) and I would just run it once, without any overheads. But since the languages were different, I had to rewrite one solution, what not only requires time, but also is a possible place for a mistake.

Does running a program on Windows take the similar amount of time? Is it possible to run a program on Ubuntu or Windows faster than in a milisecond? Given two programs in C++, how to automatically merge them into one program and test them (this feature would be awesome in Polygon I think, where stress testing is able to process only thousands of tests too)?

Regarding my last question (automatically merging two programs) some idea is to wrap everything except includes into a struct and creating one global instance of such a struct. It should be automatically zero-ed (all global variables should be 0, as the user intended).

code

The good thing is that the memory doesn't become huge if we process many tests (or does it?). But mnbvmar noticed that it won't work for static variables. Any way to make it work? Any other ideas?

•
• +58
•

By Errichto, 2 years ago, ,

Four participants will advance to the finals. Check the exact time.

EDIT: 15 minutes to the start.

•
• +110
•

By Errichto, 2 years ago, ,

Remember to register.

--- EDIT, the contest is over ---

# BearBall, 250 points

There is a special case when all points are in one line. Otherwise, for any pair of bears the number of throws is 1 or 2.

So, for each points you should count how many points are directly reachable from this one. You achieve it by sorting other points. The complexity should be .

Proof that 2 throws are enough
code for BearBall

# BearGridRect, 600 points

Hint: use flows, maybe mincost.

what graph?
code for BearGridRect

# BearCircleGame, 800 points

Dynamic programming. Iterate over the number of remaining players, from n to 1. In each moment, you need an array of size with probabilities — for each number of bears what is the probability that Limak is this far from the starting bear. Then, for each bear we need probability that he loses and thus we will know the next array (for remaining - 1 remaining bears).

a loses with probability .

Try to first write O(n3) approach — find cycle in a sequence of indices a + 1 - k, a + 1 - 2k, a + 1 - 3k... and then over indices in the cycle sum up where c is the size of cycle and d says which place this index has in the cycle.

To make it faster, notice that the answer for a and for a + k will be similar. It's enough to multiply (or divide, whatever) by the sum by two, and then add one value.

code for BearCircleGame

# WINNERS

1. liymsheep, who solved all three problems
2. ACRush
3. kriii

And congratulations to Petr for solving all problems and thus winning the parallel round.

•
• +66
•

By Errichto, 2 years ago, ,

# 680A - Bear and Five Cards

Iterate over all pairs and triples of numbers, and for each of them check if all two/three numbers are equal. If yes then consider the sum of remaining numbers as the answer (the final answer will be the minimum of considered sums). Below you can see two ways to implement the solution.

code1
code2

# 680B - Bear and Finding Criminals

Limak can't catch a criminal only if there are two cities at the same distance and only one of them contains a criminal. You should iterate over the distance and for each distance d check if a - d and a + d are both in range [1, n] and if only one of them has ti = 1.

code1
code2

# 679A - Bear and Prime 100

If a number is composite then it's either divisible by p2 for some prime p, or divisible by two distinct primes p and q. To check the first condition, it's enough to check all possible p2 (so, numbers 4, 9, 25, 49). If at least one gives "yes" then the hidden number if composite.

If there are two distinct prime divisors p and q then both of them are at most 50 — otherwise the hidden number would be bigger than 100 (because for p ≥ 2 and q > 50 we would get p·q > 100). So, it's enough to check primes up to 50 (there are 15 of them), and check if at least two of them are divisors.

code1
code2, Python

# 679B - Bear and Tower of Cubes

Let's find the maximum a that a3 ≤ m. Then, it's optimal to choose X that the first block will have side a or a - 1. Let's see why.

• If the first block has side a then we are left with m2 = m - first_block = m - a3.
• If the first block has side a - 1 then the initial X must be at most a3 - 1 (because otherwise we would take a block with side a), so we are left with m2 = a3 - 1 - first_block = a3 - 1 - (a - 1)3
• If the first blocks has side a - 2 then the initial X must be at most (a - 1)3 - 1, so we are left with m2 = (a - 1)3 - 1 - first_block = (a - 1)3 - 1 - (a - 2)3.

We want to first maximize the number of blocks we can get with new limit m2. Secondarily, we want to have the biggest initial X. You can analyze the described above cases and see that the first block with side (a - 2)3 must be a worse choice than (a - 1)3. It's because we start with smaller X and we are left with smaller m2. The situation for even smaller side of the first block would be even worse.

Now, you can notice that the answer will be small. From m of magnitude a3 after one block we get m2 of magnitude a2. So, from m we go to m2 / 3, which means that the answer is O(loglog(m)). The exact maximum answer turns out to be 18.

The intended solution is to use the recursion and brutally check both cases: taking a3 and taking (a - 1)3 where a is maximum that a3 ≤ m. It's so fast that you can even find a in O(m1 / 3), increasing a by one.

code1
code2
code3

# 679C - Bear and Square Grid

Let's first find CC's (connected components) in the given grid, using DFS's.

We will consider every possible placement of a k × k square. When the placement is fixed then the answer is equal to the sum of k2 the the sum of sizes of CC's touching borders of the square (touching from outside), but for those CC's we should only count their cells that are outside of the square — not to count something twice. We will move a square, and at the same time for each CC we will keep the number of its cells outside the square.

We will used a sliding-window technique. Let's fix row of the grid — the upper row of the square. Then, we will first place the square on the left, and then we will slowly move a square to the right. As we move a square, we should iterate over cells that stop or start to belong to the square. For each such empty cell we should add or subtract 1 from the size of its CC (ids and sizes of CC's were found at the beginning).

And for each placement we consider, we should iterate over outside borders of the square (4k cells — left, up, right and down side) and sum up sizes of CC's touching our square. Be careful to not count some CC twice — you can e.g. keep an array of booleans and mark visited CC's. After checking all 4k cells you should clear an array, but you can't do it in O(number_of_all_components) because it would be too slow. You can e.g. also add visited CC's to some vector, and later in the boolean array clear only CC's from the vector (and then clear vector).

The complexity is O(n2·k).

code1
code2
code3, Java

# 679D - Bear and Chase

Check my code below, because it has a lot of comments.

First, in O(n3) or faster find all distances between pairs of cities.

Iterate over all g1 — the first city in which you use the BCD. Then, for iterate over all d1 — the distance you get. Now, for all cities calculate the probability that Limak will be there in the second day (details in my code below). Also, in a vector interesting let's store all cities that are at distance d1 from city g1.

Then, iterate over all g2 — the second city in which you use the BCD. For cities from interesting, we want to iterate over them and for each distinct distance from g2 to choose the biggest probability (because we will make the best guess there is).

Magic: the described approach has four loops (one in the other) but it's O(n3).

Proof is very nice and I encourage you to try to get it yourself.

Proof here
code1

# 679E - Bear and Bad Powers of 42

The only special thing in numbers 1, 42, ... was that there are only few such numbers (in the possible to achieve range, so up to about 1014).

Let's first solve the problem without queries "in the interval change all numbers to x". Then, we can make a tree with operations (possible with lazy propagation):

• find minimum in the whole tree

In a tree for each index let's keep the distance to the next power of 42. After each "add on the interval" we should find the minimum and check if it's positive. If not then we should change value of the closest power of 42 for this index, and change the value in the tree. Then, we should again find the minimum in the tree, and so on. The amortized complexity is O((n + q) * log(n) * log42(values)). It can be proved that numbers won't exceed (n + q) * 1e9 * log.

Now let's think about the remaining operation of changing all interval to some value. We can set only one number (the last one) to the given value, and set other values to INF. We want to guarantee that if t[i] ≠ t[i + 1] then the i-th value is correctly represented in the tree. Otherwise, it can be INF instead (or sometimes it may be correctly represented, it doesn't bother me). When we have the old query of type "add something to interval [a, b]" then if index a - 1 or index b contains INF in the tree then we should first retrieve the true value there. You can see that each operation changes O(1) values from INF to something finite. So, the amortized complexity is still O((n + q) * log(n) * log42(values).

One thing regarding implementation. In my solution there is "set < int > interesting" containing indices with INF value. I think it's easier to implemement the solution with this set.

code1
code2

•
• +99
•

By Errichto, 2 years ago, ,

Hello Codeforces.

The CF Round #356 will happen on 8-th June (exact time). You will get five problems to solve in two hours. The round is rated.

I encourage you to read other problems if you don't like or can't solve something. The scoring distribution will be announced.

MikeMirzayanov and GlebsHP make the round possible. Also, thanks for Stonefeang, kostka, johnasselta, AlexFetisov and (more to be added?) for their amazing help. And I want to thank my girlfriend because there would be no Limak without her.

It's my first standard round. Still, you should get nice interesting problems. You will meet Limak, who is usually a little polar bear. Here he is, preparing one of problems.

I wish you great fun and no frustrating bugs.

EDIT — It's recommended for both divisions to read the Interactive Problems Guide before the round.

EDIT2, SCORING

div2: 500-1000-1750-2250-2750
div1: 750-1250-1500-2000-2500

EDIT3

The editorial with codes is ready.

WINNERS, congratulations!

and Division 2:

Thank you all for participation and see you next time. And regards from Limak, a bear.

•
• +687
•

By Errichto, 2 years ago, ,

I'm not able to find any link. I think that this problem was used in the last day of the camp (Petrozavodsk, Winter 2015). I didn't manage to solve it during the contest and I still don't see a solution.

Given n ≤ 106, find the standard deviation (or variance) of an, with allowed precision 10 - 6. A sequence a1, a2, ..., an is generated as follows:

a[1] = 1
for(int i = 2; i <= n; i++) {
int j = rand(1, i-1); // random integer from interval [1, i-1]
int k = rand(1, i-1);
a[i] = a[j] + a[k];
}


I'm not sure about constraints but I think it doesn't matter (I would appreciate any polynomial solution). Also, maybe the answer was required modulo some number, instead of a real number with some precision — I don't know, sorry. And yes, the expected value is n.

•
• +66
•

By Errichto, 2 years ago, ,

Hi everybody.

May Clash 2016 has just started. You have 24 hours to solve 6 problems, including an approximation one (tie breaker). The submission time doesn't matter so you can join whenever you want.

You get points for each test passed so do your best even if you can't solve the problem for the given constraints. Remember that not all tests are max-tests.

This time, problems are invented by niyaznigmatul so you can expect a very high quality of the problemset. I was a tester. Also, thanks to YakutovDmitriy and lightning for ideas for problems.

Top3 gets amazon gift cards, top5 gets t-shirts, top50 gets their handles showed in the first page of the leaderboard (I know, it's awesome).

I wish you great fun and no frustrating bugs.

WINNERS

So much red.

Top3 got nice scores in an approximation problem, congrats. Not only top5 solved all non-aproximation problems so I want to also mention fcdkbear, rajat1603 and eatmore.

Thank you for participating!

•
• +93
•

By Errichto, 2 years ago, ,

Hi everybody.

The VK Cup Round 3 is coming (exact time).

The duration will be longer than usual, likely 3 hours.

As usually in VK Cup, there will be three contests — div1, div2, official one. All of them are rated. Div1 and div2 versions are for individual participants, not for teams.

Setters are Stonefeang, Errichto and qwerty787788. I think that (some) problems are extremely interesting and I really wish I could participate. Thanks to GlebsHP and MikeMirzayanov, we wouldn't have a round without them. Also, thanks to AlexFetisov and winger for testing.

We will later inform about the final duration. Maybe we will inform about the number of problems and scoring.

I wish you great fun and no frustrating bugs. And Limak wishes you good luck!

UPD

• The contest will last 3 hours.
• ADJUSTED POINTS DROP — Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hour rounds.
• I updated testers above.
• Top50 in the "Div1 Edition" contest will get t-shirts. Have I already said "I wish I could participate"?

UPD 2

There are 9 problems. Div2 gets problems 1 - 6, and Div1+R3 gets 3 - 9. It means that there are 4 shared problems.
Division 2: 500 750 1000 1500 2250 3000
R3 & Div1: 500 1000 1750 2250 2250 3000 3000

UPD 3

Enjoy the editorial

UPD 4

The system testing is over. Congratulations to winners. Later I will try to put winners here in some nice format.

 VK Round 3 Div. 1 Div. 2 1. subscriber, tourist 1. Endagorion 1. Bus 2. eduardische, Alex_2oo8 2. eatmore 2. Herzu 3. AlexDmitriev, Kostroma 3. ikatanic 3. co_farmer 4. LHiC, overtroll 4. izrak 4. TDL9 5. KAN, vepifanov 5. rowdark 5. polingy