### Errichto's blog

By Errichto, 2 days 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

•
• +467
•

By Errichto, 7 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, 16 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, 16 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, 16 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, 17 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, 17 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, 17 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, 17 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, 17 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, 18 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, 18 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, 18 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, 20 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, 20 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, 23 months 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

Announcement of VK Cup 2016 - Round 3

•
• +327
•

By Errichto, 2 years ago, ,

Codes in nicer format will be uploaded later.
658A - Bear and Reverse Radewoosh and 639A - Bear and Displayed Friendscodes.
639B - Bear and Forgotten Tree 3 and 639C - Bear and Polynomialscodes.
639D - Bear and Contributioncodes.
639F - Bear and Chemistrycodes.

658A - Bear and Reverse Radewoosh — Iterate once from left to right to calculate one player's score and then iterate from right to left. It's generally good not to write something similar twice because you are more likely to make mistakes. Or maybe later you will find some bug and correct it only in one place. So, try to write calculating score in a function and run them twice. Maybe you will need to reverse the given arrays in some moment.

639A - Bear and Displayed Friends — You should remember all friends displayed currently (in set or list) and when you add someone new you must check whether there are at most k people displayed. If there are k + 1 then you can iterate over them (over k + 1 people in your set/list) and find the worst one. Then — remove him. The intended complexity is O(n + q*k).

639B - Bear and Forgotten Tree 3 — You may want to write some special if for n = 2. Let's assume n ≥ 3. If d = 1 or d > 2h then there is no answer (it isn't hard to see and prove). Otherwise, let's construct a tree as follows.

We need a path of length h starting from vertex 1 and we can just build it. If d > h then we should also add an other path from vertex 1, this one with length d - h. Now we have the required height and diameter but we still maybe have too few vertices used. But what we built is one path of length d where d ≥ 2. You can choose any vertex on this path other than ends of the path (let's call him v), and add new vertices by connecting them all directly with v. You can draw it to see that you won't increase height or diameter this way. In my code I sometimes had v = 1 but sometimes (when d = h) I needed some other vertex and v = 2 was fine.

639C - Bear and Polynomials, my favorite problem in this contest. Let's count only ways to decrease one coefficient to get the required conditions (you can later multiply coefficient by  - 1 and run your program again to also calculate ways to increase a coefficient).

One way of thinking is to treat the given polynomial as a number. You can find the binary representation — a sequence with 0's and 1's of length at most . Changing one coefficient affects up to consecutive bits there and we want to get a sequence with only 0's. We may succeed only if all 1's are close to each other and otherwise we can print 0 to the output. Let's think what happens when 1's are close to each other.

Let's say that we got a sequence with two 1's as follows: ...00101000.... Decreasing by 5 one coefficient (the one that was once in a place of the current first bit 1) will create a sequence of 0's only. It's not complicated to show that decreasing coefficients on the right won't do a job (because the first 1 will remain there) but you should also count some ways to change coefficients on the left. We can decrease by 10 a coefficient on the left from first 1, or decrease by 20 a coefficient even more on the left, and so on. Each time you should check whether changing the original coefficient won't exceed the given maximum allowed value k.

One other solution is to go from left to right and keep some integer value — what number should be added to the current coefficient to get sum equal to 0 on the processed prefix. Then, we should do the same from right to left. In both cases maybe in some moment we should break because it's impossible to go any further. In one case it happens when we should (equally) divide an odd number by 2, and in the other case it happens when our number becomes too big (more than 2·109) because we won't be able to make it small again anyway.

639D - Bear and Contribution — It isn't enough to sort the input array and use two pointers because it's not correct to assume that the optimal set of people will be an interval. Instead, let's run some solution five times, once for each remainder after dividing by 5 (remainders 0, 1, 2, 3, 4). For each remainder r we assume that we should move k people to some value x that (and at the end we want at least k people to have contribution x). Note that x must be close to some number from the input because otherwise we should decrease x by 5 and for sure we would get better solution. The solution is to iterate over possible values of x from lowest to highest (remember that we fixed remainder ). At the same time, we should keep people in 5 vectors/lists and do something similar to the two pointers technique. We should keep two pointers on each of 5 lists and always move the best among 5 options. The complexity should be O(n·5).

639E - Bear and Paradox — It's good to know what to do with problems about optimal order. Often you can use the following trick — take some order and look at two neighbouring elements. When is it good to swap? (When does swapping them increase the score?) You should write some simple formula (high school algebra) and get some inequality. In this problem it turns out that one should sort problems by a fraction and it doesn't depend on a constant c. There may be many problems with the same value of and we can order them however we want (and the question will be: if there is a paradox for at least one order). Let's call such a set of tied problems a block.

For each problem you can calculate its minimum and maximum possible number of granted points — one case is at the end of his block and the other case is to solve this problem as early as possible so at the beginning of his block. So, for fixed c for each problem we can find in linear time the best and worst possible scores (given points).

When do we get a paradox? Where we have two problems i and j that pi < pj (pi was worth less points) we solved problem i much earlier and later we got less points for problem pj. We can now use some segment tree or sort problems by pi and check whether there is a pair of problems with inequalities we are looking for — pi < pj and maxi > minj where maxi and minj we found in the previous paragraph.

We can do the binary search over the answer to get complexity or faster. Can you solve the problem in linear time?

639F - Bear and Chemistry — Task is about checking if after adding some edges to graph, some given subset of vertices will be in one biconnected component. Firstly, let's calculate biconnected components in the initial graph. For every vertex in each query we will replace it with index of its bicon-component (for vertices from subset and for edges endpoints). Now we have a forest. When we have a list of interesting vertices in a new graph (bicon-components of vertices from subset or edges) we can compress an entire forest, so it will containg at most 2 times more vertices than the list (from query) and will have simillar structure to forest. To do it, we sort vertices by left-right travelsal order and take LCA of every adjacent pair on the sorted list. If you have compressed forest, then you just have to add edges and calculate biconnected components normally, in linear time.

Tutorial of VK Cup 2016 - Round 1

•
• +104
•

By Errichto, 2 years ago, ,

Problems ABCG will be described better soon.

problem A — watch out for test like "1 1 1 2 2 2 2 3 3 3". It shows that it's not enough to sort number and check three neighbouring elements. You must remove repetitions. The easier solution is to write 3 for-loops, without any sorting. Do you see how?

problem B — you should generate all 6n possible starting strings and for each of them check whether you will get "a" at the end. Remember that you should check two first letters, not last ones (there were many questions about it).

653C - Bear and Up-Down — Let's call an index i bad if the given condition about ti and ti + 1 doesn't hold true. We are given a sequence that has at least one bad place and we should count ways to swap two elements to fix all bad places (and not create new bad places). The shortest (so, maybe easiest) solution doesn't use this fact but one can notice that for more than 4 bad places the answer is 0 because swapping ti and tj can affect only indices i - 1, i, j - 1, j.

With one iteration over the given sequence we can find and count all bad places. Let x denote index of the first bad place (or index of some other bad place, it's not important). We must swap tx or tx - 1 with something because otherwise x would still be bad. Thus, it's enough to consider O(n) swaps ~-- for tx and for tx - 1 iterate over index of the second element to swap (note that "the second element" doesn't have to be bad and samples show it). For each of O(n) swaps we can do the following (let i and j denote chosen two indices):

1. Count bad places among four indices: i - 1, i, j - 1, j. If it turns out that these all not all initial bad places then we don't have to consider this swap — because some bad place will still exist anyway.
2. Swap ti and tj.
3. Check if there is some bad place among four indices: i - 1, i, j - 1, j. If not then we found a correct way.
4. Swap ti and tj again, to get an initial sequence.

Be careful not to count the same pair of indices twice. In the solution above it's possible to count twice a pair of indices (x - 1, x) (where x was defined in the paragraph above). So, add some if or do it more brutally — create a set of pairs and store sorted pairs of indices there.

CHALLENGE — can you solve this problem if the initial sequence is already nice (if it doesn't have bad places)?

653D - Delivery Bears — invented and prepared by lewin, also the editorial.

Java code: 16825205
C++ code solving also the harder version: 16825257

Let's transform this into a flow problem. Here, we transform "weight" into "flow", and each "bear" becomes a "path".

Suppose we just want to find the answer for a single x. We can do this binary search on the flow for each path. To check if a particular flow of F is possible, reduce the capacity of each edge from ci to . Then, check if the max flow in this graph is at least x. The final answer is then x multiplied by the flow value that we found.

MUCH HARDER VERSION — you are also given an integer k (1 ≤ k ≤ 104) and your task is to find the answer for x paths, for x + 1 paths, ..., and for x + k - 1 paths. There should be k real values on the output.

The solution of the harder version.

653E - Bear and Forgotten Tree 2

C++ code: 16826422

You are given a big graph with some edges forbidden, and the required degree of vertex 1. We should check whether there exists a spanning tree. Let's first forget about the condition about the degree of vertex 1. The known fact: a spanning tree exists if and only if the graph is connected (spend some time on this fact if it's not obvious for you). So, let's check if the given graph is connected. We will do it with DFS.

We can't run standard DFS because there are maybe O(n2) edges (note that the input contains forbidden edges, and there may be many more allowed edges then). We should modify it by adding a set or list of unvisited vertices s. When we are at vertex a we can't check all edges adjacent to a and instead let's iterate over possible candidates for adjacent unvisited vertices (iterate over s). For each b in s we should check whether a and b are connected by a forbidden edge (you can store input edges in a set of pairs or in a similar structure). If they are connected by a forbidden edge then nothing happens (but for each input edge it can happen only twice, for each end of edge, thus O(m) in total), and otherwise we get a new vertex. The complexity is where is from using set of forbidden edges.

Now we will check for what degree of vertex 1 we can build a tree. We again consider a graph with n vertices and m forbidden edges. We will first find out what is the minimum possible degree of vertex 1 in some spanning tree. After removing vertex 1 we would get some connected components and in the initial graph they could be connected to each other only with edges to vertex 1. With the described DFS we can find c (1 ≤ c ≤ n - 1) — the number of created connected components. Vertex 1 must be adjacent to at least one vertex in each of c components. And it would be enough to get some tree because in each component there is some spanning tree — together with edges to vertex 1 they give us one big spanning tree with n vertices (we assume that the initial graph is connected).

And the maximum degree of vertex 1 is equal to the number of allowed edges adjacent to this vertex. It's because more and more edges from vertex 1 can only help us (think why). It will be still possible to add some edges in c components to get one big spanning tree.

So, what is the algorithm? Run the described DFS to check if the graph is connected (if not then print "NO"). Remove vertex 1 and count connected components (e.g. starting DFS's from former neighbours of vertex 1). Also, simply count d — the number of allowed edges adjacent to vertex 1. If the required degree k is between c and d inclusive then print "YES", and otherwise print "NO".

653F - Paper task — invented and prepared by k790alex, also the editorial.

Java code (modify-SA-solution): 16821422
C++ code (compressing-solution): 16826803

There are two solutions. The first and more common solution required understanding how do SA (suffix array) and LCP (longest common prefix) work. The second processed the input string first and then run SA+LCP like a blackbox, without modifying or caring about those algorithms.

Modify-SA-solution — The main idea is to modify the algorithm for computing the number of distinct substrings using SA + LCP.

Let query(L, R) denote the number of well formed prefixes of substring(L, R). For example, for substring(L, R) = "(())()(" we would have query(L, R) = 2 because we count (()) oraz (())().

How to be able to get query(L, R) fast? You can treat the opening bracket as  + 1 and the ending bracket as  - 1. Then you are interested in the number of intervals starting in L, ending not after R, with sum on the interval equal to zero. Additionally, the sum from L to any earlier right end can't be less than zero. Maybe you will need some preprocessing here, maybe binary search, maybe segment trees. It's an exercise for you.

We can iterate over suffix array values and for each suffix we add query(suffix, N) - query(suffix, suffix + LCP[suffix] - 1) to the answer. In other words we count the number of well formed substrings in the current suffix and subtract the ones we counted in the previous step.

The complexity is but you could get AC with very fast solution with extra .

Compressing-solution — I will slowly compress the input string, changing small well-formed substrings to some new characters (in my code they are represented by integer numbers, not by letters). Let's take a look at the example:

or equivalently:

Whenever I have a maximum (not possible to expand) substring with single letters only, without any brackets, then I add this substring to some global list of strings. At the end I will count distinct substrings in the found list of strings (using SA+LCP). In the example above I would first add a string "a" and later I would add "baa". Note that each letter represents some well formed substring, e.g. 'b' represents (()) here.

I must make sure that the same substrings will be compressed to the same letters. To do it, I always move from left to right, and I use trie with map (two know what to get from some two letters).

problem G — you can consider each prime number separately. Can you find the answer if there are only 1's and 2's in the input? It may be hard to try to iterate over possible placements of the median. Maybe it's better to think how many numbers we will change from 2^p to 2^{p+1}.