Hello Codeforces!

HFT Battle 2017 is going on – the trading algorithms competition, in which every participant can try on an HFT researcher’s hat. The goal is to create a stable and profitable HFT algorithm by researching a market microstructure and a behaviour of the financial instrument. In May we will be hosting another 24-hour competition in code optimization and speeding up based on algorithms created during HFT Battle. We hope that Codeforces users will especially like this format :)

During the competition we provide you a set of real HFT-instruments for research and strategy analysis and real market data from one of the world’s largest exchanges. Same as last year, trading conditions are simplified compared to the real ones: there are lower fees and round-trip.

Also there are some significant differences from the previous competition:

• You are able to create your strategies both in C++ or Python.
• We made it possible to participate in teams. To do this you should create a single account for the entire team and provide the information about one of the participants during the registration process.
• You can call out any other participant for a duel, where your strategies can see and affect each other’s transactions. Let the battle begin!

How to start

To make the strategy development easier, we have prepared the sample strategy and collected few ideas for the algorithm improvement at one place with the corresponding code examples.

We suggest you to start with the brief documentation, which will be enough for you to become familiar with the competition system. Also we have developed the offline development package: https://github.com/hftbattle/hftbattle.

The competition ends on the 30th of April 2017. The final testing will be held after that on a set of 20 new trading sessions.

This year TOP-20 participants will be awarded with valuable prizes. The best competitors will be invited to an interview at AIM Tech and will have an opportunity to join our team.

We will be happy to hear your feedback! You may use “Support” button in the web interface or text directly to [email protected]. You may also join the active discussion of the contest in our Telegram channel!

It is not required to have any specific economical knowledge to create your strategy. Basic C++ or Python skills would be enough. We are confident that most of Codeforces participants will be able to reach excellent results!

We wish you high rating and great results in HFT Battle 2017!

Hey, guys!

I'm excited to invite you to participate in 101 Hack June 2016! The contest will start at 16.30 UTC, June 20.

I'm the problemsetter of this round. You may have seen my tasks on previous HackerRank contests or may have participated in Codeforces Round 319 (Div. 1) or Codeforces Round 319 (Div. 2).

There will be five tasks and two hours for you to solve them. Top-10 contestants on the leaderboard will receive awesome HackerRank T-shirts! (I'm really jealous, since I don't have one)

I'd like to thank wanbo for his invaluable help and testing all the problems, danilka.pro for testing one of the problems and his cool proof of author's solution, Zlobober for his help in estimation of one of the tasks difficulty, and sankear, he did nice job sitting in the bar with me and discussing the problems.

I hope you will enjoy the tasks. Please read all of the problem statements during contest, as it may be essential for your final place.

Good luck!

UPD. The contest has ended. Special congratulations to Lewin: the only contestant who solved the last task!

Top-10:

1). Lewin

2). I_love_Tanya_Romanova

3). Errichto

4). tourist

5). Temirulan

6). Kostroma

7). Deemo

8). riadwaw

9). uwi

10). mgch

Task A. Div2.

It's easy to see that number x can appear in column i only once — in row x / i. For every column i, let's check that x divides i and x / i ≤ n. If all requirements are met, we'll update the answer.

The complexity is O(n)

Source

Task B. Div2.

Let's consider two cases: n > m and n ≤ m.

If n > m, let's look at prefix sums. By pigeonhole principle, there are two equals sums modulo m. Assume S_lmodm = S_rmodm. Then the sum on segment [l + 1, r] equals zero modulo m, that means the answer is definitely "YES".

If n ≤ m, we'll solve this task using dynamic programming in O(m²) time. Assume can[i][r] means if we can achieve the sum equal to r modulo m using only first i - 1 items. The updates in this dynamic programming are obvious: we either take number a_i and go to the state can[i + 1][(r + a_i) mod m] or not, then we'll get to the state can[i + 1][r].

The complexity is O(m²).

Source

Task A. Div1.

If Petya didn't ask p^k, where p is prime and k ≥ 1, he would not be able to distinguish p^k - 1 and p^k.

That means, he should ask all the numbers p^k. It's easy to prove that this sequence actually guesses all the numbers from 1 to n

The complexity is O(N^1.5) or O(NloglogN) depending on primality test.

Source

Task B. Div1.

Let's look at the answer. It's easy to notice, that centers of that tree must turn into centers after applying the permutation. That means, permutation must have cycle with length 1 or 2 since there're at most two centers.

If permutation has cycle with length 1, we can connect all the other vertices to it.

For example, let's look at the permutation (4, 2, 1, 3). 2 is a cycle with length 2, so let's connect all the other vertices to it. The resulting tree edges would be (1, 2), (2, 3), (2, 4).

If answer has two centers, let's remove the edge between them. The tree will split into two connected parts. It's easy to see that they will turn into each other after applying permutation. That means, all cycles should be even.

It's easy to come up with answer with these restrictions. Let's connect vertices from the cycles with length 2. Then, let's connect vertices with odd position in cycles to first of these and vetices with even cycles to second one.

For example, let's consider permutation (6, 5, 4, 3, 1, 2). There are two cycles: (3, 4) и (1, 6, 2, 5). We add edge (3, 4), all other vertices we connect to these two, obtaining edges (1, 3), (6, 4), (2, 3), (5, 4).

The complexity is O(N).

Source

Task C. Div1.

Let's split rectangle 10⁶ × 10⁶ by vertical lines into 1000 rectangles 10³ × 10⁶. Let's number them from left to right. We're going to pass through points rectangle by rectangle. Inside the rectangle we're going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it's odd.

Let's calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we're passing 1000 rectangles from 0 to 10⁶, 10⁹ in total. By x-coordinate we're spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 10⁹ + 2000000 in total, which perfectly fits.

The complexity is O(n * log(n))

Source

Task D. Div1.

Let's optimize the first solution that comes to mind: O(m * d_max), let's calculate can[t][v] — can we get to the vertice v, while passing exactly t edges.

Now, it's easy to find out that the set of edges we are able to go through changed only m times. Let's sort these edges in increasing order of d_i, that means for each i d_i ≤ d_i + 1. Let's calculate can[t][v] only for t = d_i. We can calculate can[d_i + 1] using can[d_i] by raising the adjacency matrix to the d_i + 1 - d_i power and applying it to can[d_i].

Next step is to fix an edge with maximal d_i on our shortest path, let it be i. We know all the vertices we can be at moment d_i, so we need to calculate the shortest path to n - 1 using edges we can go through. We can even use Floyd algorithm to calculate that.

The complexity of this solution is O(m * n³ * log(d_max)) and it's not enough.

Next observation is that adjacency matrix contains only zeroes or ones, so we can multiply these matrixes using bitsets in O(n³ / 32).

This makes complexity O(m * n³ * log(d_max) / 32), which gets accepted.

Source

Task E. Div1.

Let's solve an easier task first: independent of bipartivity, the color of edge changes.

Then we could write a solution, which is pretty similar to solution of Dynamic Connectivity Offline task in O(nlog²ⁿ).

Let's consider only cases, where edges are not being deleted from the color graph. Then, we could use DSU with storing parity of the way to the parent along with parent. Now we can find parity of the path to the root by jumping through parents and xoring the parities. Also, we can connect two components by accurately calculating the parity of the path from one root to another.

Now edges are being deleted. For each edge and each color we know the segments of requests, when this edge will be in the graph of specified color. Let's build a segment tree on requests, in each vertex of the tree we store list of edges which exist on the subsegment. Every segment will be split into log parts, so, totally there would be n * log small parts.

Now we can dfs this segment tree with DSU. We get inside the vertex, apply all the requests inside it, go through the children and revert DSU to initial state. We also answer requests in leafs of the segment tree.

Let's return to initial task. We can't use this technique, because we don't know the exact segments of edge existence.

Instead, let's do following. Initially we add each edge right until the first appearance of this edge in requests. Now, when we're in some leaf, we found out which color this edge would be right until the next appearance of this edge. So, let's update this edge on that segment.

For each leaf we're going to make an update at most once, so the complexity is O(nlog²n).

Source

If anything is unclear or bad-written, ask any questions.

Hey there!

Today at 19.30, Moscow time there will be Codeforces Round #319 and it's strongly disadvised to skip it.

I'm the author of this round, my name is Dima Gorbunov and it's my first round on Codeforces. I really hope you're going to like it and everyone will find a satisfying problem. In order to increase the probability of finding that task, please read all of the problem statements.

As usual, I'd like to thank Zlobober for his invaluable help and his special sense of humour, sankear for coding additional solutions, Delinur for the English statements and MikeMirzayanov for amazing systems Codeforces and Polygon.

You're going to have two hours to solve 5 problems. Good luck!

UPD. The scores in first division are 500-1250-1250-2000-2750.

In second division — 500-1250-1500-2250-2250,

UPD2. Because of large size tests for some of the problems, system testing will be slow (it's possible that it will take several hours). Thanks for your patience!

UPD3. English editorial is also accessible.

UPD4. Winners!

Div1:

1). Marcin_smu

2). mnbvmar

3). I_love_Tanya_Romanova

Div2:

1). latisel

2). wrong_order

3). ntitry826

A special respect to al13n for correct solution of Div1.E during the contest!