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.

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!

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.

• I was at Dropbox for a little over 3 years, and I joined when there were already ~1000 people. It was a good first job in industry to learn how things worked in general. Near the end, I felt like my work wasn't that impactful in terms of Dropbox as a product (even though it might be seen by millions of people). I feel a lot better now at a smaller company since I can see how my work is impacting the product in bigger ways.
• I was on the same team during my time at Dropbox and didn't feel like I was learning new things at the same rate when I first started. I also wanted to learn more about AI/ML, since I want to understand what's so special about it and I have almost no experience in it other than taking a class about it in undergrad. There were some ML teams in Dropbox, but they felt new and underdeveloped and they seemed to be looking for people with more experience in ML (like a masters or other industry). I think it might be harder to get into other large companies in AI for this reason, and I feel I learn best through hands-on experience, so that's why I wanted to look for a startup.
• I also wanted more ownership of what I'm doing. It felt that the product managers at Dropbox have a lot of say in what gets implemented, and I wanted more freedom. At a startup, I do have more control over what I work on.

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.

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

You must be in top 10

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)

sleeping wins

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

Yes

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

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

Bad timing for Asians

Me too

Hey! Stop insulting time!

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

$$$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.net/contest/1146/submission/53071832

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

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).

Wait and you'll find out.

But how actually you know it's a balanced problemset ! is it relative or general ?

pretests

And this guy gets AC (358 ms) without using any crazy looking code and pragmas xD

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

Optimized to 811 ms 53124680
Points I've discovered:

• No need in alignas(32)
• Greatest boost in speed makes applying algo when last chunk is proceeded separately (around 100ms)
• BS = 4096 or 8192 instead of 1024 gives around 50ms
• Changing compiler to c++14 saves 20ms 53125055
• Optimizations are evil

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

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

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.

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.

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

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

Problem K from CERC 14?

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

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!

FOR(i, 0, n)
        if(input[i] != 'a')
            hey = hey + input[i];

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.