Hi Codeforces!

I'm excited to announce the Forethought Future Cup! It will consist of two rounds, an online round on April 20th, 11:05am PDT, and an onsite round on May 4th, 10:05am PDT. **Both of these rounds will be rated and open for all participants**. The top 25 local contestants near San Francisco will be invited to the Forethought office to take part onsite.

Each round will be a combined round. In the first round, there will be 8 problems in 2.5 hours. There will be at least one interactive problem in this round. Please read the interactive problem guide if you haven’t already.

The problems in this round were all written by me. Thanks to ismagilov.code, mohammedehab2002, Jeel_Vaishnav, Learner99, dojiboy9, fortune, y0105w49, KAN, arsijo for testing and coordination. Of course, thanks to MikeMirzayanov for Codeforces and Polygon, and for allowing us to host the round.

### Prizes

T-shirts will be awarded to all onsite participants. 25 shirts will also be randomly awarded to contestants in the elimination round with ranks 1 to 250. The onsite round will also have some monetary prizes:

- First: $500
- Second: $250
- Third: $100
- 4th — 10th: $50

### About Forethought:

At Forethought, our mission is to use AI technology to augment human abilities and make everyone “a genius at their job”. Our main product is Agatha, an assistant that helps customer support agents answer cases more quickly and confidently by suggesting answers and triaging cases. We've raised over $10M in VC funding and were the winners of 2018 SF TechCrunch Disrupt Battlefield.

I joined Forethought back in December 2018. We are a small 12 person startup, and have a lot of competitive programmers on our team, including me, y0105w49, fortune, and dojiboy9 (our CEO, who is also an ICPC World Finals Judge). I’m happy to answer any questions about working here in the comments below or through PM.

We’re hiring! Please fill out this form if you are interested.

### Updates

**UPD 1** The scoring distribution will be **500-1000-1500-2250-2500-3250-3250-3750**

**UPD 2** Tutorial can be found here: https://codeforces.com/blog/entry/66639

**UPD 3** Congratulations to the top 5!

Why does it seem like so many competitive programmers are doing AI startups nowadays? Or does that merely reflect the general hype around AI now.

For me at least, when thinking about what i'm gonna do in the future as a job, nothing really feels that much like competitive programming. For the time being i find AI to be the most fun job of all too. I found AI to be fun from youtube videos of some game playing neural networks and the whole AlphaZero thing, i'm not that sure how fun it actually is. I did some front end/back end development in school but i don't find it nearly as fun as cp.

It's like the programming version of smoking crack with the cool kids. Minus the obvious harm that does, of course.

It's like competitive programming. But with decent pay :)

To be honest, people that do good on competitive programming are more likely to be able to understand and make good use of AI

Hi! I will respond here, since I work with lewin at Forethought.

For me personally, as a competitive programmer, I've always been interested in solving hard mathematical and algorithmic problems. At bigger companies (Facebook, Palantir, Dropbox, Pure Storage) I've worked on a range of problems from infrastructure to databases to even product / front-end work. In research, I also had publications in Machine Learning algorithms.

All-in-all I found that infrastructure, databases, data science (Hadoop, etc.), and machine learning / AI were sets of problems that were "almost as fun as competitive programming" because they often required solving very hard technical problems, and flexing your algorithmic or mathematical mind (I will throw statistics in there as well).

The last factor is "impact" and/or "gratification". If you just want to solve hard problems every day, then research is also a good way of doing this. But my goal in co-founding Forethought is to build a work environment where people who like solving hard problems can (a) come to work every day and do that, and (b) see the impact of their work on real users / humans.

I will also say that I didn't intentionally set out to start an AI company (I am not a fan of "AI hype"). But like many competitive programmers, I saw a hard problem ("how do we make use of all the information being lost inside an enterprise to make people more productive") and set-out to solve it. In this case, "Deep Learning" and "Natural Language Understanding" -- despite typically being "buzz words" -- happened to be the best way to solve the problem.

Hope that helps!

Hey Lewin! How do you enjoy your new job at Forethought compared to Dropbox? I'm curious about the differences between a Unicorn and a ground-level startup, which I imagine are quite significant, and also about what it's like to work at a startup with so many competitive programmers/how that affects your day-to-day.

I've been enjoying the new job. I'll explain why I was looking for a new job in the first place to explain what the differences are.

In short, I got a bit bored and wanted to try something new.

I didn't really know what I wanted to do (and I'm still not too sure what my long term plans are). I ran into Deon a few times over the past year, who I knew from a previous internship, and learned about what he was working on. It's rare to get an opportunity to work at a small stage startup with people you already know. My main goal now is to learn more and grow and see where that leads me in a year or two.

As for working with other competitive programmers, there are some small differences in how we approach some problems. For instance, I think competitive programmers highly value having a tight feedback loop. In competitive programming, you get to see almost immediately how well your code does after you finish writing it. This is similar to a small startup, especially one that works with ML, so I think that style of working is transferable. Other than that, it's really hard to say more concrete things since we have a small sample size. One other benefit of working with competitive programmers is that it's easier to connect with people if you already have something in common.

Will this contest be rated?

Yes! Both of these rounds will be rated for all participants.

if I submit at least once, will I get T-shirt? If no how could I.

You must be in top 10

thanks

If you get 1st place 500$

Expecting this round to be full of awesome questions with strong pretests!!!

Interested, though I would expect to be placed poorly as a Div. 3 participant.

Great time for US participants!

There is always good time for some places while bad for others. For example,it's good for the US means bad for China(for me)

A long but meaningful night with TCO 1A and Forethought Future Cup.

Wow!(Do you mean you took part in 2 contests in one night?)

How will you guys know who's in SF?

sadly with this time it's gonna be think or sleep challenge for me :(

sleeping wins

TCO stage-3 R1-A-> FORETHOUGHT-CUP -> KICKSTART R-Blined up for today..Will the round be in ACM-ICPC rules or in Codeforces rules? And if it's in Codeforces rules, what's the scoring destribution?

is it worth taking part if i won't be able to code last 30 minutes of round?

when you have to do codeforces at 4 but contain multiple electronic anomalies at 5

Drain adjusted?

Yes

Just curious, what does drain mean in this context? Thanks in advance.

In 2hr contest 500pt problem loses 2pts/min.

Without drain adjustment - In >2hr contest 500pt problem also loses 2pts/min.

With drain adjustment - In 2.5hr contest 500pt problem also loses (2/2.5)*2pts/min.

Contest in 2am hope i can growing my rating.

Very less registrations any reason for this :(

Late start time + 2h30 contest = Even later finish time, particularly for India and China.

Perfect timing for Indian coders :)

Bad timing for Asians

My first round was a Div3 round and then a Div2 round, I could clearly see the difference. I guess I'll find out how hard Div1 rounds are today.

I'm hoping for some interesting problems in today's contest :)

Me too

Please retard time by half an hourHey! Stop insulting time!

In problem E, if si is <, what operation is done on the array?

All a[i] < x in A will be flipped, but it's already end of the contest :)

C was a nice problem. BTW how to solve D?

How to do C :(

Loop through the bits of all number(1 to n) and for a particular bit partition each number into two sets depending upon if the bit is set or not. Then query for max distance between the two sets.

As the diameter is the distance between two leaf nodes so in at least one of the query, the two nodes would in different sets. So we need to take the maximum of all query results You can see my code

Can you pls explain the relation of bits with the problem??

Suppose dist(A, B) is max for some A≠B.

→ A and B (in numbers) should differ

→ A and B (in numbers) should differ

at least one bit.→ Call that bit be b. Query two sets: a set with numbers with zero on b-th bit, and the other set with numbers with one on b-th bit.

→ Iterate through all possible b (7 possibilities).

Hello Thank You for sharing your code.. But can you explain the concept of interactive problem? Lie in our code we have to print the query? Please explain thank you very much!

$$$1 -->$$$ Node x (max distance from 1) $$$-->$$$ Node $$$y$$$ (max distance from x = diameter of the tree)

Node x is found by Binary search and then you can just query 1 n-1 x (all nodes except x)

Another explanation about the solution:

Say you try to find the diameter of nodes between A and B. In a divide-and-conquer fashion, think what happens when you divide this sequence in half as partitions P1 and P2. If you query the distance between P1 and P2, you now have to find the distance between nodes exclusively in P2 and in P1.

So solve (A, B) = query(A, B) and solve(A, middle(A, B)) and solve(middle(A, B)+1, B) Imagine the recursion tree of such a procedure if we were to apply it. It would bring the right answer, but we would do too many queries. Can't we 'compress' these queries?

In each depth of recursion K we have multiple disjoint intervals we solve for and for each we query information about a smaller set of nodes than the initial one. Instead of doing them separately, we bring them together at the end of function.

I've explained the last part poorly, but see if my code helps: https://codeforces.com/contest/1146/submission/53071832

It's basically the same solution using bits and parity, but done indirectly (well, at least I think so?).

How to solve D?

For i from 0 to a+b i brute forced the solutions with some recursions. For i greater than a+b solution is i/gcd(a,b)+1 (I hope).

hi is contest rated and if so when do i receive rating thx love from bangladesh

Wait and you'll find out.

What was pretest 8 of D? Spent an hour trying to debug it.

F definitely doesn't seem harder than E. If it involved some more complicated tree DP, sure, maybe, but it's fairly simple. E requires more careful implementation too.

Other than that, a very nice balanced problemset.

But how actually you know it's a

balanced problemset! is it relative or general ?It's the general feel of the problems, not just difficulty levels.

Let's ignore A and B. C is a glorified binary search (also known as an interactive problem — there are very few that are more than that) with the well-known idea for finding diameter, solvable easily by anyone a bit experienced.

D is the first serious problem, which is already a good thing, because most of these 8-problem contests have E as the first serious problem. There are 2 basic ideas: how to find the first $$$x$$$ for which some point is reachable (using some graph search or another) for sufficiently small $$$x$$$ and that for sufficiently large $$$x$$$, any point in the form $$$aA-bB$$$ is reachable, which ties to Bezout's identity.

F is a standard-like problem with tree DP, not so difficult because of that but most importantly, the only such problem — it's perfectly fine being in this problemset, but if there are more of them, the contest becomes too easy.

E is rather ad-hoc, it may involve having to handle different inequalities at different stages ($$$<$$$ vs $$$\le$$$ vs $$$>$$$ vs $$$\ge$$$) and it's easy to mess up the implementation. I wonder if I did.

I haven't read H, but I tried to solve G and while I saw I didn't have enough time during the contest (and there's no time to upsolve, sadly), it seems like some meet-in-the-middle or subset solution, which is really unusual for G.

You can see how I listed a wide range of topics that appear in competitive programming problems — some math, some implementation (no "only implementation"), some standard problem, some ad-hoc parts, some parts where experience is important, an

~~interactive~~binsearch problem, there are trees x2, more general graph search, possibly meet-in-the-middle...Critical mistake

In fact there is quite simple dp for $$$O(n^5)$$$ (my solution will fail however)

One can multiply numbers in the array by two and all make all queries $$$x\to 2x\pm1$$$.

Your comments just confirm that it's an interesting problemset :^). In all of these cases, I actually thought "it's possible but I don't think I have the time to explore it".

Is answer of F only depends on count of 1's in the array (count of the children of root)? Or am I missing something?

tourist after 1 hour of the round

Among the description of Prob C,

"After printing a query do not forget to output end of line and flush the output."is quite vague. I got Idleness Limit Exceeded 7 times before passing the pretest, so wasted 31 minutes. :(Seems problem E can be solved in O(N*Q), pretests passed

UPD. 966 ms on main testsAnd this guy gets AC (358 ms) without using any crazy looking code and pragmas xD

https://codeforces.com/contest/1146/submission/53075220

What is happening here? Is it just yet another crazy CPU cache hit and branch prediction and pipelining and blah blah? Never imagined it could speed it up to 10^10.

Well, I don't see any special thing in the code I mentioned. I guess tests are weak and this guy knows where to break loop as you can see in his code.

Oh I get it now that I see the

`break`

! Thank you.This is counter-test, that leads to

`TLE`

verdict for given submission. I used this test when I tested my solution before submit.Optimized to 811 ms 53124680

Points I've discovered:

`BS = 1024`

has been choosed during contest because 32*1024 bytes can be placed in L1 cache. I thought that for system tests will be a lot of problems, because all submissions runned on multithreaded systems, where only 1 CPU and 1 cache, but a lot of threads working in same time. Therefore, I do not think that`BS=4096`

would have been accepted during system tests.This is cool, easy swapping order of cycles got 100 ms.

I think this is cecause compiler choosed

`alignas`

equal to 32 bytes with`Ofast`

and`avx-avx2`

Another way, not so straightforward, but faster: https://codeforces.com/contest/1146/submission/53111652

And it can be optimized, about 4-8 times more, getting actually $$$\mathcal{O}\left(\frac{NQ}{32}\right)$$$.

a different version of problem E in JOI https://dmoj.ca/problem/joi14p2

Any hints for D?

Find which remainders of $$$a$$$ is possible to visit and what is the minimum of maximum value we visit in that path. It can be done with dfs. Then find how each remainder contributes to the answer. There are a lot of shitty formulas but nice problem.

i feel the first 3 tasks get harder each contest. is this happens with me only ?!

i cant proof my solution for D. but it passed pretest.

i hope someone can proof/disproof this :

for given constrain a <= 100000 and b <= 100000

for i <= 3000000 use Dijkstra to find f(i). O(K log K)

for i > 3000000 f(i) = i/gcd(a,b)+1

It is easy to prove that

`a + b <= 2e5 <= i`

is sufficient. Suppose there are some cell`t`

that can be achieved by`a * x - b * y = t`

. We can arrange`+a`

and`-b`

in any order. So, let's arrange them like this: let's perfom`+a`

while current cell is`<= i + 1e5`

then perfom`-b`

while current cell is`>= i + 1e5`

. Then back to the`+a`

. It is easy to see that current cell will always be`<= i + 2e5`

.For i >= a+b-gcd(a, b), the answer will always be i/gcd(a, b)+1.

So, all we need to do is calculate the answers until a+b-gcd(a, b) using Dijkstra.

Why TLE in this Solution?

https://codeforces.com/contest/1146/submission/53073765

if(t == a+b) have O(N) time complexity

your solution repeat this operation N times so your solution have O(N^2) time complexity

Thanks :)

Then how is this Working?

https://codeforces.com/contest/1146/submission/53058473

if (t.size() + t2.size() == s.size() && t + t2 == s) { cout << t << endl; return 0; }

only done once (when t.size() + t2.size() == s.size()) so overall time complexity is O(N)

Initial statement of E contained typos that were really confusing. All occurences of j were replaces with i. I always open all statements on the very beginning of contest in separate tabs so that I can read them in a case Codeforces is down. This mistake was corrected, but there was no announcement about it, so I read initial version and I wasted some time wondering what the heck is happening here. That perfectly lines up with the fact that I lacked 1-2 mins to get H right (at least on samples).

UPD: Yay, my H passed :|... Thanks for not sending announcement.

Same, but it happened to cross my mind that the statement could be sneakily fixed, so I refreshed the page immediately after seeing the weird indexes :P

I almost got G! :<

There is an issue that I have been facing with codeforces(or maybe my network) recently. Sometimes when I try to submit my code as a file some unknown webpage appears with "Apache" or something like that written on it and I have to go back and submit my solution by copy paste. I was igonoring this since it occured only at the time of practice. But today with few seconds remaining I submitted my solution for E problem but faced this problem and was unable to submit it. I request if anyone can help me or atleast tell the cause of the problem. error screen

And even before the result, they have released the tutorials!! Great Job !! Thanks

A lot of bad typos, 2 well-known problems... Is it rated?

Btw, we had a quite funny discussion about problem G among our group.

Marcin_smu said that G it is hard to find more standard problem than G. I didn't want to call that as standard as it gets, but I agreed that this was kinda straightforward to me knowing a few similar problems before. It turned out that we had two completely different solutions XD. His solution was flow while my solution was dp.

Problem K from CERC 14?

No, but very close. L from CERC 2014 :). We had very similar problem on POI as well in 2015: https://szkopul.edu.pl/problemset/problem/kYVp05sX8lzHWNwn93xjcYwH/site/?key=statement

Yeah, that's the one I meant. I somehow recalled that one during the contest but still unable to solve it :(

I was actually reminded of that problem (from CERC), but I thought it would be something different... UPD: It is different, a nice variation on the same idea. In that problem, you just kill the farthest alien and the problem trivially splits into 2 [l, r] subproblems. Here, you can decide to keep some conditions, so the DP states are different.

Also lol, I had first blood on it in that CERC and neither of you two solved it, such a standard problem. /s

Where is the list of randomly chosen winners?

The list of people who won T-shirts.

We used these two files to generate the list:

get_tshirts.py

randgen.cpp

The seed is the score that the winner got.

OMG;; how can I get this t-shirt?

CF team will contact you soon.

Love you guys all ya thx!!!

Wow, just realized that I had the same rank with a t-shirt recipient...

O my god! My first CF-T-shirt. I am so happy!

Thanks to MikeMirzayanov for supporting such contests with nice prizes!

can someone please explain why my solution for B giving tle??? solution B

Here,

`(hey + input[i])`

is created in linear time, the original`hey`

is destroyed, and the new value is assigned. So`hey = hey + input[i]`

runs in linear time of length of`hey`

. This means the loop will run in $$$O(n^2)$$$, giving you a TLE. This mistake is known as Schlemiel the Painter's algorithm.On the other hand,

`hey += input[i]`

does an in-place insertion, the complexity being linear to the length of right-hand-side string. Think of it as a`vector<char>`

doing`push_back`

(though actual implementation differs). In this way you can get AC.Bonjour! I did some minimal benchmarking and the results justify your claims. :)

thanks a lot :)

How do I know whether I am the top 25 in SF ( Most likely not :P )

awesome