Hello everybody,

So 4 months ago I wrote a blog about an online game I created. The game was basically you trying to type words moving in linear trajectories on the screen with different speeds for one minute. Your score was, and still is, the number of characters in all words you managed to type correctly while still on the screen. A lot of time has passed, during which I have learned some more thing, and now I would like to introduce you to the new version of it.

The website address is the same — http://crazytyper.cf. The first thing you will be asked to do is to pick a nickname which you will be able to change at any moment by clicking on the "Edit nickname" label which will appear in the upper left corner.

The game now has two modes — standard and survival. You will notice that I added leaderboards showing the top 5 results for the last 24 hours for each mode. To play some mode, simply click on the respective buttons under the scoretables.

Standard mode is pretty much what the previous version was but with much improved interface — you try to type words for a minute and you get a score equal to the total number of characters in the words typed correctly. After that minute passes, your score will automatically be inserted into the database with all scores and will eventually be shown on the top 5 leaderboard, if good enough.

Survival mode is the new feature which I believe is much more entertaining. You start with 10 seconds and again try to type the words you see. For each word you type correctly, you get a 1-second increment but you can never have more than 10 seconds. The score is again the number of characters in the words you type correctly. After your timer reaches zero, your score will automatically be inserted into the database and shown on the top 5 leaderboard, if good enough.

I would love to hear some feedback from you, also maybe share your scores here. My best ones are around ~390 for standard and ~2600 for survival.

Hello everybody,

Recently I decided to learn a bit of html/css/javascript and by googling every single step, I managed to create some game which is based on typing tests. Since typing speed is often a concerning topic among coders, I thought that maybe some of you could find it entertaining. So I invite you to try it at http://crazytyper.cf/.

The home page describes what it's all about and I think it's pretty self-explanatory:

You will see ten words moving on the screen, each following its own linear trajectory. Your goal is to type words that are currently on the screen, hitting space or enter between different words. As soon as a word hits the border of the screen or you type a word correctly, it disappears from the screen and is replaced by another word at a randomly chosen position. Once you type a word correctly, the number of letters in that word is added to your score. The moment you hit a keyboard key, a 60-second timer will start counting down.

In case somebody is interested, I uploaded it to GitHub — https://github.com/Peshooo/Crazy-Typer. As I mentioned, I am an absolute novice when it comes to programming not related to competitions so I would appreciate your feedback and suggestions.

Hello everybody,

Recently, while exploring vjudge, I came across this problem and I have no idea how to solve it.

Basically, we are given N points (N ≤ 1000), no three points lie on the same line, and we are to find the sum of areas of the convex hulls for each subset of at least 3 points. There are multiple test cases and the sum of the N values over all test cases is up to 5000.

Can anybody share some ideas about this problem, please?

Hello everyone,

So I recently prepared a lecture for a Bulgarian camp on the topic since I find it quite wide and interesting. I have never seen an article discussing different approaches for the problem so today I am going to share my knowledge. Don't forget to give me your feedback, please!

Let's start with first defining the problem we are going to solve. We are given a set of N d-dimensional points. Q queries follow, each containing a d-dimensional point. We should answer each query with the distance (we will use Euclidean distance) to the point from the set which is closest to the queried one. This will be our main focus but we are still going to consider inserting/deleting points from the set when possible. It's important to say that for d > 1 we will consider only average-case complexity and we will assume that the points are distributed uniformly. Unfortunately, even the average-case complexity is exponential in the number of dimensions.

One-Dimensional NNS

Without doubt, the problem is really simple when d = 1. In the picture below, the dark blue point is the queried one and all other points belong to the set.

It is easy to see that for any point, the one which is closest to it is either the closest to the left or the closest to the right. This leads to a pretty simple solution: First we sort the initial set of points and for each query we use binary search to find its position in the sorted array which automatically gives us its predecessor and successor points.

Now what about insertion/deletion of points?

Well, we can pretty much use the same idea. We need to keep the points sorted and quickly find the position of each queried point. At this moment, it should be obvious that any binary search tree will do the job and std::set is a good example.

Locality-Sensitive Hashing for Two-Dimensional NNS

When we usually use hashing, we try to avoid collisions no matter what, right? Well, not here. We would like to find a function which maps relatively close points to the same or close numbers and not-so-close points to different/not-so-close numbers. You can try to come up with some good functions on your own. They don't need to be perfect, the one I am going to present is not guaranteed to work but as you will see, after repeating it a few times we can have some pretty decent chances of getting it right or at least very close. DO NOT continue reading if you are planning to spend some time thinking.

So, let's draw a few random lines (excuse me for being so bad at faking randomness):

For each line, consider the two half-planes it creates. Let's write a zero next to each point from one of the half-planes and a one next to each point from the other. Something like this:

Now this binary code will be the hash for each point. When we are given a query point, we are going to find its hash according to the lines and only check the points having the same hash. Of course, we will need to get too lucky in order to answer many queries correctly with just one set of lines. So let's just generate as many sets as we can afford and check all points which have the same hash according to at least one set of lines. Let's say that we generate K sets with L lines each. Don't forget that we are talking about uniformly distributed points/lines and since there are 2^L possible hashes for a set of L lines, the expected number of points in a bucket is . So the complexity will be per query.

Inserting and deleting points is pretty much trivial since this algorithm is dynamic in its essence — the lines are generated before any points are read and then we hash them one by one and insert them in the proper buckets.

Although it is an elegant approach, it doesn't guarantee to give us a correct answer so let's move on to this structure called k-d tree.

K-Dimensional Tree for Small Values of d

So this structure can solve the problem for small number of dimensions (say up to 5) in O(logN) per query on average. We will see why it works only for small number of dimensions and that it is not exactly O(logN) but something more special after a few moments. I am going to explain it for d = 2 since d being 3 or 4 or 5 really makes no difference.

Let's start with the root of the tree which will be responsible for all N points. Let's sort the points by their X coordinate. We will draw a line which we will call a splitting line somewhere between the points in the middle in order to split them evenly. The X coordinate this line passes through we will call a splitting value for the current node (the root in the beginning):

Now all points from the first to the middle position go to the left subtree and the others — to the right subtree. For the subtrees we will repeat the same process but this time we will sort the points by their Y and the splitting line will go through some Y:

We will keep building the tree, alternating the axes we are splitting by until we reach a subarray with only one point which results in the so called leaf nodes. That is, each leaf node contains a point and each non-leaf node contains the splitting value and the axis it is splitted by:

I will first explain how the NNS works and then discuss the complexity. It is actually a pretty simple recursion, you won't believe how simple! We start at the root with our answer (closest distance) set to infinity. If we reach a leaf node at any moment, we will just compare the current answer and the distance between the queried point and the point stored the current leaf. Now, I am assuming that we are in a non-leaf node. On each step, we check whether the queried point falls into the left or right subtree (assuming it was there). We don't need to be exact, if it lays on the splitting line, it doesn't matter if we consider this left or right subtree.

We will first recursively traverse the subtree our point falls into. "But we need to traverse the other one afterwards", you may say. And so will we but only if we need to. And by "we need to" I mean "there is a chance of encountering a closer point in the other subtree". Let Ans be the closest distance encountered so far, after traversing one of the subtrees and D be the distance from the queried point to the splitting line. It's easy to see that all possible candidates for better answer must be in the circle with center the queried point and radius Ans. So we will traverse the other subtree if and only if Ans>D, that is there are some points in the other subtree which are in the circle with center the queried point and radius Ans. And this is it — as simple as it is. Notice that the distance between the queried point and the splitting line is just the absolute difference between the splitting value and the corresponding coordinate of the queried point.

Let's see why this is O(logN) (not exactly O(logN), as I said, but we will get back to that soon). I don't think this qualifies as a formal proof but just to give you an idea. Take a look at the last picture and you will see how every leaf (point) is bounded by some rectangle. So we get some N rectangles in total. We can assume that our plane is bounded by some very big square. For our uniform distribution, we can expect each of those bounding rectangles to have similar sizes or to be more precise similar sides. That is, we can expect our big square (the plane) to be divided into by small squares or something really close to such configuration.

Consider some query. What the recursion will first do is find one of these small squares our queried point falls into and set the distance between the queried point and the point in that leaf as the current answer (O(logN) so far). Say that it is Ans. Of course, traversing only this small square is not enough, and we will need to consider some more (those within radius Ans). However, by gives us a tight bound on Ans — . Which means that we will only need to consider the squares surrounding this current cell (which happen to be 8), if the distribution is perfectly uniform. So the average complexity turns out to be around O(8 * logN).

"But we don't consider constant factors when talking about complexity", may come to your mind. This is true. As you remember I said that the complexity is not really O(logN) and is exponential in the number of dimensions. Do you see where this is going? This 8, the number of surrounding squares for a unit square, is actually 3^d - 1. And here you go, the average-case complexity for a k-d tree query is actually O(3^d * N).

Inserting a point is actually pretty straighforward — we find the leaf which would contain this point if it was in the set (but actually contains another one). Then we just find a splitting line between the two points — the one in the current leaf and the one being inserted and treat this as an internal (non-leaf) node.

Deleting a point will be just finding the leaf that contains it and detaching it from the tree.

Vantage-Point Tree

This is a data structure which is a representative of another class of trees — ball trees. It is really similar to the k-d tree in the way it works and has similar complexity but it uses circles instead of lines to form the left and right subtree.

I won't be posting pictures but only explain the idea quickly since it has only minor differences with the k-d tree. The root again contains information about all N points. On each step we randomly choose the so-called vantage-point for the node among all points this node is responsible for. Then we sort all points by their distance to the vantage-point. We choose a radius (the so-called threshold), which is the distance between the vantage-point and the middle point after sorting. Then we build the left subtree over the first half (those inside the circle) and the right subtree over the second half. It's not a problem if some of the points from the right subtree lie on the circle. Then we recursively build the left and right subtree.

When we query some point, we again start at the root with our answer set to infinity. Every time we visit a node, we compare the answer and the distance between the queried point and the vantage-point for the current node. Then we check if it falls inside the circle or not. Depending on that, we first traverse the left or the right subtree, respectively.

After that, we will visit the other subtree only if there is a possibility of finding a better answer. Say that the threshold for the current node is T, the current answer is Ans and the distance between the queried point and the vantage-point is D. If we first visited the left subtree, then we will go to the right one if and only if D + Ans > T. If we first visited the right subtree, then we will go to the left one if and only if D - Ans < T.

For reference, consider this problem: http://www.spoj.com/problems/FAILURE/
My k-d tree solution: https://ideone.com/yDBOyc
My VP tree solution: https://ideone.com/o1wTNS
It is also worth mentioning that the linked problem is a special case of the nearest neighbor search — it only asks about points from the set which has a pretty neat O(NlogN) divide and conquer solution but I am too tired to explain it right now.

Hello everyone!

So two days ago, a friend of mine told me that one of my problems on SPOJ has been used as a problem for Bubble Cup. And by coincidence I have just had this conversation:

.

We can't be sure if it really is coincidence or attempt of gaining points in Bubble Cup in a nasty way but something made me think that the latter could with high probability be the case.

As you see, I didn't agree to give him my code but what if I did? Would it be cheating? I should mention that I didn't agree in anyway to get my problem used in Bubble cup, nor was I informed by someone from their team. I also made sure that the "Available for use in 3rd party contests" isn't checked on my problem panel in SPOJ:

I don't know if they have the rights of using my problem but surely I still have rights on my own problem. And as far as I know, it isn't a problem to discuss a problem from SPOJ, given that this is the only place I have agreed for my problem to be present.

PS: I will also appreciate if someone tells me if they have the right to use my problem in their contest? I don't know much about these things but it looks nasty to me. As Xellos pointed out, SPOJ is mentioned as a problem source (something I didn't see) so you can ignore this PS :)

Hello everyone,

So few hours back, there were two cheating teams in our room. One of the teams was called Runners and the other was Runners VKCup. You see, nothing suspicious on first glance. So these teams used the same codes to pass A's pretests but me and my friend Radoslav hacked them both — 1, 2 :D

In the end, one of these teams managed to accept A for 75 points. I would normally ask for making their round unrated but they actually lost rating so this sounds like a better punishment :D

Hello everyone!

This time I won't be asking you for help on problems, it's not related to programming at all. But these days I really often come across some strange topics by this user dnjfurnck. All topics look the same way — the content of the blog contains some link and those posts get a huge amount of upvotes in no time. Once he even copy-pasted this blog by RetiredAmrMahmoud. I posted a comment with the link to the original topic, asking why he was doing that and guess what — my comment got something like -20 in 3-4 minutes.

Is there any way Codeforces can prevent such things happen? I think it should be stopped :)

Hello everybody,

Recently I decided to look for some problems involving queries on trees and the last I found was this — http://acm.timus.ru/problem.aspx?space=1&num=1752 (note that this is not the problem I am asking about). In short, there is an unweighted tree with N<=20000 nodes and Q<=50000 queries are given. Each query contains a vertex V and distance D. You are to find some vertex that is on distance exactly D from V or report that there is no such vertex.

The problem above has a fairly simple solution if you have solved some problems about diameters and LCA. However, when I first read the problem, I misunderstood it and I thought it was asking for how many vertices are there such that the distance from them to V is exactly D. After spending an hour of thinking, I looked at the discussions for some hints and I saw that this was not the problem.

Anyway, I think the problem which I thought I should solve is quite interesting and I wonder if someone has a solution to it. If so, please share your ideas. Also, I would love it if you can give me some more problems about queries on trees, here is one I really liked — http://www.spoj.com/problems/DRTREE/ and also one prepared by myself — http://www.spoj.com/problems/MAXCHILDSUM/.

Thanks in advance! :)

Hello everybody,

When I opened gmail this morning, I saw the usual "You have new message" notification — http://store.picbg.net/pubpic/F3/D8/21675f680b25f3d8.png. However, when I followed the link, I saw there was no such message — http://store.picbg.net/pubpic/4D/EA/a9846246fd744dea.png.

How is this possible? I tried sending a random message to a friend of mine in order to see if I can somehow delete it in the first few minutes but nah, I couldn't.

PS: I also noticed that I haven't received an email for this comment — http://codeforces.net/blog/entry/46407?#comment-308043. Is it some sort of a bug, I remember this has happened before?

Hello everyone,

Today espr1t gave us the following game theory problem. Elly and Kriss are playing a game on a table with size NxM (1<=N,M<=10^9). The player to take a move chooses a cell from the table (R,C) and removes row R and column C and this way she splits the board in 4 parts of sizes (R-1)x(C-1), (R-1)x(M-C), (N-R)x(C-1), (N-R)x(M-C). The one who can't make a move loses. We are to find out who the winner will be. The idea was to use SG numbers in order to find some pattern which has complexity O(N^2*M^2) and it turned out that the only boards for which the first player loses had sizes 2x2, 4x4, 4x6, 8x12 and 10x10. However, we (also espr1t himself) can't prove that this works for every board, we have only checked that for N and M up to 2000.

Please, help us :D

Hello everybody,

Today I was solving a problem which reminded me that I still don't know an efficient algorithm for finding the area of the union of large number of rectangles (all rectangles are with sides parallel to the axes). I was looking for a tutorial and the best I found was an article from topcoder which only mentions the existence of such algorithm and presents an O(N^2logN) sweep line + BST algorithm. Can someone please tell me how to solve this faster — O(NlogN) or something like that. I thought about sweep line with segment tree in which I need to update an interval with 1 or -1 and get the number of zeroes over the whole interval but I couldn't come up with a way to do it.

Thanks in advance! :)

Hello everybody,

So two-three weeks ago I started learning C#. I decided to code some problems in C# after doing that in C++ in order to practice it and of course learn some things I don't know to do in that language.

Today I came across this problem — http://codeforces.net/problemset/problem/220/B and I coded Mo's algorithm in C++. It easily got accepted with time about 2 seconds (the time limit is 4 seconds) — http://codeforces.net/contest/220/submission/15191708. Then I moved to C# and after more than an hour spent in looking for 'how to write a comparator for Array.Sort for custom class in C#', I finally submitted a code in C# — http://codeforces.net/contest/220/submission/15192611. As it can be seen, it gave TLE on the fifth test.

Then I read that for large arrays, Array.Sort uses quick sort, so I added a random shuffle before the actual sorting — http://codeforces.net/contest/220/submission/15192841, still TLE #5. I started looking for a faster input method and I read that BufferedStream may help — http://codeforces.net/contest/220/submission/15193006 — unfortunately, it didn't. At the end, I tried to store the whole output in a StringBuilder and then output it but I got TLE once again — http://codeforces.net/contest/220/submission/15193128.

Can anyone please suggest a way to speed the program up? I am quite new to C#, I tried using google but I found no more than what I described in the post.

Thanks in advance! :)

Hello everybody!

This morning I realized that I was about to miss the contest since I completely forgot about it so just a quick reminder. It can be done from 11th to 14th this month :)

PS: According to usaco.org, this year there is going to be a new Platinum division :)

Hello everybody,

I have seen the name "Systems of Distinct Representatives" a few times in a short period of time so I decided to learn it. I have read about Hall's theorem and some of its applications but the thing is that I don't know some efficient way to find that system of distinct representatives. So the problem goes like this: We are given N sets S1,...,Sn of integers. We are to choose an integer from each set which we call a representative of that set. We want all sets to have different representatives. The best algorithm I know is to build a bipartite graph with sides the sets and the numbers and then the maximum matching will give us an answer. So that's why I learned the Hopcroft-Karp matching algorithm and assuming that the graph is built in O(E) time now I can solve the problem in O(E*sqrt(V)) which is worst case O(N^2*sqrt(N)).

However, I was told that it is possible to solve the problem in O(N^2). I will be really thankful if some of you can explain some more algorithms that can solve the problem faster and give me some problems if possible :)

Thanks in advance! :)

Hello everybody,

Last year I read that dynamic trees exist, that is trees in which we create only the nodes we need since there can be a lot (say we have indices 1,...,10^9). I thought it's cool and wanted to know more about it. I googled a few times "Dynamic BIT", "Dynamic trees" or something like that but I found nothing...

Recently I participated in BOI 2015 and there was a problem that required a segment tree for 60 points and dynamic segment tree or AVL Tree which I can't code for full score so I wasn't able to get more than 60 on it. Now, I tried googling "Dynamic Segment Tree" but found nothing...

Can somebody please explain how dynamic segment trees work and give me an implementation, I would appreciate your help!

Thanks in advance! :)

UPD: Thanks everybody for the help, I understood it! So basically, we initially have the root only which stores the whole interval ([1;10^9] for example). Then the update/query goes exactly like in the normal segment tree but if we don't have a child of some node but we need it, we just create it and go on. I implemented Horrible Queries from SPOJ (I know that a normal segment tree is enough, but I wanted to test it). Here is my accepted code, it might be helpful for somebody who has problems with this structure — http://ideone.com/hdI5aX.

Hello everybody,

A while ago I decided to learn about Hungarian algorithm. After watching some videos and reading some articles I think I got the main idea:

1) Find the minimum number in each row and subtract it from all elements in the row.

2) Find the minimum number in each column and subtract it from all elements in the column.

3) Cover all zeroes with minimum number of vertical and/or horizontal lines.

4) If the number of the lines is N, then we have found our assignment. Otherwise, find the minimum uncovered number, subtract it from all uncovered numbers and then go back to step 3.

Well, the thing is that I never found a good implementation. I can implement step 1 and 2. For step 3, I think that we can check whether the minimum number of lines is equal to N using bipartite matching. But if the minimum number is less than N, I don't know how I can find those covering lines. Please, help me with implementing it.

Thanks in advance!

UPD: I cannot fully understand Xellos' solution but a friend of mine(radoslav11) wrote this code and got AC with it. The bad thing is that neither me nor him can prove the correctness of the algorithm. At least for me this seems not to be right:

 if(v != parent[u])
            low[u] = min(low[u], low[v]);

Can anybody prove the correctness of the code or give a counter example and if such example exists can you explain in details another algorithm that is correct, please? :)

Hello everybody,

Recently, I started learning about articulation points, bridges, bi-connected components and strongly connected components. I decided to solve some problems from lightoj and I can't solve this one.

In short, you are given an undirected connected graph with N vertices and M edges (N<=10000, M<=20000). Find the minimum edges we need to add so that the graph should not contain a bridge.

Can anybody tell me what the solution is and prove its correctness since I came up with some algorithms that seemed correct to me but after a while I found some counter-examples, please? And can you give me some problems to solve involving those topics because now the seem kinda confusing to me and I think that I need to practice more, please?

Another question that I want to ask is: I know that a bi-connected graph is a graph without articulation points. But is it true that if a graph doesn't contain a bridge, then it is bi-connected and is it true that if a graph is bi-connected, then it contains a bridge and why?

Thanks in advance!

Hello everybody,

Here is a cool problem that I am unable to solve:

There is a table with 3 rows and N columns. The first row contains a permutation 1,...,N. The second and third row contain integers in the interval [1,N] but there can be repeated numbers in each row. Some random guy decided to remove columns from this table. After that our random guy sorts the numbers in each row and wants to have only equal numbers in each column. We are to find the minimum number of columns our guy needs to remove in order to achieve his goal.

In the cases worth 40% of the total points, it will hold N<=10.

In the cases worth 70% of the total points, it will hold N<=10000.

In the cases worth 100% of the total points, it will hold N<=100000.

I can solve the problem only for 40 out of 100 points.

Please, help me to solve it for full score! :)

Update: Solved! Thanks, Enchom!!! His code is here

Hello everybody,

Some weeks ago I started arranging contests very often in lightoj for me and some of my friends in order to practice. The problems are from lightoj's problemset. You can see the past contests here. Feel free to participate.

I can solve some of the problems but also there are some that I am not able to solve during the contest. After a contest I try to solve the problems that I failed. But I am not able to come up with solutions for all of them. There are three of the problems that I can't solve and find them very interesting:

1) Paths in a tree

Initially there is an undirected tree with N<=20000 nodes but then for some reason the edges become directed. We have to add minimum number of special paths so each node can be reached from each other. A special path is a chain of edges where each edge goes in the opposite direction of the edge in the initial graph. Special paths can share nodes and edges as well.

There are T<=30 test cases.

TL: 2s

ML: 32MB

My idea:

If I see an edge (a,b) I mark in[b] and out[a]. Then I am using dp[node] to calculate the answer. If out[node] is false then dp[node]=1. Otherwise dp[node] is the sum of the dp's of each node's children. Then I print the sum of the dp's of those nodes with in[node]=false.

Unfortunately, my idea is wrong because it fails this case:

5

0 2

1 2

2 3

2 4

The correct answer is 2, my solution prints 4.

2) Coin change 2 Solved! Thanks tenshi_kanade and ffao!!!

My code

In a strange shop there are n types of coins of value A1, A2 ... An. You have to find the number of ways you can make K using the coins. You can use any coin at most K times.

N<=100

K<=10000

Ai<=500

All Ai will be distinct.

There are T<=100 test cases.

TL: 1s

ML: 32MB

My idea:

I use dp[current coin][current K] and calculate each state in O(K) which makes O(T*N*(K^2)) total complexity and gives TLE.

3) Dice 1 Solved! Thanks please_delete_account!!!

My code

You have N dices; each of them has K faces numbered from 1 to K. Now you have arranged the N dices in a line. You can rotate/flip any dice if you want. How many ways you can set the top faces such that the summation of all the top faces equals S?

N<=1000

K<=1000

S<=15000

TL: 2s

ML: 32MB

There are T<=25 test cases.

My idea:

I use dp[current dice][current S] and calculate each state in O(K) which gives TLE.

Please, help me to solve them.

Thanks in advance!

Hello, everybody!

Yesterday I tried to solve this problem on spoj. I spent about three hours on it, but I didn't manage to solve it. In the comments I read that there is a solution in O(n) time complexity. Can you help me, please?

Thanks in advance! :)