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

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

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

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

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

Hello Codeforces!

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

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

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

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

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

Code: 25627790

Code: 25627860

Code: 25627873.

Code: 25627885.

Code: 25627898.

Code: 25627911.

Code: 25627924.

Hello.

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

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

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

I wish you great fun and no frustrating bugs.

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

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

Specifically, the winners of VK Cup Round 1 are:

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

The winners of parallel rounds are:

Div. 1:

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

Div. 2:

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

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

Hi everybody.

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

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

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

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

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

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

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

Hello Codeforces!

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

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

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

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

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

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

EDIT: Updated info about prizes.

Hello Codeforces! Did you miss Limak?

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

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

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

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

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

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

EDIT2: Bump, the contest starts in 24 hours.

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

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

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

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

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

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

You can download my codes to all problems here.

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

750B - New Year and North Pole

750C - New Year and Rating

750D - New Year and Fireworks

750E - New Year and Old Subsequence

750F - New Year and Finding Roots

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

750G - New Year and Binary Tree Paths

750H - New Year and Snowy Grid

750A - New Year and Hurry

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

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

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

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

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

750B - New Year and North Pole

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

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

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

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

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

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

C++ code: 24067685
python code: 24067669

750C - New Year and Rating

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

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

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

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

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

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

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

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

750D - New Year and Fireworks

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

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

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

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

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

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

750E - New Year and Old Subsequence

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

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

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

TODO

750F - New Year and Finding Roots

750G - New Year and Binary Tree Paths

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

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

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

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

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

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

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

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

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

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

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

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

750H - New Year and Snowy Grid

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

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

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

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

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

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

My code: 50164800.

Hello everybody!

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

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

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

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

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

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

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

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

UPD2: In 750F - 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

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

Congratulations!

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

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

#include <bits/stdc++.h>
using namespace std;

Struct P1 {
	int s, t[100000];
	int main() {
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i) {
			scanf("%d", &t[i]);
			s += t[i];
		}
		printf("%d\n", s);
		return 0;
	}
} P1_global;

struct P2 {
	// something similar
} P2_global;

int main() {
	for(int rep = 0; rep < 1000; ++rep) {
		// generate the test and either print it to the file or put it to some stream
		auto p1 = P1_global;
		p1.main();
		auto p2 = P2_global;
		p2.main();
		// compare outputs
	}
}

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?

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

EDIT: 15 minutes to the start.

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 .

import java.util.Arrays;

public class BearBall {
	public int countThrows(int[] x, int[] y) {
		int n = x.length;
		int answer = 0;
		for(int i = 0; i < n; ++i) {
			// sort other points by angle
			Point[] p = new Point[n-1];
			int tmp = 0;
			for(int j = 0; j < n; ++j) if(i != j)
				p[tmp++] = new Point(x[j] - x[i], y[j] - y[i]);
			Arrays.sort(p);
			// check if all are collinear
			if(p[0].compareTo(p[n-2]) == 0) {
				answer = 0; // forget what was calculated so far
				for(int a = 0; a < n; ++a)
					for(int b = a + 1; b < n; ++b)
						answer += 2 * (b - a);
				return answer;
			}
			for(int j = 0; j < n - 1; ++j) {
				++answer; // the first point in this direction
				while(j + 1 < n - 1 && p[j].compareTo(p[j+1]) == 0) {
					answer += 2; // not the first point in this direction
					++j;
				}
			}
		}
		return answer;
	}
}

class Point implements Comparable<Point> {
	int x, y;
	Point(int _x, int _y) { x = _x; y = _y; }
	public int compareTo(Point other) {
		if(isRight() != other.isRight())
			return isRight() ? 1 : -1;
		return x * other.y - y * other.x;
	}
	void write() {
		System.out.println(x + " " + y);
	}
	boolean isRight() {
		return x > 0 || (x == 0 && y > 0);
	}
}

BearGridRect, 600 points

Hint: use flows, maybe mincost.

import java.util.*;

public class BearGridRect {
	int n, m;
	int row(int i) { return i; }
	int column(int i) { return n + i; }
	int query1(int i) { return 2 * n + i; }
	int query2(int i) { return 2 * n + m + i; }
	public int[] findPermutation(int tmp_n, int[] r1, int[] r2, int[] c1, int[] c2, int[] cnt) {
		n = tmp_n;
		m = r1.length;
		int s = 2 * n + 2 * m;
		int t = 2 * n + 2 * m + 1;
		int total = 2 * n + 2 * m + 2;
		MinCostMaxFlow f = new MinCostMaxFlow();
		f.init(total);
		
		boolean visited[][] = new boolean[n][n];
		int cnt_sum = 0;
		
		for(int i = 0; i < m; ++i) {
			cnt_sum += cnt[i];
			f.add(query1(i), query2(i), cnt[i], 0);
			for(int r = r1[i]; r <= r2[i]; ++r)
				for(int c = c1[i]; c <= c2[i]; ++c) {
					f.add(row(r), query1(i), 1, 0);
					f.add(query2(i), column(c), 1, 0);
					visited[r][c] = true;
				}
		}
		for(int r = 0; r < n; ++r)
			for(int c = 0; c < n; ++c)
				if(!visited[r][c])
					f.add(row(r), column(c), 1, 1);
		
		for(int r = 0; r < n; ++r)
			f.add(s, row(r), 1, 0);
		for(int c = 0; c < n; ++c)
			f.add(column(c), t, 1, 0);
		
		int[] ans = f.findFlow(s, t);
		int total_flow = ans[0];
		int total_cost = ans[1];
		if(total_flow != n || cnt_sum + total_cost != n) {
			int tmp[] = {-1};
			return tmp;
		}
		ans = new int[n];
		for(int r = 0; r < n; ++r) {
			for(int c = 0; c < n; ++c) {
				if(f.flow[row(r)][column(c)] > 0)
					ans[r] = c;
				for(int i = 0; i < m; ++i)
					if(f.flow[row(r)][query1(i)] > 0 && f.flow[query2(i)][column(c)] > 0) {
						ans[r] = c;
						f.flow[row(r)][query1(i)] = f.flow[query2(i)][column(c)] = 0;
					}
			}
		}
		return ans;
	}
}

class MinCostMaxFlow { // from http://web.mit.edu/~ecprice/acm/acm08/MinCostMaxFlow.java
	boolean found[];
	int N, cap[][], flow[][], cost[][], dad[], dist[], pi[];
	
	void init(int N) {
		this.N = N;
		cap = new int[N][N];
		cost = new int[N][N];
	}
	void add(int from, int to, int ca, int cos) {
		cap[from][to] = ca;
		cost[from][to] = cos;
	}
	
	static final int INF = Integer.MAX_VALUE / 2 - 1;
	
	boolean search(int source, int sink) {
		Arrays.fill(found, false);
		Arrays.fill(dist, INF);
		dist[source] = 0;

		while (source != N) {
			int best = N;
			found[source] = true;
			for (int k = 0; k < N; k++) {
				if (found[k]) continue;
				if (flow[k][source] != 0) {
					int val = dist[source] + pi[source] - pi[k] - cost[k][source];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (flow[source][k] < cap[source][k]) {
					int val = dist[source] + pi[source] - pi[k] + cost[source][k];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (dist[k] < dist[best]) best = k;
			}
			source = best;
		}
		for (int k = 0; k < N; k++)
			pi[k] = Math.min(pi[k] + dist[k], INF);
		return found[sink];
	}
	
	int[] findFlow(int source, int sink) {
		found = new boolean[N];
		flow = new int[N][N];
		dist = new int[N+1];
		dad = new int[N];
		pi = new int[N];
		
		int totflow = 0, totcost = 0;
		while (search(source, sink)) {
			int amt = INF;
			for (int x = sink; x != source; x = dad[x])
				amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
			cap[dad[x]][x] - flow[dad[x]][x]);
			for (int x = sink; x != source; x = dad[x]) {
				if (flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
					totcost -= amt * cost[x][dad[x]];
				} else {
					flow[dad[x]][x] += amt;
					totcost += amt * cost[dad[x]][x];
				}
			}
			totflow += amt;
		}
		return new int[]{ totflow, totcost };
	}
}

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(n³) 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.

public class BearCircleGame {
	int mod = 1000 * 1000 * 1000 + 7;
	int mul(int a, int b) {
		return (int) ((long) a * b % mod);
	}
	int my_pow(int a, int b) {
		int r = 1;
		while(b > 0) {
			if(b % 2 == 1) r = (int) ((long) r * a % mod);
			a = (int) ((long) a * a % mod);
			b /= 2;
		}
		return r;
	}
	int inv(int a) { return my_pow(a, mod - 2); }
	
	public int winProbability(int n, int k) {
		int dp[] = new int[n];
		dp[0] = 1; // probability that Limak starts
		for(int remaining = n; remaining >= 2; --remaining) {
			int old[] = dp;
			dp = new int[remaining - 1];
			boolean vis[] = new boolean[remaining];
			for(int starting = 0; starting < remaining; ++starting) if(!vis[starting]) {
				int p = 0;
				int x = starting;
				int div = 1;
				int cycle_size = 0;
				do {
					vis[x] = true;
					++cycle_size;
					div = mul(div, inv(2));
					p = (p + mul(old[x], div)) % mod;
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
				
				int power_two = 1;
				for(int i = 0; i < cycle_size; ++i)
					power_two = 2 * power_two % mod;
				if(power_two == 1) {
					System.out.println("assert inv(0)");
					return -1;
				}
				// multiply by 2^c/(2^c-1) (because it's geometric  series)
				int mul_by = mul(power_two, inv(power_two - 1));
				
				do {
					int dead = (x + k - 1) % remaining;
					if(dead != 0) {
						int nxt = (dead == remaining-1) ? 0 : dead;
						dp[nxt] = mul(p, mul_by);
					}
					p = (p - mul(old[x], inv(2)) + mod) % mod;
					p = 2 * p % mod;
					p = (p + mul(old[x], div)) % mod; // div == inv(2)^c
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
			}
		}
		return dp[0];
	}
}

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.

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.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t[5];
	int s = 0;
	for(int i = 0; i < 5; ++i) {
		scanf("%d", &t[i]);
		s += t[i];
	}
	int best = s;
	
	// discard 2 cards
	for(int a = 0; a < 5; ++a)
		for(int b = a + 1; b < 5; ++b)
			if(t[a] == t[b])
				best = min(best, s - 2 * t[a]);
	
	// or discard 3 cards
	for(int a = 0; a < 5; ++a)
		for(int b = a + 1; b < 5; ++b)
			for(int c = b + 1; c < 5; ++c)
				if(t[a] == t[b] && t[a] == t[c])
					best = min(best, s - 3 * t[a]);
	
	printf("%d\n", best);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t[5];
	for(int i = 0; i < 5; ++i)
		scanf("%d", &t[i]);
	sort(t, t + 5);
	int best_remove = 0;
	for(int i = 0; i < 5; ++i) {
		if(i + 1 < 5 && t[i] == t[i+1])
			best_remove = max(best_remove, 2 * t[i]);
		if(i + 2 < 5 && t[i] == t[i+2])
			best_remove = max(best_remove, 3 * t[i]);
	}
	printf("%dn", t[0]+t[1]+t[2]+t[3]+t[4]-best_remove);
	return 0;
}

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 t_i = 1.

#include<bits/stdc++.h>
using namespace std;
const int nax = 1005;
int t[nax];
int main() {
	int n, a;
	scanf("%d%d", &n, &a);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &t[i]);
	int answer = 0;
	for(int i = 1; i <= n; ++i) if(t[i]) {
		// can we catch criminal in city i?
		int distance = i - a; // distance from a
		int j = a - distance; // the other city at the same distance
		if(j < 1 || j > n || t[i] == t[j])
			++answer;
	}
	printf("%dn", answer);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int nax = 1005;
int t[nax];
bool impossible[nax];
int main() {
	int n, a;
	scanf("%d%d", &n, &a);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &t[i]);
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			if(abs(i - a) == abs(j - a) && t[i] != t[j]) {
				// i and j have the same distance to a
				// also, there is a criminal in exactly one of them
				impossible[i] = impossible[j] = true;
			}
	int answer = 0;
	for(int i = 1; i <= n; ++i)
		if(t[i] == 1 && !impossible[i])
			++answer;
	printf("%dn", answer);
	return 0;
}

679A - Bear and Prime 100

If a number is composite then it's either divisible by p² 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 p² (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.

#include<bits/stdc++.h>
using namespace std;

bool isPrime(int a) {
	for(int i = 2; i * i <= a; ++i)
		if(a % i == 0)
			return false;
	return true;
}

bool divisible(int a) {
	printf("%dn", a);
	fflush(stdout);
	char sl[10];
	scanf("%s", sl);
	return sl[0] == 'y' || sl[0] == 'Y';
}

int HIGH = 100;

int main() {
	int counter = 0; // we print "composite" if counter >= 2
	for(int a = 2; a <= HIGH/2 && counter < 2; ++a)
		if(isPrime(a))
			if(divisible(a)) {
				++counter;
				if(a * a <= HIGH && divisible(a * a))
					++counter;
			}
	puts(counter >= 2 ? "composite" : "prime");
	return 0;
}

from sys import stdout

PRIMES = [x for x in range(2,100) if 0 not in [x%i for i in range(2,x)]]

NORMAL = PRIMES[:15]
SQUARES = [x*x for x in PRIMES[:4]]

for ele in SQUARES:
    print(ele)
    stdout.flush()
    x = input()
    if x == "yes":
        print("composite")
        exit(0)

yes = 0
for ele in NORMAL:
    print(ele)
    stdout.flush()
    x = input()
    if x == "yes":
        yes += 1

print("prime" if yes < 2 else "composite")

679B - Bear and Tower of Cubes

Let's find the maximum a that a³ ≤ 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 m₂ = m - first_block = m - a³.
• If the first block has side a - 1 then the initial X must be at most a³ - 1 (because otherwise we would take a block with side a), so we are left with m₂ = a³ - 1 - first_block = a³ - 1 - (a - 1)³
• If the first blocks has side a - 2 then the initial X must be at most (a - 1)³ - 1, so we are left with m₂ = (a - 1)³ - 1 - first_block = (a - 1)³ - 1 - (a - 2)³.

We want to first maximize the number of blocks we can get with new limit m₂. 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)³ must be a worse choice than (a - 1)³. It's because we start with smaller X and we are left with smaller m₂. 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 a³ after one block we get m₂ of magnitude a². So, from m we go to m^2 / 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 a³ and taking (a - 1)³ where a is maximum that a³ ≤ m. It's so fast that you can even find a in O(m^1 / 3), increasing a by one.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

pair<ll,ll> best;

ll my_pow(ll x) { return x * x * x; }

void rec(ll m, ll steps, ll subtracted) {
	if(m == 0) {
		best = max(best, make_pair(steps, subtracted));
		return;
	}
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	rec(m - my_pow(x), steps+1, subtracted + my_pow(x));
	if(x - 1 >= 0)
		rec(my_pow(x)-1-my_pow(x-1), steps+1, subtracted + my_pow(x-1));
}

int main() {
	ll m;
	scanf("%lld", &m);
	rec(m, 0, 0);
	printf("%lld %lldn", best.first, best.second);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll my_pow(ll x) { return x * x * x; }

ll steps(ll m) { // works in O(m^(1/3))
	if(m <= 7) return m;
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	return 1 + steps(max(m - my_pow(x), my_pow(x)-1-my_pow(x-1)));
}

int main() {
	ll m;
	scanf("%lld", &m);
	ll subtracted = 0, steps_so_far = 0;
	while(m) {
		++steps_so_far;
		ll x = 1;
		while(my_pow(x+1) <= m) ++x;
		if(steps(m) == 1 + steps(m - my_pow(x))) {
			m -= my_pow(x);
			subtracted += my_pow(x);
		}
		else {
			m = my_pow(x) - 1 - my_pow(x-1);
			subtracted += my_pow(x-1);
		}
	}
	printf("%lld %lldn", steps_so_far, subtracted);
	return 0;
}

#include "bits/stdc++.h"

using namespace std;

#define ll long long

vector <ll> X;
map <ll, pair <int, ll> > M;

pair <int, ll> go(ll x)
{
  if(x <= 1)
    return {x,x};
  if(M.find(x) != M.end())
    return M[x];
  int i = upper_bound(X.begin(), X.end(), x) - X.begin() - 1;
  int p1, p2;
  long long q1, q2;
  tie(p1, q1) = go(x - X[i]);
  tie(p2, q2) = go(X[i] - 1);
  return M[x] =  max(make_pair(p1+1, q1+X[i]), {p2, q2});
}

int main()
{
  for(int i=0; i<=1e5+7; i++)
    X.push_back(1LL*i*i*i);
  ll x;
  cin >> x;
  int a;
  long long b;
  tie(a,b) = go(x);
  cout << a << " " << b << "n";
}

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 k² 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(n²·k).

#include<bits/stdc++.h>
using namespace std;
const int nax = 505;
int n;
char grid[nax][nax]; // input
int cc[nax][nax]; // id of CC in which this cell is
int cc_size[nax*nax]; // size of CC
int when_added[nax*nax];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char EMPTY = '.';

bool inside(int x, int y) {
	return 0 <= min(x, y) && max(x, y) < n;
}

void dfs(int x, int y, int which_cc) {
	cc[x][y] = which_cc;
	++cc_size[which_cc];
	for(int i = 0; i < 4; ++i) { // iterate of 4 adjacent cells
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if(inside(x2, y2) && grid[x2][y2] == EMPTY && cc[x2][y2] == 0)
			dfs(x2, y2, which_cc);
	}
}

void add(int x, int y, int & answer, int current_time) {
	if(inside(x, y) && grid[x][y] == EMPTY) {
		int id = cc[x][y];
		if(when_added[id] != current_time) {
			when_added[id] = current_time;
			answer += cc_size[id];
		}
	}
}

int main() {
	int k;
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; ++i)
		scanf("%s", grid[i]);
	
	// run DFS many times to find CC's (connected components)
	int how_many_cc = 0;
	for(int x = 0; x < n; ++x)
		for(int y = 0; y < n; ++y)
			if(grid[x][y] == EMPTY && cc[x][y] == 0)
				dfs(x, y, ++how_many_cc);
	
	int cur_time = 1;
	int best_answer = 0;
	
	for(int y_low = 0; y_low + k <= n; ++y_low) {
		// first we put a square with corner in (0, y_low)
		for(int x = 0; x < k; ++x)
			for(int y = y_low; y < y_low + k; ++y)
				--cc_size[cc[x][y]]; // subtract cells inside a square
		
		for(int x_low = 0; x_low  + k <= n; ++x_low) {
			int answer = k * k; // all cells inside a square
			// consider one row: below, above, left, right
			for(int x = x_low; x < x_low + k; ++x) {
				add(x, y_low - 1, answer, cur_time);
				add(x, y_low + k, answer, cur_time);
			}
			for(int y = y_low; y < y_low + k; ++y) {
				add(x_low - 1, y, answer, cur_time);
				add(x_low + k, y, answer, cur_time);
			}
			++cur_time;
			best_answer = max(best_answer, answer);
			
			if(x_low + k != n) {
				// move a square to increase x_low by 1
				for(int y = y_low; y < y_low + k; ++y) {
					++cc_size[cc[x_low][y]]; // remove cells with x = x_low
					--cc_size[cc[x_low+k][y]]; // insert cells with x = x_low+k
				}
			}
		}
		
		for(int x = n - k; x < n; ++x)
			for(int y = y_low; y < y_low + k; ++y)
				++cc_size[cc[x][y]]; // we don't need cells inside to be subtracted
	}
	printf("%dn", best_answer);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 500 + 5;
const int nax2 = nax * nax;

int n,k;

int ile_na_zew, akt_stan = 1;

char t[nax][nax];
int ojc[nax][nax];
int ilosc[nax2], lewo[nax2], prawo[nax2], gora[nax2], dol[nax2];
int suma[nax][nax], kol[nax], stan[nax2];
bool bylo[nax][nax];

vector<pair<pii, int> > wiersz[nax];

int ruchi[] = {-1, 0, 1, 0};
int ruchj[] = {0, -1, 0, 1};

void dfs(int i, int j, int wsk) {
  ilosc[wsk]++;
  ojc[i][j] = wsk;
  bylo[i][j] = true;
  lewo[wsk] =  min(lewo[wsk], j);
  prawo[wsk] = max(prawo[wsk], j);
  gora[wsk] =  min(gora[wsk], i);
  dol[wsk] =   max(dol[wsk], i);  
  
  REP(g,4) {
    int ni = i + ruchi[g];
    int nj = j + ruchj[g];
    
    if (t[ni][nj] == '.' && bylo[ni][nj] == false)
      dfs(ni,nj,wsk);
  }
}

void check(int o) {
  if (stan[o] != akt_stan)
    ile_na_zew += ilosc[o];
  stan[o] = akt_stan;  
}

int main() {	
  scanf("%d%d",&n,&k);
  FOR(i,1,n) scanf(" %s",t[i]+1);
  
  int wsk = 1;
  FOR(i,1,n) FOR(j,1,n) if (t[i][j] == '.' && !bylo[i][j]) {
    lewo[wsk] = prawo[wsk] = j;
    gora[wsk] = dol[wsk] = i;
    dfs(i,j,wsk);
    //printf("%dn",ilosc[wsk]);
    if (prawo[wsk] - lewo[wsk] + 1 <= k && dol[wsk] - gora[wsk] + 1 <= k) {
      //puts("DD");
      int x = max(1, dol[wsk] - k + 1);
      wiersz[x].pb(mp(mp(lewo[wsk], prawo[wsk]), ilosc[wsk]));
      wiersz[gora[wsk]+1].pb(mp(mp(lewo[wsk], prawo[wsk]), -ilosc[wsk]));
    }
    ++wsk;
  }
  
  FOR(i,1,n) FOR(j,1,n) suma[i][j] = suma[i-1][j] + suma[i][j-1] - suma[i-1][j-1] + (t[i][j] == '.');
  //FOR(i,1,n) FOR(j,1,n) printf("(%d,%d): %dn",i,j,suma[i][j]);
  
  int res = 0;
  FOR(i,1,n-k+1) {
    for (auto p: wiersz[i]) {
      int l = max(1, p.st.nd - k + 1);
      //printf("%d %d %dn",l,p.st.st,p.nd);
      kol[l] += p.nd;
      kol[p.st.st + 1] -= p.nd;
    }
    
    int suma_s = 0;
    FOR(j,1,n-k+1) {
      suma_s += kol[j];
      int ile_w_s = suma[i+k-1][j+k-1] - suma[i-1][j+k-1] - suma[i+k-1][j-1] + suma[i-1][j-1];
      ile_na_zew = 0;
      REP(g,k) {
        check(ojc[i-1][j+g]);
        check(ojc[i+k][j+g]);
        check(ojc[i+g][j-1]);
        check(ojc[i+g][j+k]);
      }
      
      int x = ile_na_zew + (k * k  - ile_w_s) + suma_s;
      //printf("(%d,%d) : %d %d %d %dn",i,j,ile_na_zew, ile_w_s, suma_s, x);
      
      res = max(res, x);
      ++akt_stan;
    }
  }
  printf("%dn",res);
	return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE_356 solver = new TaskE_356();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE_356 {
        int n;
        int k;
        boolean[][] f;
        List<Integer> componentCellCount;
        int[][] color;
        int x = 0;
        int y = 0;
        int totalEmpty = 0;
        int sumInComponents = 0;
        int[] amInComponents;
        int[] flag;
        int currentFlagColor = 0;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            k = in.nextInt();
            f = new boolean[n][n];
            color = new int[n][n];
            ArrayUtils.fill(color, -1);
            for (int i = 0; i < n; ++i) {
                char[] c = in.nextString().toCharArray();
                for (int j = 0; j < n; ++j) {
                    f[i][j] = (c[j] == '.');
                }
            }

            // Caclulate all CC
            int res = 0;
            componentCellCount = new ArrayList<Integer>();
            int currentComponentId = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (color[i][j] == -1) {
                        int count = dfs(i, j, currentComponentId++);
                        componentCellCount.add(count);
                        res = Math.max(res, count);
                    }
                }
            }

            flag = new int[currentComponentId];
            amInComponents = new int[currentComponentId];
            // Preprocess first square
            for (int i = 0; i < k; ++i) {
                for (int j = 0; j < k; ++j) {
                    addCell(i, j);
                }
            }

            res = Math.max(res, checkResult());

            for (int i = 0; i <= n - k; ++i) {
                int delta = i % 2 == 0 ? 1 : -1;
                for (int j = 0; j < n - k; ++j) {
                    moveSquare(0, x, y, x, y + delta);
                    y += delta;
                    res = Math.max(res, checkResult());
                }
                if (i != n - k) {
                    moveSquare(1, x, y, x + 1, y);
                    ++x;
                    res = Math.max(res, checkResult());
                }
            }
            out.println(res);
        }

        void moveSquare(int type, int cx, int cy, int nx, int ny) {
            if (type == 0) {
                if (ny < cy) {
                    for (int i = 0; i < k; ++i) {
                        removeCell(cx + i, cy + k - 1);
                        addCell(cx + i, ny);
                    }
                } else {
                    for (int i = 0; i < k; ++i) {
                        removeCell(cx + i, cy);
                        addCell(cx + i, ny + k - 1);
                    }
                }
            } else {
                for (int i = 0; i < k; ++i) {
                    removeCell(cx, cy + i);
                    addCell(nx + k - 1, cy + i);
                }
            }
        }

        void removeCell(int cx, int cy) {
            if (f[cx][cy]) {
                --totalEmpty;
                amInComponents[color[cx][cy]]--;
                if (amInComponents[color[cx][cy]] == 0) {
                    sumInComponents -= componentCellCount.get(color[cx][cy]);
                }
            }
        }

        void addCell(int cx, int cy) {
            if (f[cx][cy]) {
                ++totalEmpty;
                amInComponents[color[cx][cy]]++;
                if (amInComponents[color[cx][cy]] == 1) {
                    sumInComponents += componentCellCount.get(color[cx][cy]);
                }
            }
        }

        int dfs(int cx, int cy, int cId) {
            if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0;
            if (color[cx][cy] != -1) return 0;
            if (!f[cx][cy]) return 0;
            color[cx][cy] = cId;
            int am = 1;
            am += dfs(cx - 1, cy, cId);
            am += dfs(cx + 1, cy, cId);
            am += dfs(cx, cy - 1, cId);
            am += dfs(cx, cy + 1, cId);
            return am;
        }

        int checkResult() {
            ++currentFlagColor;
            int res = k * k - totalEmpty + sumInComponents;
            for (int i = 0; i < k; ++i) {
                res += checkCell(x - 1, y + i);
                res += checkCell(x + k, y + i);
                res += checkCell(x + i, y - 1);
                res += checkCell(x + i, y + k);
            }
            return res;
        }

        int checkCell(int cx, int cy) {
            if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0;
            if (!f[cx][cy]) return 0;
            if (amInComponents[color[cx][cy]] > 0) return 0;
            if (flag[color[cx][cy]] == currentFlagColor) return 0;
            flag[color[cx][cy]] = currentFlagColor;
            return componentCellCount.get(color[cx][cy]);
        }

    }

    static class ArrayUtils {
        public static void fill(int[][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                Arrays.fill(f[i], value);
            }
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}

679D - Bear and Chase

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

First, in O(n³) 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(n³).

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

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
typedef double T;
const int nax = 1005;
int dist[nax][nax];
vector<int> w[nax];
T p_later[nax]; // p[v] - probability for city v in the second day
T p_dist_max[nax];
bool vis[nax];

void max_self(T & a, T b) {
	a = max(a, b);
}

T consider_tomorrow(int n, int g1, int dist1) {
	T best_tomorrow = 0;
	// we need complexity O(n * x)
	// where x denotes the number of v that |dist1-dist[g1][v]| <= 1
	for(int i = 1; i <= n; ++i) {
		p_later[i] = 0;
		vis[i] = false;
	}
	vector<int> interesting;
	for(int v = 1; v <= n; ++v) if(dist[g1][v] == dist1)
		for(int b : w[v]) {
			// Limak started in v with prob. 1/n
			// he then moved to b with prob. 1/degree[v]
			p_later[b] += (T) 1 / n / w[v].size();
			if(!vis[b]) {
				vis[b] = true;
				interesting.push_back(b);
			}
		}
	
	// interesting.size() <= x, where x is defined above (needed for complexity)
	for(int g2 = 1; g2 <= n; ++g2) {
		T local_sum = 0; // over situations with fixed g1, dist1, g2
		
		for(int b : interesting)
			max_self(p_dist_max[dist[g2][b]], p_later[b]);
		for(int b : interesting) {
			local_sum += p_dist_max[dist[g2][b]];
			p_dist_max[dist[g2][b]] = 0; // so it won't be calculated twice
		}
		max_self(best_tomorrow, local_sum);
	}
	return best_tomorrow;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	FOR(i,1,n) FOR(j, 1, n) if(i != j)
		dist[i][j] = n + 1; // infinity
	FOR(i,1,m) {
		int a, b;
		scanf("%d%d", &a, &b);
		w[a].push_back(b);
		w[b].push_back(a);
		dist[a][b] = dist[b][a] = 1;
	}
	// Floyd-Warshall
	FOR(b,1,n)FOR(a,1,n)FOR(c,1,n)
		dist[a][c] = min(dist[a][c], dist[a][b] + dist[b][c]);
	
	// g1 is the first guess
	T answer = 0;
	FOR(g1, 1, n) {
		T sum_over_dist1 = 0;
		FOR(dist1, 0, n) {
			int cnt_cities = 0;
			FOR(i, 1, n) if(dist[g1][i] == dist1)
				++cnt_cities;
			if(cnt_cities == 0) continue; // there are no cities within distance dist1
			
			// 1) consider guessing immediately
			T immediately = (T) 1 / n; // how much it counts towards the answer
			// 2) consider waiting for tomorrow
			T second_day = consider_tomorrow(n, g1, dist1);
			sum_over_dist1 += max(immediately, second_day);
		}
		max_self(answer, sum_over_dist1);
	}
	printf("%.12lfn", (double) answer);
	return 0;
}

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 10¹⁴).

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

• add on the interval
• 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) * log₄₂(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) * log₄₂(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.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
const int pot = 256 * 1024;
const ll INF = 3e18L;
ll cur_power[nax]; // the least power of 42 larger than the current value
// true_value + remaining = cur_power,  where remaining=tr[pot+i]

struct Node {
	ll local;
	ll lazy;
	ll smallest() { return local + lazy; } // smallest value in this subtree
} tr[2*pot];

void propagate(int i) {
	assert(i < pot);
	tr[2*i].lazy += tr[i].lazy;
	tr[2*i+1].lazy += tr[i].lazy;
	tr[i].local += tr[i].lazy;
	tr[i].lazy = 0;
}
void act(int i) {
	assert(i < pot);
	assert(tr[i].lazy == 0);
	tr[i].local = min(tr[2*i].smallest(), tr[2*i+1].smallest());
}

void change(int i, int low, int high, int q_low, int q_high, ll val) {
	if(q_low <= low && high <= q_high) {
		tr[i].lazy += val;
		return;
	}
	propagate(i);
	int mid1 = (low + high) / 2;
	if(q_low <= mid1)
		change(2*i, low, mid1, q_low, q_high, val);
	if(q_high >= mid1+1)
		change(2*i+1, mid1+1, high, q_low, q_high, val);
	act(i);
}
void change(int q_low, int q_high, ll val) {
	change(1, 0, pot - 1, q_low, q_high, val);
}

int where_smallest(int i = 1) {
	if(i >= pot) return i - pot;
	propagate(i);
	int ret;
	if(tr[2*i].smallest() < tr[2*i+1].smallest())
		ret = where_smallest(2*i);
	else
		ret = where_smallest(2*i+1);
	act(i);
	return ret;
}

ll move_power(int i, ll rem) {
	assert(rem <= 0);
	while(rem < 0) {
		ll cur_value = cur_power[i] - rem;
		cur_power[i] *= 42;
		rem = cur_power[i] - cur_value;
	}
	return rem;
}

set<int> interesting; // the set of indices i that t[i] != t[i+1] (and maybe few others)
// all other indices have value INF in the tree

ll get_value(int i) {
	assert(interesting.count(i));
	vector<int> w;
	for(int x = (pot + i) / 2; x >= 1; x /= 2)
		w.push_back(x);
	reverse(w.begin(), w.end());
	for(int x : w) propagate(x); // top-down
	return tr[pot+i].smallest();
}

const int SET_TYPE = 10042;
const int INC_TYPE = 10043;
void set_or_inc(int i, ll val, const int type) {
	vector<int> w;
	for(int x = (pot + i) / 2; x >= 1; x /= 2)
		w.push_back(x);
	reverse(w.begin(), w.end());
	for(int x : w) propagate(x); // top-down
	if(type == SET_TYPE) {
		tr[pot+i].lazy = 0;
		tr[pot+i].local = val;
	}
	else if(type == INC_TYPE) {
		tr[pot+i].local += val;
	}
	else assert(false);
	reverse(w.begin(), w.end());
	for(int x : w) act(x); // bottom-up
}

void re_insert(int i) {
	int j = *interesting.lower_bound(i);
	if(i == j) return;
	cur_power[i] = cur_power[j];
	set_or_inc(i, get_value(j), SET_TYPE);
	interesting.insert(i);
}

void init_value(int i, int val) {
	cur_power[i] = 1;
	ll how_much_remains = 1 - val; // how much remains to cur_power[i]
	ll rem = move_power(i, how_much_remains);
	set_or_inc(i, rem, SET_TYPE);
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i = 0; i < 2 * pot; ++i)
		tr[i].local = INF;
	for(int i = 1; i <= n; ++i) {
		interesting.insert(i); // we don't mind that maybe t[i] = t[i+1]
		int val;
		scanf("%d", &val);
		init_value(i, val);
	}
	// queries
	while(q--) {
		int type;
		scanf("%d", &type);
		if(type == 1) { // print value
			int i;
			scanf("%d", &i);
			i = *interesting.lower_bound(i);
			printf("%lldn", cur_power[i] - get_value(i));
		}
		else if(type == 2) { // set interval to x
			int low, high, val;
			scanf("%d%d%d", &low, &high, &val);
			// t[low] = t[low+1] = ... = t[high-1] = INF
			// t[high] = val
			if(low - 1 >= 1)
				re_insert(low - 1);
			interesting.insert(high);
			init_value(high, val);
			while(true) {
				auto it = interesting.lower_bound(low);
				assert(it != interesting.end());
				int i = *it;
				assert(i <= high);
				if(i == high) break; // we only want [low, high-1]
				interesting.erase(it);
				set_or_inc(i, INF, SET_TYPE);
			}
		}
		else { // increase by x
			assert(type == 3);
			int low, high, val;
			scanf("%d%d%d", &low, &high, &val);
			if(low - 1 >= 1)
				re_insert(low - 1);
			re_insert(high);
			bool ok = false;
			while(!ok) {
				ok = true;
				change(low, high, -val);
				while(true) {
					int i = where_smallest();
					ll rem = tr[pot+i].smallest();
					assert(1 <= i && i <= n);
					if(rem > 0) break;
					if(rem == 0) {
						ok = false;
						break;
					}
					ll new_rem = move_power(i, rem);
					set_or_inc(i, new_rem, SET_TYPE);
				}
			}
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, q;

vector <long long> poty;

int n1;

long long inf=(long long)1000000000*1000000000;

long long narz[1000007];
int czybom[1000007];
long long bom[1000007];

long long maxd[1000007];
long long mind[1000007];
long long zos[1000007];

int typ, p1, p2, p3;

inline int potenga(int v)
{
    for (int i=1; 1; i<<=1)
    {
        if (i>=v)
        {
            return i;
        }
    }
}

inline long long wie(long long v)
{
    return poty[lower_bound(poty.begin(), poty.end(), v)-poty.begin()];
}

inline long long brak(long long v)
{
    return wie(v)-v;
}

inline void pusz(int v)
{
    if (v>=n1)
    {
        czybom[v]=1;
        bom[v]+=narz[v];
        narz[v]=0;
        maxd[v]=bom[v];
        mind[v]=bom[v];
        zos[v]=brak(bom[v]);
        return;
    }
    int cel1, cel2;
    cel1=(v<<1);
    cel2=(cel1^1);
    if (czybom[v])
    {
        czybom[cel1]=1;
        bom[cel1]=bom[v];
        narz[cel1]=0;

        czybom[cel2]=1;
        bom[cel2]=bom[v];
        narz[cel2]=0;

        czybom[v]=0;
        bom[v]=0;
    }
    narz[cel1]+=narz[v];
    narz[cel2]+=narz[v];
    narz[v]=0;

    mind[v]=inf;
    maxd[v]=-inf;
    zos[v]=inf;

    for (int h=0; h<2; h++)
    {

        if (czybom[cel1])
        {
            bom[cel1]+=narz[cel1];
            narz[cel1]=0;
            maxd[v]=max(maxd[v], bom[cel1]);
            mind[v]=min(mind[v], bom[cel1]);
            zos[v]=min(zos[v], brak(bom[cel1]));
        }
        else
        {
            maxd[v]=max(maxd[v], maxd[cel1]+narz[cel1]);
            mind[v]=min(mind[v], mind[cel1]+narz[cel1]);
            zos[v]=min(zos[v], zos[cel1]-narz[cel1]);
        }

        swap(cel1, cel2);
    }
}

void dod(int v, int a, int b, int graa, int grab, long long w)
{
    if (a>=graa && b<=grab)
    {
        narz[v]+=w;
        return;
    }
    if (a>grab || b<graa)
    {
        return;
    }
    pusz(v);
    dod((v<<1), a, (a+b)>>1, graa, grab, w);
    dod((v<<1)^1, (a+b+2)>>1, b, graa, grab, w);
    pusz(v);
}

void zmi(int v, int a, int b, int graa, int grab, long long w)
{
    if (a>=graa && b<=grab)
    {
        narz[v]=0;
        czybom[v]=1;
        bom[v]=w;
        return;
    }
    if (a>grab || b<graa)
    {
        return;
    }
    pusz(v);
    zmi((v<<1), a, (a+b)>>1, graa, grab, w);
    zmi((v<<1)^1, (a+b+2)>>1, b, graa, grab, w);
    pusz(v);
}

void popr(int v)
{
    pusz(v);
    if (zos[v]>=0)
    {
        return;
    }
    if (mind[v]==maxd[v])
    {
        czybom[v]=1;
        bom[v]=mind[v];
        narz[v]=0;
        pusz(v);
        return;
    }
    popr((v<<1));
    popr((v<<1)^1);
    pusz(v);
}

long long wyn;

void czyt(int v, int a, int b, int cel)
{
    if (a>cel || b<cel)
    return;
    pusz(v);
    if (a==b)
    {
        wyn=bom[v];
        return;
    }
    czyt((v<<1), a, (a+b)>>1, cel);
    czyt((v<<1)^1, (a+b+2)>>1, b, cel);
}

int main()
{
    scanf("%d%d", &n, &q);
    n1=potenga(n+2);
    poty.push_back(1);
    for (int i=1; i<=11; i++)
    poty.push_back(poty.back()*42);
    zmi(1, 1, n1, 1, n1, 0);
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &p1);
        zmi(1, 1, n1, i, i, p1);
    }
    while(q--)
    {
        scanf("%d", &typ);
        if (typ==1)
        {
            scanf("%d", &p1);
            czyt(1, 1, n1, p1);
            printf("%lldn", wyn);
        }
        if (typ==2)
        {
            scanf("%d%d%d", &p1, &p2, &p3);
            zmi(1, 1, n1, p1, p2, p3);
        }
        if (typ==3)
        {
            scanf("%d%d%d", &p1, &p2, &p3);
            dod(1, 1, n1, p1, p2, p3);
            while(1)
            {
                popr(1);
                if (zos[1]==0)
                {
                    dod(1, 1, n1, p1, p2, p3);
                }
                else
                {
                    break;
                }
            }
        }
    }
    return 0;
}

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 Radewoosh, 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!

1. Petr
2. ainta
3. halyavin
4. jcvb
5. brandnewnode

and Division 2:

1. Y_UME
2. kaq
3. BehtarinFake
4. Zoli9
5. Jeannette

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

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 ≤ 10⁶, find the standard deviation (or variance) of a_n, with allowed precision 10^- 6. A sequence a₁, a₂, ..., a_n 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.

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.

1. HellKitsune
2. FatalEagle
3. zeliboba
4. Xellos
5. Lewin

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!

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 Radewoosh, 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.

Codes in nicer format will be uploaded later.
658A - Bear and Reverse Radewoosh and 639A - Bear and Displayed Friends — codes.
639B - Bear and Forgotten Tree 3 and 639C - Bear and Polynomials — codes.
639D - Bear and Contribution — codes.
639E - Bear and Paradox — codes.
639F - Bear and Chemistry — codes.

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·10⁹) 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 p_i < p_j (p_i was worth less points) we solved problem i much earlier and later we got less points for problem p_j. We can now use some segment tree or sort problems by p_i and check whether there is a pair of problems with inequalities we are looking for — p_i < p_j and max_i > min_j where max_i and min_j 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.

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 6ⁿ 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 t_i and t_i + 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 t_i and t_j 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 t_x or t_x - 1 with something because otherwise x would still be bad. Thus, it's enough to consider O(n) swaps ~-- for t_x and for t_x - 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 t_i and t_j.
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 t_i and t_j 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.

TODO — add codes.

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 c_i 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 ≤ 10⁴) 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.

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(n²) 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}.

Hi everybody.

The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.

I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: Lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Radewoosh. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.

Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.

I wish you great fun and no frustrating bugs. Enjoy the contest.

Scoring: 500-1000-1500-2000-2500-3500-3500.

WINNERS

1. EvenImage, the only one to solve all 7 problems!
2. JoeyWheeler
3. jcvb
4. andrew.volchek
5. ikatanic

In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).

Editorial is being created here.

If you don't know what the dynamic scoring is, you can read about it here. In my opinion it's a useful alternative. With smoother steps (250 instead of 500) it doesn't work so bad. Or does it? The main advantage is that organizers don't have to correctly estimate the difficulty. What are drawbacks? And should it be changed and improved in some way?

Hi. I want to invite you to HourRank 6. The contest will take place tomorrow (exact time) on the HackerRank platform. The duration is exactly one hour. I think that both beginners and experienced participants will find problems interesting for them.

There are problems from me and from forthright48. I want to thank Radewoosh for helping me with preparing problems, and for testing. I also thank malcolm, wanbo and Shafaet for testing and the technical help.

Limak needs you! I wish you great fun and no frustrating bugs. Looking forward to seeing you!

Besides fun, top 10 will get HR t-shirts. Good luck.

WINNERS

1. Endagorion
2. LayCurse
3. riadwaw
4. I_love_Tanya_Romanova
5. tabasz

It happened to me twice to skip a CF round because of the registration. Once I was too late, and once I even implemented A and tried to submit — but it turned out I haven't registered. It also happened to some of my friends.

For standard CF rounds the registration ends 5 minutes before the contest. The reason is that participants must be divided into rooms, to be able to hack. But hacking isn't so important, right? It's some extra possibility and many would enjoy a round even without hacks.

Let's allow participating without having a room. All people registered at least 5 minutes before should be assigned to rooms as usually. And after that, one should be able to register "out of room" — to participate without hacking and being hacked. A round should be rated for everybody. So, one could register after reading problems, and maybe even after implementing something.

Note that hacks are only a privilege. It's good to be hacked instead of getting WA on systests, and it's good to be able to hack others. So, it will be optimal to register before a round, if possible.

Does anybody see any drawbacks? If not, then make this change please. @CF_TEAM

Hi again.

Tomorrow (exact time) the Semifinals of IndiaHacks-Algorithms will start — link. You can participate only if you got any points in at least one of qualifiers. You will get 24 hours and 10 problems, including an approximation one to break ties. The submitting time doesn't matter unless you have a tie in an approximation problem (very unlikely).

In my opinion problems are unusually interesting. They were prepared by kostya_by, k790alex, and by me. Thanks for johnasselta and belowthebelt for helping me with testing and checking everything.

Top20 Indians advance to onsite finals. Top20 non-Indians advance to finals but will participate remotely, still fighting for prizes. Finals will happen somewhen in March.

I wish you great fun and no frustrating bugs. Looking forward to seeing you! Below, you can see prizes for top contestants in the final round.

WINNERS OF THE SEMIFINALS

1. tourist
2. eatmore
3. Al.Cash
4. mugurelionut
5. Romka

And congratulations for all advancing to the final round. The unofficial list of advancers is in the comments below.