Forethought Future Cup
By Lewin, 6 years ago, In English

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, vlyubin, 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, vlyubin, 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://mirror.codeforces.com/blog/entry/66639

UPD 3 Congratulations to the top 5!

  1. tourist
  2. Benq
  3. Radewoosh
  4. yutaka1999
  5. ainta
  • Vote: I like it
  • +423
  • Vote: I do not like it

Comments Comments (106)
| Write comment?
»
6 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +41 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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!

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +166 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +265 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Will this contest be rated?

→ Reply
»
6 years ago, # |
  Vote: I like it -27 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Great time for US participants!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

How will you guys know who's in SF?

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

TCO stage-3 R1-A-> FORETHOUGHT-CUP -> KICKSTART R-B lined up for today..

→ Reply
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Will the round be in ACM-ICPC rules or in Codeforces rules? And if it's in Codeforces rules, what's the scoring destribution?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Drain adjusted?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yes

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Contest in 2am hope i can growing my rating.

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Very less registrations any reason for this :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bad timing for Asians

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -61 Vote: I do not like it

Please retard time by half an hour

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to do C :(

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

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

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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://mirror.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?).

    → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like 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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I haven't read H

        Critical mistake

        unusual G

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

        > vs >= in E

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like 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?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +179 Vote: I do not like it

tourist after 1 hour of the round

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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. :(

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Seems problem E can be solved in O(N*Q), pretests passed

UPD. 966 ms on main tests

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    pretests

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

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

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Oh I get it now that I see the break! Thank you.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      This is counter-test, that leads to TLE verdict for given submission. I used this test when I tested my solution before submit.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      Greatest boost in speed makes applying algo when last chunk is proceeded separately (around 100ms)

      This is cool, easy swapping order of cycles got 100 ms.

      No need in alignas(32)

      I think this is cecause compiler choosed alignas equal to 32 bytes with Ofast and avx-avx2

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Another way, not so straightforward, but faster: https://mirror.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)$$$.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for D?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why TLE in this Solution?

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

I almost got G! :<

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +56 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Problem K from CERC 14?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it +7 Vote: I do not like 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

        → Reply
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Where is the list of randomly chosen winners?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +101 Vote: I do not like it

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.

List place Contest Rank Name
6 1146 6 Um_nik
36 1146 36 budalnik
45 1146 45 majk
53 1146 53 jiangly_fan
54 1146 54 Namnamseo
65 1146 65 tamionv
67 1146 67 tabasz
76 1146 76 orz
79 1146 79 AndreySergunin
89 1146 89 E869120
97 1146 97 hank55663
102 1146 102 amnesiac_dusk
124 1146 124 pllk
128 1146 128 adedalic
155 1146 155 mibig
172 1146 172 ppc_qjd
179 1146 179 dmkz
189 1146 189 Fortin
191 1146 191 teapotd
208 1146 208 kabuszki
209 1146 209 MrDindows
228 1146 228 jugol
229 1146 229 yzyz
235 1146 234 Derbent
241 1146 241 ramchandra
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      CF team will contact you soon.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Love you guys all ya thx!!!

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Thanks to MikeMirzayanov for supporting such contests with nice prizes!

    → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it 
    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Bonjour! I did some minimal benchmarking and the results justify your claims. :) 

      #include <iostream>
#include <cstdio>

#include <chrono> 
using namespace std::chrono; 
using namespace std;

void api1(int turn)
{
    string str = "";
    for(int i = 0; i < turn; i++)
    {
        str = str + "SchlemielThePainterProblem";
    }
}

void api2(int turn)
{
    string str = "";
    for(int i = 0; i < turn; i++)
    {
        str += "SchlemielThePainterProblem";
    }
}

int main()
{
    int turn; cin >> turn;

    auto start = high_resolution_clock::now();
    api1(turn);
    auto stop = high_resolution_clock::now(); 
    auto duration = duration_cast<microseconds>(stop - start); 
    cout << "duration for str = str + .. = " << duration.count() << endl;


    start = high_resolution_clock::now();
    api2(turn);
    stop = high_resolution_clock::now(); 
    duration = duration_cast<microseconds>(stop - start); 

    cout << "duration for str +=  .. = " << duration.count() << endl;

    /*
    10
    duration for str = str + .. = 42
    duration for str +=  .. = 5
    100
    duration for str = str + .. = 117
    duration for str +=  .. = 9
    1000
    duration for str = str + .. = 1045
    duration for str +=  .. = 37
    10000
    duration for str = str + .. = 97951
    duration for str +=  .. = 509
*/
    return 0;
}
      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks a lot :)

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Nothing Important

→ Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

awesome

→ Reply