Hi all,

The 8VC Venture Cup 2017 - Final Round is tommorrow at 18:05 UTC. Along with that, Codeforces Round #393 will be held at the same time both for Div. 1 and Div. 2 participants. The Div. 1 Edition will contain the same problems as the Final Round, the Div. 2 Edition will be easier.

Of course, those who have placed in top 200 in 8VC Venture Cup 2017 - Elimination Round should register for the Final Round, all the others should register for Div. 1 or Div. 2 editions according to their rating. All three contests will contain six problems, last two hours and be rated.

The problem authors are Um_nik, Endagorion, sivukhin, pashka and me. Also huge thanks to fcspartakm for his help in preparation, and to vepifanov and AlexFetisov for testing the round. I suggest you reading all the problems to find which one you like the most!

I'd like to remind you about the prizes:

• Overall 1st place — $2000
• Overall 2nd place — $1000
• Overall 3rd-5th places — $500 each
• Overall 1-50th place — t-shirts with 8VC and company logos
• Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar and 8VC) and other Silicon Valley technologists
• Local top finishers — Opportunity to meet with leadership from 8VC portfolio companies

Please welcome one more company became interested in the Venture Cup, Progressly!

Progressly is a cloud-based Operational Performance Management platform allows you to document, collaborate on, and gain contextual insights into core business processes and outcomes in real time.

The scoring is usual in all three contests: 500-1000-1500-2000-2500-3000.

Congratulations to the winners!

8VC Vecture Cup 2017 winners:

1. V--o_o--V
2. bmerry
3. Marcin_smu
4. LHiC
5. qwerty787788

Codeforces Round #393 Div. 1 winners:

1. HYPERHYPERHYPERCUBELOVER
2. RomaWhite
3. PavelKunyavskiy
4. snuke
5. vintage_Vlad_Makeev

Codeforces Round #393 Div. 2 winners:

1. Kacey
2. wcx5tq957i
3. BekzhanKassenov
4. Tailz
5. BitHashTech

Editorial

Hello everyone! The first round of the 8VC Venture Cup 2017 will be held on Sunday.

I am honoured to be the problemsetter of the round. Reyna helped me a lot. Huge applause to KAN for his valuable coordinator's help, and MikeMirzayanov for his admirable work for the Codeforces comunity. I also want to thank testers very much (Alexey ashmelev Shmelev and Alex AlexFetisov Fetisov).

This round is a first stage of 8VC Venture Cup 2017. If you want to acknowledge yourselves with the competition, try here.

The main character of the round is PolandBall. It's a small friendly Ball who lives in a forest along with other Balls. You'll surely like it :)

I tried to fulfill your demands with a various, interesting and challenging problems described in a concise way.

Hope to see you soon, good luck and have fun!

UPD1: Scoring 500 — 1000 — 1500 — 2250 — 2500 — 2750 — 3500.

UPD2 Thank you for participation! Contest is over. Did you like the problemset? Feel free to comment =)

UPD3 Editorial

UPD4: Winners

1. tourist
2. jqdai0815
3. W4yneb0t
4. ilyakor
5. ainta.

Hope you've had a good time with PolandBall solving the problems.

Congratulations to all the winners and TOP-200 who advances into 8VC Finals =)

Hello Codeforces!

I'm pleased to announce the first championship hosted on the Codeforces platform. Welcome 8VC Venture Cup 2017!

8VC will be hosting a coding championship on Codeforces. The championship will begin on January 15 and take place in 2 rounds.

The contest will occur in two rounds:

• The Elimination Round is online and takes place on January 15, 17:05 (UTC). Elimination Round follows regular Codeforces rules and consists of 7-8 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round.
• The Final Round takes place on January 22, consists of 5-6 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round. We will invite the top local finishers in Elimination Round to Woodside, CA to compete in the Final Round. In addition, we will invite the top 200 overall finishers to compete online.

Cool prizes are offered to winners and best participants.

PRIZES

• Overall 1st place — $2000
• Overall 2nd place — $1000
• Overall 3rd-5th places — $500 each
• Overall 1-50th place — t-shirts with 8VC and company logos
• Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar and 8VC) and other Silicon Valley technologists
• Local top finishers — Opportunity to meet with leadership from 8VC portfolio companies

ABOUT 8VC

8VC, which consists of Joe Lonsdale (co-founder of Palantir) and his core team from Formation | 8, is a Silicon Valley venture capital firm that invests in industry-transforming technology companies. The team's investment portfolio includes companies such as the selected companies below, and a host of other top technology platforms that leverage modern algorithms and data science to power their core business processes.

Hello everyone!

The final round of the 8VC Venture Cup will be held on Feb/28/2016 18:10 (UTC). ecnerwala and I are the problem setters. We want to thank GlebsHP and vnovakovski for help in preparing the contest, stella_marine for fixing the statements, and MikeMirzayanov for creating the Codeforces platform.

The contest is by invitation only to the top 200 contestants and top local contestants from Round 1 and contains six problems. We will also hold rated, out-of-contest participation for both div1 and div2 contestants — all three groups will feature slightly different problemsets. Local contestants will compete onsite in Silicon Valley. OpenGov, one of the featured 8 | VC companies, has been generous to host this competition at their offices; see more details about this awesome company below:

OpenGov transforms the way the world analyzes and allocates public money. With more than 700 government customers across 45 states in a rapidly expanding network, OpenGov is the market leader in cloud-based financial intelligence, budgeting, and transparency for government. The OpenGov platform transforms government financial data into intuitive, interactive visualizations for both internal government users and citizens.

ABOUT 8 | PARTNERS

8 | Partners, which consists of Joe Lonsdale (co-founder of Palantir) and his core team from Formation | 8, is a Silicon Valley venture capital firm that invests in industry-transforming technology companies. The team's investment portfolio includes companies such as those featured below, and a host of other top technology platforms that leverage modern algorithms and data science to power their core business processes. If you are interested to connect, please take a look at http://www.codeforces.com/8vc/apply.

PRIZES

• Overall 1st place — $2500
• Overall 2nd place — $1000
• Overall 3rd-5th places — $500 each
• Overall 1-50th place — t-shirts with 8 | VC and company logos
• Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar, & 8 | Partners) and other Silicon Valley technologists
• Local top finishers — Opportunity to meet with leadership from 8 | VC portfolio companies

The scoring distribution will be standard for all three divisions: 500 — 1000 — 1500 — 2000 — 2500 — 3000

Good luck!

UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest.

Congratulations to the top overall contestants:

1. tourist
2. Egor
3. ikatanic
4. enot110
5. DemiGuo

As well as the top onsite contestants:

1. winger
2. waterfalls
3. KADR

Editorial can be found here.

Thanks for participating!

626A - Robot Sequence

We can simulate Calvin’s path on each substring, and check if he returns to the origin.

Runtime: O(n³)

626B - Cards

Note that if we have exactly one card of each color, we can always make all three options (by symmetry). Thus, if we have at least one of each color, or at least two of each of two colors, we can make all three options. The remaining cases are: if we only have one color, that’s the only possible final card; if we have one of each of two colors, we can only make the third color; if we have at least two of one color and exactly one of a second, we can only make the second or third color (e.g. sample 2).

Runtime: O(1)

626C - Block Towers

There are a variety of ways to do this problem. Here is one way: if the answer is X, there must be at least n multiples of 2 below X, at least m multiples of 3 below X, and at least n + m multiples of 2 or 3 below X. These conditions are actually sufficient, so we need to find the smallest X such that , , and . We can do this with a linear search, or with an explicit formula.

Runtime: O(1)

626D - Jerry's Protest

We do this algorithm in two phases: first, we compute the probability distribution of the difference between the winner and loser of each round. This takes O(n²) time. Then, we can iterate over the 2 differences which Andrew wins by and compute the probability that Jerry has a greater total using with suffix sums.

Runtime: O(n² + a_max²)

626E - Simple Skewness

We can show that any subset with maximal simple skewness should have odd size (otherwise we drop the larger middle element: this decreases the median by more than it decreases the mean, assuming the mean is larger than the median).

Let’s fix the median at x_i (in the sorted list), and set the size of the set to 2j + 1. We’d like to maximize the mean, so we can greedily choose the largest j elements below the median and the largest j elements above the median: x_i - j, ..., x_i - 1 and x_{n - j + 1}, ..., x_n.

Now, notice that by increasing j by 1, we add in the elements x_{i - j - 1} and x_n - j, which decrease as j increases. Thus, for a fixed i, the overall mean is bitonic in j (it increases then decreases), so we can binary search on the marginal utility to find the optimum.

Runtime:

626F - Group Projects

This is a dynamic programming problem. Notice that the total imbalance of the groups only depends on which students are the maximum in each group and which are the minimum in each group. We thus can think of groups as intervals bounded by the minimum and maximum student. Moreover, the total imbalance is the sum over all unit ranges of the number of intervals covering that range. We can use this formula to do our DP.

If we sort the students in increasing size, DP state is as follows: the number of students processed so far, the number of g groups which are currently “open” (have a minimum but no maximum), and the total imbalance k so far. For each student, we first add the appropriate value to the total imbalance (g times the distance to the previous student), and then either put the student in his own group (doesn’t change g), start a new group (increment g), add the student to one of the g groups (doesn’t change g), or close one of the g groups (decrement g).

Runtime: O(n²k)

626G - Raffles

First, note that the marginal utility of each additional ticket in a single raffle is decreasing. Thus, to solve the initial state, we can use a heap data structure to store the optimal raffles.

Now, after each update, we can show that the distribution should not change by much. In particular, after one ticket is added to a raffle, Johnny should either remove one ticket from that raffle and place it elsewhere, not change anything, or, if the raffle was already full, put one more ticket in to keep it full. Similarly, after a ticket is removed, Johnny should either do nothing, remove one ticket to stay under the maximum, or add one ticket. (The proofs are fairly simple and involve looking at the “cutoff” marginal utility of Johnny’s tickets.) All of these operations can be performed using two heaps storing the optimal ticket to add and the optimal ticket to remove.

Runtime:

Hello everyone! The first round of the 8VC Venture Cup will be held on Saturday, February 13th at 12:35PM EST. ecnerwala and I are the problem setters. We want to thank GlebsHP for his help in preparing the contest, Delinur for translating the problems, and MikeMirzayanov for creating the Codeforces platform

The contest is for competitors in both divisions and contains seven problems. The scoring distribution is as follows:

500 — 750 — 1000 — 1500 — 2000 — 2500 — 3000

The contest will be slightly longer than usual — two and a half hours. The top 200 contestants will advance to the final round, and the top 20 local finishers will be invited to Woodside, CA to compete onsite. Good luck!

UPD: System testing is now over. Congratulations to the top contestants:

1. Petr
2. jqdai0815
3. ilyakor
4. bmerry
5. Errichto

The top 200 contestants will advance to the final round in two weeks. Congratulations!

The editorial can be found here.

Hey Codeforces!

I’ve worked with Addepar and the broader 8 | family of companies in Silicon Valley throughout 2014 and 2015, and it’s been an excellent experience. I would encourage everyone in the community to learn more about the great work that these companies are doing and I’m happy to announce that 8 | Partners will be hosting the 8 | VC VentureCup on Codeforces! It’ll be a fun contest and I’ve worked on the problems along with a few competitive programmers in our network. The contest will begin on February 13 and consist of two rounds.

ABOUT 8 | PARTNERS

8 | Partners, which consists of Joe Lonsdale (co-founder of Palantir) and his core team from Formation | 8, is a Silicon Valley venture capital firm that invests in industry-transforming technology companies. The team's investment portfolio includes companies such as those featured below, and a host of other top technology platforms that leverage modern algorithms and data science to power their core business processes.

SELECT 8 | FEATURED COMPANIES

If you’re interested in job opportunities with these companies or others in the 8VC portfolio, contact us below!

THE CONTEST

The contest will occur in two rounds:

Round 1 is online and takes place on February 13. Round 1 follows regular Codeforces rules and consists of 7 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round.

Round 2 takes place on February 28, consists of 5 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round. We will invite the top 20 local finishers in Round 1 to Woodside, CA to compete in Round 2. In addition, we will invite the top 200 overall finishers to compete online.

PRIZES

• Overall 1st place — $2500
• Overall 2nd place — $1000
• Overall 3rd-5th places — $500 each
• Overall 1-50th place — t-shirts with 8 | VC and company logos
• Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar, & 8 | Partners) and other Silicon Valley technologists
• Local top finishers — Opportunity to meet with leadership from 8 | VC portfolio companies

Good luck!