8VC Venture Cup 2016 — Final Round
By scott_wu, 9 years ago, In English

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!

  • Vote: I like it
  • +165
  • Vote: I do not like it

Comments Comments (200)
| Write comment?
»
9 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Will problem set be same for both division and top 200 contestants ?

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

what about difficulty of problems ?

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

    As mentioned in a previous blog, the problems today is harder than in a regular Codeforces round. Since it alao has one more problem than usual, I'm afraid 2 hours is a bit short :((

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

      regular codeforces round means Div2 and Div1 combined rounds or Div1 rounds ?

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

      Will the Div.2 version be easier?

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

I was invited to onsite though didn't get into top-200 in the Round 1. System doesn't allow me to register to "Final Round" because I am not in top-200. Should I go to onsite but compete in "Final Round (Div. 1 Edition)"?

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

    Please, do not register on Div.1/Div.2 Editions. I'll register you on "Final Round" manually.

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

stella_marine for translating the problems

Where is Delinur then?

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

what about the format of unofficial div. 1 and div. 2 rounds? how many problems in each, and will they contain the same problems, or some will be different?

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

    The problemset for div. 1 will be a bit easier than from problemset for final round. Same, the problemsset for div. 2 will be a bit easier than the problemset for div. 2.

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

      "problemset for div. 2 will be a bit easier than the problemset for div. 2."

      Not really sure how that's possible...

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

        He might mean that "The problemset for div. 1 will be a bit easier than from problemset for final round. Same, the problemsset for div. 2 will be a bit easier than the problemset for div. 1."

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

      div 1, div 2, div 3

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

Please let me register in div1 edition, I don't want to lose my ratings

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

    I am sure you will do great...

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

How will be the rating system distribution? :/

I mean, will it be combined for all contestants, separated between Div1-Div2, or even Final-Div1-Div2?

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

    Since problem set is not same for all 3 variants it can't be combined

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

      ow, you caught me there... oh no :')

      (thanks anyway!)

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

My internet speed is fluctuating today, so I want to participate unoffiaclly (without registration). Is it possible?

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

    Try virtual participation after the round maybe? I think that is the only way.

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

      Actually, I remember once solving problems without registration during contest, but there was recently a contest unofficial participation was disallowed because of large no. of official registrants. That's what I was confirming about, if the same will happen today.

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

    You can wait 2 hours and then participate virtually

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

Wow, official finals are harder than Div1 set and only the top 200 are participating, hello rating loss.

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

?

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

why contest will be started too late? Now it is mid-night.so...............

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

    You might find it hard to believe, but the world has different time zones. I believe it's morning for the contest creators.

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

      if contest will be started codeforces usual time,i think most of them will be helpful.bcoz participant will be high .

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

        If I got the right timezones, the usual Codeforces time is too early morning for the organizers. The current time allows for both Americans and Europeans as well as parts of Asia to have it at reasonable (not like 3am) time.

        Also I hope participants are not high while coding, doesn't seem like a good idea!

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

        Oh God, how I like to be high while at contest.

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

          After an hour of making div.0 E fit into TL I actually feel high.

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

        bcoz participant will be high

        Don't do drugs, kids!

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

        Lol You mean number of participants will be high haha

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

        One has to wonder about the meaning of the term "High Elves".

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

You can see onsite finalists only by link: http://codeforces.net/contest/627/standings?list=b0ba514e26c9f1c73337415d0f8927e6

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

    Em, I think you have a bug there. I'm on the list, but I'm not an onsite finalist.

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

      It seems it shows finalists + current user. It will be fixed, but you can easily compare your result and onsiters!

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

    For some reason I can see myself in this list, despite not being onsite. Is it OK?

    P.S. Nevermind. It seems every contest participant can see himself even if he is not in the list.

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

    Please remove me from that list. It seems somewhere I clicked the button that I don't supposed to click :-)

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

Please modify the problem statement of DIV2 Problem B, it's confusing and difficult to understand :(

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

Not sure what to feel about the problemset

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

Does anyone know what pretest 5 for Div2 C was? (task with XOR, sum given)

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

    Probably a high integer value > 10^9 I got WA at it just because I was making sums till 30 bits only!

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

      You're right, just tested my solution with large numbers and it messed up, though I have no idea why at the moment =/

      Oh goddamnit got it. There I was thinking I was clever by using __builtin_popcount() to count the number of 1 bits in X. Turns out it takes int as a parameter, so it's cast down, disregarding the higher part. WAAH!

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

        Ya you need to use __builtin_popcountll(). (Just figured this out yesterday)

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

        Same thing happened to me. :( I spent some 45 minutes debugging it, when it struck me. FML.

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

    Something like 10^12 10^12. My error was because of integer overflow.

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

    I failed this pretest many times.

    My mistake was that when sum == xor I divided the result by 2 and it's supposed to subtract 2 from the result because only the pairs (sum, 0) and (0, sum) are invalid.

    It passed pretests after that, hopefully systests too.

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

    I'm almost certain it was of the form (2 ^ i - 1) (2 ^ i - 1) for some positive integer i < 40. For instance: 65535 65535. I added a check in my code for this particular case (the answer is 2 ^ i - 2), and it passed the pretests.

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

      If after removing the 1s in xor from s, we get 0, then we subtract 2, otherwise, answer=2^no. of 1s in x

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

      Why is that case different from other tests of the form i i? In all those cases you're supposed to subtract 2 from the answer.

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

    try 4 4 answer is 0

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

Somehow someone failed Div 2 C with the test : 7 5

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +113 Vote: I do not like it

Holy shit, this went well. I really really hope I won't fail systests on anything (and that I'll become IGM).

UPD: Epic win.

My (short) solutions for A-E:

A: Process odd bits of X first, even bits afterwards. If the k-th bit of X is 1, what does it contribute to the sum S? If it's even, what can it contribute to S? Special case: subtract 2 if a = 0 or b = 0 is possible.

B: Straightforward, remember the number of orders per day ord(i) and compute a prefix sum of min(ord(i), B) and a suffix sum of max(ord(i), A) for every query — using Fenwick trees.

C: Process the fuel stations from cheapest to most expensive, compute the optimal amount of fuel when exiting that station (you only want to reach the first cheapest); from that, we can find the amount when entering that station and thus the cost.

D: Binary search. Special case: answer = minimum Ai. If we forbid some vertices, we can split the remaining tree into rooted connected components with roots hanging from "forbidden" edges. The DFS-traversal forms a path with some fully traversable subtrees hanging from it. We need tree DP for size/full traversability of subtrees and for a part of the path which goes down, and then merging those <= 2 downward paths + some fully traversable subtrees.

E: The answer is the total number of submatrices — number of submatrices with sum  < K. For every left side of a submatrix, increment the right side, add violas and recompute the number of ways W to choose the top+bottom side. Remember the number of violas at every y-coordinate in a map<>, W is the sum of intervals in which they're the topmost. Small K means those intervals won't span more than K entries in the set<>, so just a few of them need to be recomputed.

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

    Thanks for your quick mini-editorial! :D

    Please, can you explain me why there is the special case in A?

    In test case S = 3 X = 3, the statement says that there are only two correct solutions ( (1,2) & (2,1) ). Why (0,3) & (3,0) are not good solutions?

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

      Read the problem statement.

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

        "Two positive integers a and b have a sum.."

        That 'positive' means greater than 0? I thougs 0 was positive too :(

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

          You learned something from math-English, then.

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

    Congrats... they all passed :D

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

    For D I implemented something like you describe, taking O(N) for each iteration of binary search, but it kept timing out on pretests (although I couldn't find a test case to make it take more than 1 second on my machine).

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

      Argh! Just realised that it isn't O(N) at all: a vertex with high degree will kill it. Somehow I neglected to test that.

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

    Hi! Could you please explain your approach to B? What about leftover production which can be used on later days? What are your fenwicks storing exactly ( prefix sum of min(ord(i), B) and a suffix sum of max(ord(i), A) ) because I don't understand how to find the answer from these. Please explain.

    I found an approach with 5 fenwicks, so I want to understand your approach, you only use 2 fenwicks :) thanks in advance

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

      Production can be used only on the day it was produced, so no leftover.

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

        Whaaaat????

        Each order requires a single thimble to be produced on precisely the specified day

        I misinterpreted it as

        Each order requires a single thimble to be delivered on precisely the specified day

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

      I committed exactly the same mistake. How did you solve the mis-interpreted question with 5 Fenwick Trees?

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

10s too slow to submit F :(

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

Solution for Div 2 C?

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

    dynamic programming on the bits. Let f(i, carry) be the solution considering the first i bits and if we have a carry (from the previous bits (0 , i - 1)).

    Now depending on the value of the ith bit of the sum and the ith bit of the xor we call the appropriate recursive calls.

    for example (assume carry is 0) if the value of the ith bit of the xor is 0, then we can put either (0, 0) or (1, 1). now if the ith bit of the sum is 0, then the first choice (0, 0) will have the solution f(i + 1, 0) and the second choice (1, 1) will have the solution f(i + 1, 1). and the rest of the cases are similar.

    Hope it helped.

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

      And till how many bits do you call f? max(number of bits in S, number of bits in X) or some constant?

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

        I did it till number of bits of x. However, it might be wrong. I think it should be till the end of the max and to check finally if we have a carry or not.

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

          Until the MSB of S is good enough. I mean, if we have some sum of 2 numbers (or 1) that have a bit bigger than the S's MSB set, it is bigger than S.

          On the other hand, checking until X's MSB doesn't guarantee correctness.

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

          Same approach Me too failed systests :( idk y

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

      Awesome approach. I couldn't solve it during the contest but your approach made things pretty clear. Since sum & xor is in the range of 10^12. We can continue till 40 bits approx.

      Attaching my link to the above approach implementation http://codeforces.net/contest/635/submission/16423712

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

    There's also an O(sqrt(N)) meet in the middle solution in which you split the number into 2 groups of ~20 bits each.

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

      This was the approach I tried during the contest. I missed the restriction about positive integers and I submitted it before the end of the contest so I did not have time to fix it.

      Dynamic programming solution is much elegant and saves a lot of time and memory resources.

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

    Make use of the fact that each integer has a unique binary representation,so this means we don't have to use DP , simply check if the binary representation of s' is a subset of ~ x, where s'=(s-(sum of 1<<position of bits set in x))/2, if s is divisible by 2. In other cases(s' is odd, or s' is not a subset of ~ x) output is 0.

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

I hope the System Test won't take forever to start.

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

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

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

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

    Your hopes have been denied.

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

      FML.

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

        Well, congratulations on the spectacular performance :)

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

          Thanks, I really didn't expect to do this well (not after yesterday's debug output fuckup).

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

Problem 627C - Package Delivery is quite similar with 241A - Old Peykan. You increased limits but solution idea is the same.

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

O(N^2) somehow passes pretests for Div2B.

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

    Link to the code?

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

    Pretests are weak. My recursion also passes div1B:

    ll count(ll s,ll x){ if(s%2!=x%2) return 0; if(s==0) return 1; if(s<x) return 0; if(s%2==1){ return 2*count(s/2,x/2); } else{ return count((s-2)/2,x/2) + count(s/2,x/2); } }

    But it is O(s+x) in worst case.

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

What is WA5 in D (DFS)?

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

The difficulty of problems was very appropriate: in all 3 contests, someone solved the second-last problem but no one solved the last problem.

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

    I would say implementation of div2 F was way easier than div2 E or my approach is wrong (might be, cause it's pretty simple and obvious).

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

D on div 1 is quite similar to this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=283

The only difference is that that one is slightly harder: B is not necessarily equal to D

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

When .o. forgets to do unsuccessful hacks......

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

I opened B's statement and thought "Ok, let's look for something shorter", then went to E which reminded me of this topic — http://codeforces.net/blog/entry/23613, which led me to this problem — http://codeforces.net/contest/364/problem/E and I spent the whole competition (well, after submitting A) trying to change some of the solutions of that problem in order to make them pass without understanding how those solutions worked :D So, yeah, I got what I deserved :D

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

Can Div1 D be solved using stack? Or something more tricky?

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

    You can use deque to maintain remained gas to get a O(m) solution instead of priority queue. but sorting is still needed.

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

    I've solved this task many times (include the first time I come up with this task by myself..)

    So the idea is: you can buy some gas, and at some point you can sell them at the price you bought it.

    • When you are spending gas, spend the cheapest one
    • When you arrive at a station, if there are gas more expensive than the one at this station, sell them all. And then buy as much as you can.
    • When you arrive destination, sell all.

    You can use an array with 2 pointers (left, right) to keep a sorted list of gas with different price and amount.

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

      Another view:

      Each cell has its travel cost (initially INF). When you visit gas station, you need to update the consequent N cells with cellcosti = min(cellcosti, stationcost). Let the starting point have 0 fuel cost.

      Of course you don't store the whole cellcost array, you store only events (add possible cost/remove cost) and sweep from left to right, taking the minimum cost on each segment. So you need a sliding window minimum (using deque). And I also used deque for events instead of 2 pointers.

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

      @cgy4ever: How can we maintain a sorted array in log(n)? Wouldn't insertion (new gas station) take O(n)?

      I was thinking a max-heap (for new station), and a min-heap (for traveling), and another simple array just to store the values. When we extract from either heap, we check from the array if value has been changed by the other heap, and update accordingly, before proceeding.

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

        "if there are gas more expensive than the one at this station, sell them all." — it means when you want to insert x, you will remove all elements larger than x first, so after that you just need append x to the back.

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

    not sure if correct

    sort all gas stations by cost

    use set<start, end> of gas for gas station and for each gas station insert values and update answer

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

    div1D can also be solved with divide and conquer. solve(l , r) denotes min cost to reach rth point from lth point if we leave with full fuel at l. find the point with minimum fuel cost in range l + 1 to r — 1 , and buy all fuel here or as much as we need to reach rth point and now add solve(l , index) + solve(index , r) to it. Code

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

At first glance, the problem 627E - Orchestra is very similar to 364E - Empty Rectangles.

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

Duh, "Orchestra" was almost the same as http://codeforces.net/contest/364/problem/E I copy pasted more or less randomly chosen solution (I chose -XraY-'s one) and adjusted it to this problem, but got TLE. After that I compared those two problems more carefully and found out that the fastest out of >80 ACs to "Empty rectangles" runs 2,5s for n<=2500 and k<=6, and here we have 2s, n<=3000, k<=10, so there's no chance that those problems follow exactly the same idea >_>. Only difference in statements is that number of forbidden cells is not larger than 3000 in Orchestra while there is no such constraint in Empty Ractangles and in Empty Rectangles there needed to be exactly k forbidden cells and here less than k (but second difference is not making Orchestra easier).

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +43 Vote: I do not like it

    My solution highly exploits the fact that n ≤ 3000.

    The main idea: Suppose the top side of the rectangle is in row i and the bottom side is in the row j > i. First iterate over all i in any order, for a fixed i iterate over j from r - 1 to i. When we have fixed i and j, we have a horizontal strip of cells, write down for each column how many 1s there are in this column in our strip into an array A. Having this array, it's easy to find how many good rectangles there are in this strip: for each non-zero item j in A we only need to know closest non-zero item to the left prev[j] of it and the first positon from[j] such that on the segment [j, from[j]] the sum of values in A is greater or equal to k.

    Now let's understand what changes when we decrease j by 1. Some values in A decrease by 1 (that's O(n) totally over all j), my idea is that there will be no more than k values of from we need to fix for each changed position j (actually, those positions are no more than k non-zero items to the left of j). I use this fact for a careful recalculation of array from.

    The main difficulty here is how to find a closest non-zero item to the left or to the right in A. I do that by using path compression technique that provides a very fast log factor. So, overall complexity after careful amortized is for all path compression and O(rnk) for all changes in arrays A and from. Overall complexity is . It has pretty easy implementation, though I spent about an hour on optimizing this solution to make it fit into TL, and still, it runs for about 1.7 sec on pretests :(

    UPD: formulas above had a mistake, I've lost the r factor in an analysis. Now it's fixed.

    UPD: 1918 msec on final tests. Damn I feel lucky :)

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

3500 signed up for Div. 2, but only 1000 solved A? Where did the other 2500 go?

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

    So that's part of why the rating change prediction plugin thing shows so much loss for me :D I did screw up royally, but -82 does seem like worse than my previous royal screwups.

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

      Hah, royal screwups :)
      I hope you haven't trademarked the idiom, cause I'll have to use it a lot in the future :)

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

        This is a real English idiom, not one I made up :D (Though I admit I did hesitate after posting it if it actually existed, but Google says yes :D )

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

    3500 signed up but I only see 1300 in the standings. Still trying to figure out where the rest went...

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

      I felt like Div2A was less easy than usual. Maybe some got discouraged.

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

        Got the same feeling. Still, can you leave a competition after it starts?

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

          Il you don't make any submission, your ranking doesn't change. But after one submission or more, it's too late...

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

            You can sumbit and not be rated if your points are <= 0

            Why do you think some people spam bad hacks and get into a negative score?

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

              In today's contest, Hedgehogy got less than -2000 points and lost 74 points. There is something that I don't get.

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

                Yeah, you're right. But I definitely saw it in some other contests. When people got negative points they got * above their name, which means they were out of the contest. Shrugs

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

          Sadly yes, if you don't submit at all you're not counted — no rating change for you, no difference for other participants. This is a good thing for people who realize after registering that they cannot come, but I don't think that's a typical problem, so I'm not sure why it's so... Maybe they don't want to discourage anyone by such a loss or something?

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

            Wow.. you can totally bail out if you realise the problems are harder than usual.

            Whilst it's only fair to let people leave the competition if they can't make it, it shouldn't really be allowed after the competitions started or after you've read the problems.

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

              What's the point? They'll keep sucking if they keep bailing out. Bail as many as you want. Nobody's loss except yours.

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

        Yeah, basically the brute force solution required a few more control structures than usual. :D (6 nested loops for the very brutest one)

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

Any hints to solve Div 2 B- Island Puzzle

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

    move 0 in both arrays in place 1 then check numbers in places 2 to n to each other

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

    Ignore zero in both arrays and then check whether they are cyclic permutation.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    1. Read the two lists of numbers.
    2. Remove the number 0 from both of them (can be done while reading)
    3. Rotate the second lists until it starts with the same number as the first list.
    4. Compare if every number in the same position of both lists are the same, if they are --> YES, else NO
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Same Idea as mine. But how is it possible that we all came up with the same solution. Is there a proof of its correctness somewhere?

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

        If we have the numbers 0 1 2 3 4 5, we can get all the possible positions of 0 when swapped with its neighbours:

        0 1 2 3 4 5

        1 0 2 3 4 5

        1 2 0 3 4 5

        1 2 3 0 4 5

        1 2 3 4 0 5

        1 2 3 4 5 0

        Here we can see that moving the 0 doesn't affect to the relative order of the other numbers and we can move the 0 to whatever position we like. Then the 0 is not a necessary data we need to keep, we can throw it away.

        We know that we can't change the relative order of the other numbers, then we only can verify that the elements are in the same order.

        I don't know any other proof of correctness.

        Hope this helps you :)

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

        if 0 is in i index, then if you move statue in i-1 index to i then now i+1 index lost its access to 0. Similarly, if you move statue in i+1 index to i then now i-1 index lost its access to 0. So, only indices adjacent to i can make a move. This means no jumping over indices, only sliding. Imagine 0 is like a tiny bubble in a bottle of liquid, tilted 90 degree.

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

    ignore 0, and check if they are rotation of each other

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

    Proof for the method is welcomed.

    Thanks in advance.

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

      if you move 0 to left n times.. 0 will be in same position but remaining array will be rotated once. so you can generate all the rotated arrays. As you cannot place any non zero number between 2 numbers. So, any other array other than rotations cant be generated. Hope thats correct and helps :)

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

      Ignoring the zero in the arrays, the first array can be transformed into the second one only by some finite number of cyclic shifts, (i.e. 2nd array is a rotation of the 1st). That ordering does not change. If 1 is followed by 2 counterclockwise (or clockwise) in the first array, it has to be the same in the second array too.

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

we are waiting for...

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

Please post photos from the onsite contest. :D

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

I'm looking at my code for Preorder Test (Div1 edition task E) for like an hour already and can't understand why it gets TLE#8.

Can any of you guys help me find the bug? I don't think 8 million dfs calls can cause TLE in C++ when TL is 7 seconds.

http://ideone.com/d46vuQ

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

    Your algorithm becomes quadratic if you have a case where one vertex is connected directly to all of the remaining ones.

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

Pending System Testing is the most annoying sentence I've read in a while.

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

    Notice this: " UPD: Due to onsite awards presentation, we will hold final system testing until around one hour after the end of the contest. " So you don't lose time if you have to do something :)

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

      If I had something else to do I wouldn't be so on edge :D

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

      Hum, I think it's been more than an hour already...

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

    I've always wondered: What is the purpose of this phase?

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

http://pastebin.com/dqJRLfCU http://pastebin.com/pfxyMvFQ Task D Div2.

Can anyone explain me, why the first one got WA4 but the second one got AC. It`s not Long Long problems for sure, because max value in this task is about 1e9.

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

    Typically, it can produce up to a thimbles a day. However, some of the machinery is defective, so it can currently only produce b thimbles each day.

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

      so? in my first code it is clear. Only i had changed is first query.

      From
      update(1, 0, n - 1, d - 1, get(1, 0, n - 1, d - 1, d - 1) + min(a, q));

      to update(1, 0, n - 1, d - 1, min(TTT[d - 1], a * 1LL));

      Where TTT is a previous values.

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

        get(1, 0, n — 1, d — 1, d — 1) + min(a, q) can exceed a.

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

          wow, really. Thank you, I was so dumb, lost 20 minutes, trying to fix it :c

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

the contest ended seconds before I got to send my code for problem Div2 E :( If it was submitted and passed system test I might have ended up in top 20 for the first time :3

anyway, If this code gets accepted later I'm not gonna forgive my slow internet connection >:(

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

    system test finished and I still can't send my code :D

    this is feeling like forever :(

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

    The same situation with Div2 C. I am waiting for check the last solution. Will it able only after changing of ratings?

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

    Well :D, for anyone following this: I just sent my code for E and I got WA on test 10...

    It's both a relief and a pain in the butt :3 ...

    I really don't know how to feel about this contest anymore :\

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

      Be happy you learned stuff.

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

        Yes! I did learn to always open submit code page before reading the problem :D ..

        It was a nice contest anyway :) I'm happy I participated

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

      be happy for you had an idea ... i aspire to the day i read a problem like problem E and think of something ... i guess this requires time and hard work :)

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

It seems like we have to wait all night again.

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

is an editorial going to be published ?

and could anybody kindly give a hint on C div2 ?

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

    For C, focus on each bit of the numbers.

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

      i got the bits part ... but does a backtracking solution pass?

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

Oh no!! If I registered, I'd be under 300 rank and I'd be blue right now ;_;

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

DIV2 C can be easily solved using identity a+b=a^b +((a&b)<<1)

from above identity,value of a&b=(a+b-(a^b))/2

now using a^b and a&b,we can count ordered pair easily...

for each bit in a^b and a&b,we have 4 possibilities

(a^b) : (a&b)

1 : 1 (not possible)

1 : 0 (2 cases--> (ai=0,bi=1) or (ai=1,bi=0))

0 : 1 (1 case--> (ai=1,bi=1))

0 : 0 (1 case--> (ai=0,bi=0))

code: 16412578

complexity: O(log(x))

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

I'm in trouble when submitting problem Div2C. In my computer it gives the right answer for the first testcase, but when I submit it, it gives 0 as result, what is wrong. I've tried with Ideone an it gives the same as in my computer. Is anyone having the same problem as me? It's due to any particularity of the CF compiler that I'm not taking care in my code?

https://ideone.com/csKtVP

http://codeforces.net/contest/635/submission/16418542

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

    You access an element of the vx vector that does not exist, because it can have size less than nbits.

    When different compilers give different results, it's usually the programmer's fault for doing something that is not allowed.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

Could div2 C be solved with the following logic?

Now there is no point in finishing my question, if the comment is hidden :)

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

Can someone please tell why my solution fails? 16414129 I wrote y = Xor sum xor x Then replaced in the sum equation and then tried dp. Similar solution passes but mine fails. I cant get the bug!:(

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

    You are terminating your loop too early, so you fail when sum < xor. Just let i run till 60. Also your dp array is too small.

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

      Thank you I deserved that WA :(. Although i was happy to solve a good question

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

Could someone help me find an error in my submission for Div 1 C -http://codeforces.net/contest/634/submission/16414568

My logic is that I store the values of the elements in two subtrees, only if they are smaller than a and b respectively. I also keep a count of all active elements (<=a/b) in the subtree as well. I can split the query into two halves and query the correct tree (b one before repairs and a one after repairs.) Could someone please tell me what is my logic/implementation error?

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

When will editorial be published?

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

When editorials will be published ?? Waiting....

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

If anyone wants to know the solution to div 2 C or finals A please have a look at my blogspot.

http://iamayushanand.blogspot.in

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

As the editorials haven't been published yet, here is my greedy approach for problem E from Div 2(635E — Package Delivery)

Let us see for all i from 0 to m if it possible to reach some location such that X[i] ≤ location. Now, to travel the distance between the previous location and the new location, we will have to choose one of the P[i] such that they lie in range [location - n, location]. So let us keep a set of all those locations from which we can start prioritising by lower P[i] and greater X[i](this would also manage duplicates). Keep track of the starting pointer at each i, and for the next i, just iterate it until you reach the lower_bound on that X[i]-n. This is O(nlgn) because each element may be inserted in the set at most once.

Now, this is slightly tricky and I'm not formally sure why it works(intuition rules :P ) but while we are removing these elements, we simply need to check if the element being removed is the best element, and if so, try to jump to X[j]+nth location(where j is that element). This works because for the X[j]+nth location the current set should correspond to the entire range that we would need to check otherwise as well. Now if we don't reach the X[i]th location after all this work, it means that we need to use some other value in the set to jump to the X[i]th location. Implementation of this is not so tough, just checking a few boundary cases is slightly tedious. This is my accepted submission: 16432717

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

8VC has sent me some photos from the Final. I'm glad to see familiar faces. Share them with you:

https://get.google.com/albumarchive/pwa/114907919772955385569/20168VCVentureCupFinal?authuser=0&authkey=Gv1sRgCIfk3s78m9T6sgE&feat=directlink

→ Reply