Codeforces Round 380 Div.1+Div.2 (and Technocup 2017 — Elimination Round 2)
By MikeMirzayanov, history, 8 years ago, translation, In English

Hello, my dear lovers of algorithms and data structures.

Codeforces Round 380 will start on November 20 (Sunday), 09:05 (UTC). It will be based on Technocup 2017 Elimination Round 2. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2017.

Many thanks to KAN, GlebsHP, fcspartakm, Levshunovma. Hope to extend the list soon because of testers. Also some problem ideas are mine.

I hope you will like problems. It will be 6 problems in each division.

Good luck and bugless code

Scoring:

  • TK Elim 2 and Div 2: 500-1000-1750-1750-2000-2500
  • Div 1: 750-750-1000-1500-2000-2500

UPD 1: Here are our winners!

Top-5 in the Technocup stage:

  1. sslotin
  2. Arthur
  3. hloya_ygrt
  4. asokol
  5. Denisson

Top-5 in Div.1:

  1. riadwaw
  2. MrDindows
  3. Belonogov
  4. dreamoon_love_AA
  5. LHiC

Top-5 in Div.2:

  1. Ralsei
  2. NotDeep94
  3. ecvlco397
  4. kongroo
  5. meeeep
  • Vote: I like it
  • +227
  • Vote: I do not like it

Comments Comments (167)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +156 Vote: I do not like it

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

And if I am not a Russian-speaking high-school student, I should register in Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) ???

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

    Yes, the registration will be open soon.

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

      Great, now I can happily miss another boring university day :D

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

        Yep, it's usually boring on Sundays in university

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

          Believe me, It's always boring :p

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

          Sunday is not weekend in all countries :)

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

          Now i am saying, boring university is better than negative rating change :p

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

Does the Division 2 contest get all the same problems as the actual Technocup round or are there going to be unique problems as well?

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

    Division 2 will contain the same set of problems as Technocup Round. Division 1 will contain harder problems.

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

The one didn't write "thank ... and Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon" in contest description.

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

The midterm exams start tomorrow, which gives me only two options :(( :

A- Participate in the contest and let the exams go to hell.

B- Let the exams go to hell and participate in the contest.

What do you people think?

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

    Participate in the contest :)

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

    Go to the exam :) If you don't participate on a div2, nothing will happen, You can do it virtual contest :) But You'll not have a virtual xm or something like that!

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

    i would suggest to go for A, because contest comes first :p

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

Will the problems be in english as well?

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

Probably got my birthday gift from Codeforces. Div1 Contest on my birthday

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

If i will register in Technocup 2017 — Elimination Round 2, would I have rating change or not? The same question about Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 — Elimination Round 2). Will I participate in technocup olymp?

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

    If you register for Technocup 2017 — Elimination Round 2, you will get both rating change and participation, if you register for Codeforces round 380, you will get just the rating change.

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

      whaaaaat???!!! Besides the rating change , What can I get if I participate in Technocup 2017 and get a high rank :D

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

The midterm exams start tomorrow, which gives me only two options :(( :

A- Participate in the contest and let the exams go to hell.

B- Let the exams go to hell and participate in the contest.

What do you people think?

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

Will division 2 in English? :/ when I registered, I saw Russian sentence :/ so,if the contest will be taken in English please make the reg. page in English.

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

How hard will it be compared to a div 2 round ( like round #379 )? I wanna know if i can solve anything or not

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

Is it rated?

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

The System testing should start now because it takes long time

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

Is Div 1 rated?

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

i've waited this round for 2 weeks, wish it will be an excellent round LOL

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

great :)
what a hurry contest where just ended one Regional :)
by the way All the best to all

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

It's "TLE" when I used "cin" for Problem B(div2)! Sad ~,~!

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

Can anyone hack any submission during contest???

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

Strongest pretests in DIV1 — rare hacks :(

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

    t < s in A brought me down by 100+ ranks already :D

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

How to solve Div 2 D and E?

D seemed like binary search to me but couldn't get anything concrete in time. :/

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

    I solved D using greedy and C using binary search, dunno about E.

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

      How?

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

        In C use binary search to find the least powerful engine that will fit into the time. In D find the maximum number of ships that can be placed in the board. The answer is the maximum number of ships minus real number of ships + 1. Then just shoot so that you remove a possible ship with each shot.

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

          It's funny how C problems are harder to pass than D problems now. :D

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

            They had the same score. But yeah, this D was easier to code than the A imo lol.

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

    Find all the empty segments, and the max. number of ships placeable in the field is sum of (length of segment i / b). Let the number be x, and you need to shoot at least x-b+1 times to ensure a hit. Then just shoot at places where the number of placeable ships will decrease for a sure.

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

    D — greedy — one should take every kth consecutive zero if a=1, dont take last a-1 such places.
    E — consider height of tree to be 1..n-1, calculate answer as function of distinct values not present and values lying outside, take min overall.

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

Worse div1 contest ever!

no interesting problem

no hack

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

If I don't fail system test, this round will be my best round ever.
Good luck to me.
UPDATE: Failed E T T

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

    Still top 100 so nice job anyways!

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -136 Vote: I do not like it

OMG !!! I hate all problems where arrays length is not standard. For example why in problem C array G is '2e5' ???? I had -200 for this mistake. HATE NOT STANDARD ARRAYS LENGTH PROBLEM.

UPD #NOPROBLEMWITHNOTSTANDARTARRAYSLENGTH

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

    What exactly do you consider 'standard array length'? You have different constraints in each problem, it literally takes a second to look at them. Don't whine.

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

      I'm saying that there's no big difference in length 1e5 and 2e5. So I can't understand why they took 2e5?

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

How to solve Div1 D? I used DP[left][right][k] and it passed pretests with 1.7 sec, but it doesn't seem to be a correct solution..

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

    You may notice, that k <= 100 and -100 <= right - left <= 100

    UPD: where 100 is surely = O(sqrt(n))

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

      So, will pass?

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

        I don't think so. But with understanding of this constraints it'll be O(n2)

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

      Ah, so the number of states will be less than 4000 * 200 * 100 = 80000000.. Thx for explaining!

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

        In fact, this can be done in O(N^2) memory if you just memoise using a map. This is because the number of papers Igor and Zhenya have taken in total differs by at most O(sqrt(N)) (To increase the difference after they have made an equal number of moves, you have to increase k, and k is O(sqrt(N))). So this actually runs in O(N)*O(sqrt(N))^2= O(N^2). Memoisation ensures that you only use memory proportional to number of states visited.

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

        I read your solution submitted during the contest, is there any trick on implementing? I did almost the same thing as in your code but just got TLE

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

          1. I always add "fflush(stdout); _Exit(0);" in the end of the main() function. When I use many maps or sets or the elements are too many, it reduces the running time about a few hundred milliseconds.

          2. Consider branching like this:

          if (k <= mem) { ... } else { ... }

          instead of

          if (k <= rem) { ... } if (k + 1 <= rem)

          because it is unnecessary to check "k + 1 <= rem".

          I submitted your solution with these two micro optimizations, and it was accepted. 22377001

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

            Wow! That works! Thank you!!!

            It seems that I have to be very careful with the constants of solutions when their complexity is near the boundary.

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

Looks like O(n*k) solutions passed pretests in div2 C. I should have hacked...

I wonder how many of these were submited.

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

Lets hope system testing isn't late today?

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

    Now it's running!

    UPD: uh-oh... It seems that queue is stopped?!

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

How to avoid TLE in DIV2 B? Tried ios.. and scanf but couldn't pass.

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

    Use prefix sums.

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

      I used prefis sums with cin and got TLE, that's really annoying

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

        prefix sums for Div2 B?

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

          Yes, so you can know if there is anything on the right,left, up or down

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

            Oh. I used a different method.I was able to get AC using normal cin. You can refer to my way here:
            (Ignore the functions before main() ) 22349678

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

_how can get the solution or tutorial ?

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

Div1 systest paused???

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

    They noticed that systest today is a little bit fast, so they paused it a bit because CF traditions says it should be slow.

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

    I think so.

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

    They started div2 testing. Looks like they can't do both at the same time...

    → Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it -12 Vote: I do not like it

.

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

Honestly I don't see any point setting TL = 1s for Div 1 A so that log(2e9) or slightly slow binary search can't pass.

Edit: My apology. This solution actually fails because of integer overflow when computing (lo + hi) / 2 as pointed out by P_Nyagolov.

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

    Same thing.

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

      My apology. Thank you for pointing out my mistake.

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

    It is not because of slow binsearch, but because of hanging binsearch. They have overflow or other mistakes in implementation.

    Even solution with extra internal binary search (e.g. O(n·log2n)) passes the tests and fits in half of TL.

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

Feels bad when failing 3 contests in two days. :'(

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

My wrong solution 22349543 passed systest, but it will fail on this test:

1 1 10 18
5 6
5

Correct output: 5
My output: -1

I just noticed it just after contest end that I forgot to handle that case, to fix that I should add else x-=V[n]*(llu)h-S[h-1]; on 34th line.

Edit: Wow so fast rating change =)

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

my solution for problem B(div 2) in pyth2 is giving TLE and same solution in pypy2 is accepted,,

poor testing in python

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

What is the test that does this? :)

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

Nice contest !

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

I got TLE on systest on the same test I got accepted in pretests with 920 ms. I used prefix sums on line and columns.

this

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

Mysterious TL in problem A for div 1, test 9

Why is there TL on test 9 in my this solution? http://mirror.codeforces.com/contest/737/submission/22357999 It has return code -1, but still even checker should print RE, I don't understand why is it so. Maybe some of you know?

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

I had TLE using cin and cout, but after I used scanf I got AC.

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

    Welcome to CodeForces buddy.

    If you insist on using cin, cout make sure you are using c+14 and use ios::sync_with_stdio(false) .

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

Potato quality pretests making my tomato quality codes to fail since 2 onion type of contests.

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

Could anyone help me to find my mistake in problem C ?

http://mirror.codeforces.com/contest/737/submission/22349523

I am very eager to know...

UPD : FOUND

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

22356216 What is the problem a***b != a***b ?

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

The participation was rather low today, and I assume the reason for this a slightly more difficult problem A(div 2).

People have come to the contest and decided against submitting I presume. Wouldn't it be great to have a topcoder like system, where u are on the leaderboard if u open the contest ?

Its much more difficult to get a positive rating change with such low participation.

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

    That could be the case for div2; however, for div1 main reason of low participation seems to be a lot of other contests clashing with CF round — OpenCup stage, bunch of regionals (SWERC, CERC, NWERC); also some teams are on their road home from MIPT training camp.

    Issue you mentioned has been discussed a lot of times already, and I don't think there are going to be some changes on it in near future. This system itself is really vulnerable (simply register another account to read problems I guess). It needs a lot of harsh actions — like checking IP addresses of contestants etc. Nowadays people aren't even banned for having multiple accounts or competing in teams using single account (when one account sometimes makes submissions from 2 or 3 cities during a contest). I'm personally fine with it in case we have to choose between platform improvement or having more contests — and improving "fair play" system :) I'm sure that I'm not at the top not because of cheaters but because of other contestants being much better than me :)

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

Is the rating system broken?
I was ranked 995 and my rating changed from 1448->1446(-2). Edit:Nvm, I guess it's due to low participation.

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

22356216 What is the problem a***b != a***b ?

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

    you print something strange at the end! I think it's '/n';

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

      It's actually '/0', he has array out of bounds.

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

Didn't pass C because I didn't sort the array in which I binary searched. How the hell did it even work?

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

    I was wondering why my solution to (div2)B wasn't working until I noticed that I'd erased the part which was reading the data and that I'd been processing uninitialized 2d array. :D

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

I am very heated up right now(actually, not really) I was solving 729A - Interview with Oleg. I thought I had did answer and submitted my code, and I got a "wrong answer". I looked at the test cases, and tried it on my program, but in my program, it printed the right answer.

include <stdio.h>

char d[101]; int N; int f(int n) { for (int i = n; i < N; i += 2) { if (d[i] == 'g'&&d[i + 1] == 'o') continue; else return i; } } void fill(int a, int b) { int cnt = 1; for (int i = a; i < b; i++) { if (cnt > 3) d[i] = 0; else d[i] = '*'; cnt++; } return; } int main() { scanf("%d", &N); scanf("%s", d); for (int i = 0; i < N — 2; i++) { if (d[i] == 'o' && d[i + 1] == 'g' && d[i + 2] == 'o') fill(i, f(i + 3)); } for (int i = 0; i < N; i++) { if (d[i] == 0) continue; else printf("%c", d[i]); } } this is the code. I've got stuck on test case 2. What is wrong with it???

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

    f doesn't return anything if it goes on until the end of the string

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

    Hi, it's more convenient to post your whole submission. Let's say: 22363876. Also, as tfg has noted, your function f doesn't return any number if the control gets out of for loop without ever evaluating else clause. The behaviour of function f is therefore probably undefined and it just so happens that it returns correct value on your (and mine) computer, but not on the OJ. One way to modify this could be for example:

    Code

    That being said, it might not be the most beautiful solution to your problem. By the way, if you compile your program with "-Wall" flag, it gives you a warning:

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

      thank you very much :D, I'm new here, so I didn't know how to ask... Sorry

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

Hey, how to solve Div1B?

Thanks.

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

    We have to change as few zeroes as possible to ones so that it is impossible to place a ships on the zeroes. Calculate for the initial configuration how many ships can be placed. After that, greedily remove the possibility of placing a ship, whenever there are b consecutive zeroes (i.e. change the b-th consecutive zero to one). Do it until fewer than a ships can be placed.

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

Any suggestions for div2E?
I used this idea: consider it to be a tree, so each node has it’s depth (number of superiors) If the tree has it’s total depth K, then there should be all integers in range 0 – K and not any deeper than K.
So, for each K in range 1 — N I check how many changes I need to make in order to make the tree with depth equal to K. Any idea why it wouldn’t work?
Here is the link of my try.

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

    That's the right idea.

    You check how many changes you need to make to create a tree with total depth from 1<=K<=N-1 (a tree with only a 0 has depth 0). All numbers from 1 to K must be present (there will be only one 0) so to do that you check if you can use the numbers > K to fill the gaps since you will have to change them anyway (to K or some other number lesse than K). If it still isn't enough, you will have to use the numbers from 1 to K to fill any missing gaps. If you consider the numbers that are 0 and aren't the chief as N, you will get the right answer since they are wrong and you need to change them.

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

      Thanks!
      My wrong was that I used only those who had 0 depth to fill the gaps, didn't use those which are > K

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

When will be editorial?

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

When will the editorial published? I couldn't figure out the solution of C. Can anyone explain it please.

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

    Sort the cars by their volume of fuel and use binary search to find the first car that can arrive to the destination in time, lets say it's the k-th car. Then just itterate through all cars from k to n and pick the one which costs the least.

    My code. Sorry but it's pretty ugly :D

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

      Thanks a lot i got it.

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

      Rudy1444

      Could u explain / prove these lines of code ?

      d2=a[p].first-d;

      d1=d-d2;

      time+=(2*d1+d2);

      thanks in advance !

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

        D1 is the distance he will travel normally and D2 is the distance he will travel accelarated. So we have D1+D2=D, where D is the total distance. Also he uses 1 l/km in the first case and 2 l/km in the second so D1+2*D2=V, where V is the volume of fuel. So we have D2=V-D, D1=D-D2. The we just find the time. I'll leave proving the time formula as homework :D

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

    We can binary search the least fuel f we need to get to the destination in time. And the answer is the cheapest car whose fuel limit is larger than or equal to f. Now the question is: how to check if we can get to the destination in time with a certain fuel limit.

    Denote the distance between a pair of adjacent gas stations as d, the distance we need to drive in accelerate mode as a, the distance we need to drive in normal mode as b, the fuel limit as v, and the shortest time we need to get to the destination as t.

    In order to get to the destination as fast as possible, we should use as much fuel as we can.

    If 2d ≤ v we can always drive in accelerate mode, i.e. t += d;. If d > v then we don't have enough fuel even if we always drive in normal mode, so return false; in your check function.

    Now we only need to consider the case when d ≤ v < 2d. Because we need to use as much fuel, so we have the following two equations:

    2a + b = v and a + b = d.

    Solve them, and we get a = v - d and b = 2d - v, i.e. t += (v-d) + 2*(2*d-v);

    You can check my code for more details. Remember to use long long type or set the upper limit of the binary search to a little bit more than 1e9. I set the upper limit to 2e9 during the contest and it overflows :(

    My code: 22361702

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

I try to use an unordered_map to solve Div1.D during the contest but got TLE on pretest 9. After the contest I checked some successful submissions made by others and found that they also use unordered_maps. Are there any tricks when using unordered_map to speed it up?

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

    Not sure if this is the case here, but sometimes they have testcases that specifically catch unordered_maps. I think it's stupid, but it's happened in the past that you need to use the normal map (which is a bst) to pass the test-cases which are designed to specifically beat unordered_maps.

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

When will the editorial be published? Or is it published already? The last round of technocup didn't link it's editorial to the problem page so I am concerned that the same thing might happen again.

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

    Looking for help in solving div1E.

    I have drafted the minimum time should be max single machine/child play time, and I should rent second machines greedily by the length of play time queue. However, I have no idea how I should cope with providing a valid schedule.

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

mfw practicing a day after the contest was held

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

Free Fuel IN C WoW!

→ Reply