1082F - Быстрый набор

Hi. I will explain my approach to solve this hard and counter-intuitive problem.

The problem

You've got some telephone numbers. Each number is dialed a given amount of times. You would need to do an amount of key presses to dial all numbers, that is well defined. However there is an amount of special buttons that can be used to type several digits at once. The buttons can only be used at the start of a number (before manually typing anything). Buttons presses does not count as digit press. Buttons can only be used once per number. You need to decide how to place k buttons to minimize total digit presses.

First insight

We need to build a trie structure of the numbers, this will allow us to exploit numbers that have something in common

(Example of trie of test case 1)

Need of DP

We should note some kind of DP should be used using sub-trees. The sub-problem could be defined like

"Solving sub-tree rooted at i using j buttons on strings belonging to that sub-tree.

But there is a technical problem defining DP like that. Although it is logically valid to think "solving" as "assigning buttons" to strings on that sub-tree, we need to store some number to represent that way of "assigning buttons" on DP_{ij}. The natural value would be "total key presses" to solve the sub-tree i using j buttons. But think about the characters of strings belonging to sub-tree but that are outside it. Should we consider it on sub-problem value? Yes or No?

I have though about that fact some time and realized that we can't solve the problem no matter the answer is Yes or No.

If the answer is Yes and we consider the outside characters of strings then DP of a smaller sub-trees is depending of DP of bigger sub-trees which is a contradiction. (Think if we use a button over the root of a sub-tree, then the sub-tree DP value changes)

If the answer is No, then and we only consider key presses used on that sub-tree then there is another problem. Imagine we are solving a sub-tree i with j buttons and we assume we have solved all children of sub-tree rooted at i root for all j' ≤ j. If we use a button ending on i we can't compute the total key presses of sub-tree rooted at i because it depends on the amount of strings belonging to sub-trees rooted at i children that are currently not being helped by any button, that do not depend on the sub-trees rooted at children of i DP values. It is another variable that should be added as another DP variable. But I have not analysed if this way the problem could be solved, maybe is too hard.

Thus the conclusion is that one way or another we need to add another variable to characterize our DP sub problem, otherwise the sub-problems can't be connected properly.

We use the DP that answer YES to the question made above. We need to solve the fact stated about the dependency of smaller sub-trees with bigger sub-trees by adding a variable.

DP would be defined like this

DP_i, j, k: Amount of key presses to dial all strings belonging to sub-tree rooted at i using j buttons on them. (And k??)

This of course depends of buttons used upside i. But there is a simplification. It depends in particular only on the lowest button used upside i, not every one.

So that is the variable we need to make DP well defined, the lowest button used upside i. That is the only information about upper nodes that our sub-tree uses.

DP_i, j, k: Amount of key presses to dial all strings belonging to sub-tree rooted at i using j buttons on them, considering the lowest button used up-side i ends at node k

And now when we solve highest sub-trees using lower sub-trees, they don't depend on highest sub-trees, because when we solve a higher sub-tree using a lower sub-tree we know k value that would correspond to the children DP solution we are using.

48045680

Hi all! I want to write 'cause I am totally happy about my last ranking promotion; to expert!

It have been now 3 years of hard work, and, let me say, It is worth! Who can say learning is boring?

I still remember the old days, in IOI2015, That times I was weak and still very shy. I was a mosquito, and IOI the bazooka.

Moreover, one fact I would like to share: I am currently not aiming to be a computer scientist, I am currently studying to be a electronics engineer, so this is not my principal field. However computer science is widely used here and I find, to learn it very complementary, it helps me with my field, although it is not strictly central, It is something not very well taught in my courses but that is it useful.

I hope you all the best wishes! Ask me problems if you need help :) I love trying to explain hard things.

IOI 2015 — Sorting

Statement

If we resume, then it says: "We've got an array S of length N (with distinct values) and two arrays Jx , Jy of length M (all arrays filled with values from 0 to N-1). Then the game starts and it consist of M turns, each turn i goes this way:

• A: We swap S[Jx[i]] with S[Jy[i]] (Jx[i] can be equal to Jy[i])
• B: Then we're allowed to do any swap (we can swap a value with itself). I will call this custom moves

The objective of the game is to make the array S sorted with the lower amount of turns. We're guaranteed that there is a solution with an amount of turns lower or equal than M.

Limits:

• N ≤ 200000
• M ≤ 600000
• M = 3N, so M > N

First Procedure

We'll first to solve the problem without trying to get the lower amount of turns. This solution (that is pretty) hard, will then make us solve the harder sub-task with a simple binary search with no modifications of the algorithm.

This solution points to make the array to be sorted when M turns have passed. Not after, not before.

Note that the sorted array must be [0, 1, 2, ...N - 1], or, in other words . We need all S[i] to be equal to its index.

We know that we make the array sorted when M turns passed. This must happen. So, we can predict how items will move until the M turns have passed. We can answer for each item i, where its value will be when all M moves have passed. Also we can answer "where the item i in the final sequence is in the actual sequence" if we don't make more additional moves of course. We know that the item i in the final sequence must be equal to i! And we know where this item in the final sequence is in the current sequence. So we'll only need to swap (in the first turn), the sequence with value i to the place that will go to the index i in the final sequence.

We'll need to repeat this process in each of the M turns. And in each turn we'll update two arrays

1. F = "where the item i in the final sequence is in the actual sequence
2. E = "where is the item with value i in the actual sequence"

This way we will in each turn swap E[i] with F[i], this means, "the place where i value is" to "the place that will be in the final array in i". Of course in the case E[i]! = F[i], otherwise we increase i and try to swap the next one. The idea is that in each turn we'll have "up to i-1" values already in its right position, and in case all i values are in its right position, then we only need to wait until M moves happened (and until then we don't swap anything (swap 0,0))

The final approach: Binary Search

We will need to consider trying to solve the problem "If there only were W ≤ M turns". We the algorithm of above with can answer to solve the answer "Can we solve the problem on W turns?". So with a binary search we will test to get the lower W that makes it possible to solve the problem. That will be the answer with a total algorithm complexity of O(log(M) * (M + N)).

Conclusion

This is an extremely hard task, Although no special algorithm is needed, you need some observations and to not get lost while thinking things because there is a good amount of deep thinking needed. Good Luck.

Code: Here Code v2: Here

623C - Электрические заряды

Hi all! I finally managed to code the solution of this tricky problem, I needed to read the editorial (very hard to follow) and make lot of hard work to get the trick of how to do it so now I want to share my conclusion of how it can be solved properly.

Problem Statement

It says you have a list of points with X and Y coordinates. However you need to define whether you will draw each one using its X coordinate or its Y. (and the other will be zero). Formally speaking you can draw each one on the (X,0) or in the (0,Y). The objective is to get the minimum diameter of the set of points, defined as the longest distance between any of them

Worst Solution

We need to note the worst solution would be to check both coordinates for each point (two possibility for each one. This would delay around 2^N * (time to get longest distance in each chance). As N is 100000 is impossible doing something like that.

First key observation

Imagine then an optimal solution where we have points drawn on X axis. Think about the points that its X coordinate is between at least the X coordinate of two points drawn on X axis. Why would we take the risk of drawing these points on its Y coordinate when if we draw it on X coordinate then the diameter would not be affected (because of course the two points drawn on X axis surrounding this point (sorted by X coordinate) have a bigger distance) . So our conclusion if that in an optimal solution the points drawn on X coordinate must be consecutive if we sort points by X (the same applies to Y, if we sort points by Y then the points drawn on Y axis are also consecutive in this kind of sorting). We can express the solution as Y POINTS — X POINTS — Y POINTS (sorted by X coordinate). or X POINTS — Y POINTS — X POINTS (sorted by Y coordinate). both are totally compatible, you can solve the problem once with any of them and you will get the same result.

An O(N*N) Approach

So we need to get the best start point and the best end point for this consecutive points. (sorted by X). We could make an O(N*N) algorithm if we try every possibility of the endpoints, but there still is an issue, because imagine we've got two endpoints, x1 and x2, to calculate exact diameter we need a trick because it is impossible by default to get the maximum and the minimum Y coordinate of the other points in O(1) (We would need to do another iteration on the points not used). The trick, as editorial says, is pretty easy, before we start solving the problem we need to get all the maximum and minimum Y values for each prefix and suffix of the points (sorted by X). You can get it on O(N). So then for example if we have as endpoints point 3 and point 6, (N=10) then the the maximum Y value would be max( MAXIMUM Y VALUE 0 to 2, MAXIMUM Y VALUE 7 TO 9) and the minimum Y value would be min( MINIMUM Y VALUE 0 to 2, MINIMUM Y VALUE 7 TO 9).

So this solution needs an O(N) precomputation (that gets on time) plus an O(N*N) algorithm to check every pair of endpoints (and getting the MAXY and MINY of each chance is instantly thanks to p recalculation). With the two X endpoints and the two Y endpoints (MAXY and MINY) we can easy and fast calculate the diameter for each chance.

However as N=100000 then O(N*N) is not enough. Every problem with N>10000 suggest a logarithmic approach solution (of course with a 1-3 seconds time limit). So there are two things I know that work on a logarithmic basic; segment tree and binary search. In this case we need to implement a binary search approach to increase performance to be enough to solve problem

First Binary search

Now we'll change the angle of what we were thinking. Instead of thinking about trying pairs of points, we'll develop an algorithm that answers: it is possible to make the points fit in M diameter? And here is where the binary property applies. Because if it is possible to make points fit in a diameter of a M value (example=1000), then it is possible to fit them in any higher diameter than 1000. But if it not then it is not possible to make them fit on any diameter lower than 1000. So we need to implement a binary search that discovers the value of M were we start to be able to fit the points (The lower value of M that can fit the points). As the problem ask for the square of the minimum diameter we won't make the binary search of the diameter but of the square of the diameter (In the contrary case we'll be obligated to do lots of sqrt() calculations that we know are too slow for this kind of contests and to deal with float numbers). so until now M is the square of the diameter and this does not change the behavior of the binary search. For the lower bound of M we will use the -1 value because zero can be a solution (in case all points are in the same point drawn and 0^2=0) and the higher bound will be max(10^8*2,10^8*10^8), i don't know who is bigger and it is not important because as the binary search is really fast we can just use LLONG_MAX from <climits.h> or <bits/stdc++.h> and won't change practically the run-time.

How to calculate binary property status

So now we need to do the hardest part. How we'll calculate whether is it possible or not the calculate if we can fit the points in a squared diameter of M? (And to do this in better than O(N*N), otherwise the total complexity would be O(N*N*log(N), worse than the original O(N*N))

To make things easier we we'll first check two border cases. We'll try to draw all points on X axis and to draw all of them on Y axis. In the first case the diameter would be the difference between first and last point (Remember, we decided to sort points according to X coordinate) and in the second the difference between MAXY and MINY (To get them we can use PREFIX UP TO N-1 or SUFFIX UP to 0, Remember we have precomputed them in a initial O(N) ). if the diameter value of any of those cases is lower than the M value we are trying to see is better then we answer yes, otherwise we need to check cases where some points lie on X axis and some others on Y axis to check whether it is possible. (of course as M is the square of diameter then to compare M and the diameter calculated we need to square diameter calculated rather than making the sqrt(M), DIA*DIA<=M) So now we need to check the other cases. it can be done on O(N) using the famous two pointer technique or in a modest (O(N*LOG(N)) using another binary search that will also fit the time limit, and because it is easier I will develop that method. Remember that all points that lie on X axis (of course sorted by X) are together. So we'll need to check every starting point of the chain going from the point 0 to the point N-1 and then using a binary search calculate the ending point of the chain. But because this method will not get all ending points of the chain checked we'll need to also check every ending point of the chain and then we'll need to binary search to get its starting point to the left side.

So we are checking a starting/ending point and now we need to get the other left/right endpoint to make sure the answer of diameter squared will not be bigger than the M value we are checking. If the point X coordinate distance is bigger than M then is easy to say we can not draw the point on X axis while maintaining diameter lower than M. So this point and all points farther away need to be drawn on Y axis. Also if the distance of this point to the (0,0) is bigger than the distance of the starting/ending point to (0,0) we'll decide to draw this point on Y axis (and so all father points than this one), because otherwise we risk about making the square distance between MAXY and the point or the distance between MINY and the point be bigger than M, and there is no way to make sure if it will or not, so any point that it X coordinate is far away than M from starting/ending point and its distance to (0,0) is bigger than the distance to (0,0) of starting point (shown in editorial as abs(X[point])>abs(X[s/e]) and any point farther than that won't be part of chain so it will be drawn on Y axis. In the contrary case if the point is nearer than M from the starting/ending point and abs(X[point])<=abs(X[s/e]) and any point between this point and starting/ending point will be drawn on X axis because we can to not take the risk of drawing it on Y axis. So using the binary search we have just calculated the starting/finishing point from a finishing/starting point of a chain. All points inside this chain will be drawn on X axis while all others on Y axis. We have deducted that to calculate the diameter of this configuration we only need the endpoints (that its distance squared is lower than M as we avoided to assign two points farther than that in algorithm) and the MINY and MAXY. to calculate both MINY and MAXY of the points drawn on Y axis we'll use the PREFIXES and SUFFIXES max/min Y calculated. As I previously said,

if we have as endpoints point 3 and point 6, (N=10) then the the maximum Y value would be max( MAXIMUM Y VALUE 0 to 2, MAXIMUM Y VALUE 7 TO 9) and the minimum Y value would be min( MINIMUM Y VALUE 0 to 2, MINIMUM Y VALUE 7 TO 9).

So with endpoints and MAX/MINY we need to see if any squared distance is bigger than M. If for example MAXY-MINY squared is bigger than M then of course this chain possibility can not fit on M. Also if distance squared of starting/ending point (s/e,0) to (0,MAXY) or (0,MINY) is bigger than M then the chain is also invalid. The other two diagonals (that would be the endpoint we've just binary searched) does not matter because as abs(X[e2])<=abs(X[s/e]) then it size is equal or less than the other two diagonals we've just tested. So if nothing of those conditions invalidate the M value then we've just found a valid chain that fits on M! Congrats! So we return in the function that checks if a squared value of diameter (M) is valid true. If in there is no solution in any chain (of the ones we checked on O(N(LOG(N)) that fits on M then the function should answer that it is not possible to find a combination of points that fits on squared diameter of M.

Total complexity

So that's all we've the method to get the whether we can or not fit the points on squared diameter of M in O(n(log(n)) and as we'll use it on a binary search between all posible values of squared diameter distances, then the total complexity will be (O(log(MAXDIS)*N*log(N))) plus a precomputation of O(N) to get the prefixes and suffixes.

pretty hard I think haha the editorial was way too short. Ask any question and try to code it, you can also check my submission :) 15849301

As everybody should know, last friday the Wunder Fund round has taken place here. I had unbelievable bad luck because that day I needed to travel 400 km to another city in Argentina to some holidays so I was forced to do the round... on a mobile?? I managed to solve that way only the easiest problem 1 using android c++ application while I was in the bus, luckily the first task was a typical procedural problem were the solution was pretty easy. At first I though it was very similar to the popular 2048 game, but in this case only 1D and not only 4 numbers. However being using my mobile phone I was confused about some details and then I realised... it was not the sum but the value of the combining numbers plus 1, so I switched from doing an intelligent binary transformation solution to a mere live simulation of the procedure with a vector. I managed that way to get accepted and switched to second problem that was not so easier, but easy to figure out the solution because the solution ramification has a nice property, that is every path make you to complete a valid sequence that follow the rules, so you can easily first find any good chance for first number, then for second (of course it can not be same as first), third and until N always choosing the first available number that makes the table valid. Of course I couldn't realize that when using the mobile so I only submitted it by the time contest finished. I also give a try to third problem, and because of my lack of experience in computational geometry I used the techniques I learnt on the problem of google code jam round 1A 2015 logging, where the solution was to sort the points by their angle relative to other point. In this case it was somewait similar. To form an empty triangle you could sort angles of points relative to some point (I my case I decided the center to be point 1), then find to consecutive points in this sorted list that are nearer than 180 degrees (I consider a change the combination of last number of the list and first number of it like a circle list), and then to avoid points to be inside the triangles of that points, if any of those two points has more points with the same angle but smaller distance, replace by the one more nearer. I got sick getting tons of wrong answers and I think one time limit, because of the CRAZY epsilon used to compare if long doubles were equal, * * plus * * in the end I realized that I needed to change atan2() function (used to get easily the angle relative to one point) to atan2l() and by the way get more precision. Then I get even more crazy. If I added too many zeroes to the EPSILON then case 20 failed, but If I kept to little then case 51 failed. I don't know way but there was a point between them in which I get accepted. The lemma? Doubles are definitely horrible, now I understand IOI syllabus. I will try to code the version that does not use angle calculations, because in a real contest you can not be dealing with such precision issues, that cost you lots of wrong answers submissions, which here, in codeforces, are unacceptable. Good luck guys, I will see if I get time to compete in the next round, maybe I will do it in my car with the mobile 4G because I am traveling again at that time....... bad luck again :( hehe will be funny though