When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

GlebsHP's blog

By GlebsHP, history, 8 years ago, translation, In English

Hello everybody!

Today the second regular rated round based on problems of VK Cup 2016 Final Round will take place. Of course, we have created some more easy problems to fulfill the requirements of different skill levels and make the contest interesting for everyone.

The commentators of the previous announcement pointed out that I forgot to thank MikeMirzayanov for making Codeforces and Polygon so awesome. I was wrong, Mike, that's really cool :)

Scoring distribution will be published right before the start of the contest. We wish you good luck and beautiful solutions!

UPD1. Scoring for div2: 500-750-1000-1500-2000-2500. Scoring for div1: 500-1000-1500-2250-3000.

UPD2. The contest is over, congratulations to winners!

Div1:

  1. ainta

  2. W4yneb0t

  3. Petr

  4. muratt

  5. kcm1700

  6. Vercingetorix

  7. Tinsane

  8. Reyna

  9. aid

  10. zemen

Div2:

  1. MinamiKotori

  2. Ancient_mage

  3. WhatTheFua

  4. Yanba

  5. macieck9

  6. OMRailgun

  7. radoslav11

  8. zhsh

  9. skywalkert

  10. abgnwl

UPD3. I sincerely apologize for the delay with problem analysis. I was out of town for a vacation. Here it is.

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

| Write comment?
»
8 years ago, # |
  Vote: I like it -89 Vote: I do not like it

You also forgot to tell the main character of the problems.

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

don't forget to add codes on editorial as previous round.

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

    LOL it should've been

    DONT FORGET TO WRITE AN EDITORIAL

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

Where are you tourist? :(

»
8 years ago, # |
  Vote: I like it -28 Vote: I do not like it

how many tasks in this problemset??!!

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

petr now

»
8 years ago, # |
Rev. 3   Vote: I like it -33 Vote: I do not like it

want another Christmas tree!!

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

Is tourist travelling?-_^

»
8 years ago, # |
  Vote: I like it -37 Vote: I do not like it

New king of the iron throne of codeforces is Petr now :). tourist is busy in westores and hoping to see him to fight for the iron throne of codeforces again :P

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

    You watch too much game of thrones.

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

      what's wrong in that?? It is the most amazing tv series so far i have seen. I suggest u must also watch to get something from nothing ;)

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

        Btw, i've watched every single episode of this show, But it didn't improve my coding skills at all. ..hmm weird, isn't it?

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

          I had never said watched it at the stack of your coding. And all the time coding is impossible even for tourist , petr too.. When i m tired and for refreshment i watched to gain my momentum again. So it helps me to back to coding..That's how it helps :p

»
8 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

I'm Really surprised :D

I hope I'll be Specialist :))

->-> Thanks A lot <-<-

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

Guess it will be a colorful contest ;). Good luck everyone :)

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

what if mike Participated in one contest ? .. won't be great contest :p !?

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

Wish good-luck to all. Happy Coding :)

»
8 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Game of codeforces throne likely to be unseen today as neither tourist nor Petr have registered so far! Can TooSimpIe make it happening today?

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

Scoring distribution?

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

score distribution right before the start wow, they really meant right before the start.

»
8 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Tired of pokemon commercials.

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

Seems like I can't concentrate on the contest with police helicopters hovering around...

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

    police helicpters?

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

    What did you do?

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

      Live in Munich and work near OEZ

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

        The shooting was reported about an hour ago, But you commented about 90 minutes ago, wtf? Are you involved in this? :/

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

          Because police helicopters were there much earlier than any reports. And my colleague who left work a little bit earlier reported hearing shots (and hidden in nearby home)

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

    I also couldn't concentrate on all past 30-50 contests which I participated with missiles falling around me.

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

      Said like a boss :D

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

      You deserve a special competitive medal, dude. I was really surprised with your performance in the last ACPC contest when you became second on the Arab region alone because your teammates couldn't get visa for Egypt. You live in the most dangerous city in the world where you are not sure how your tomorrow is going to be. Go on and keep competing, you are a wonderful example and inspired a lot of people! May Allah keep you all safe.

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

      You forget about electricity shortage :D .

»
8 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Edit: It's too late to delete this, so I'm sorry for taking up some unnecessary space. Basically I made an incorrect assumption that I'm not sure is legal to post here during the contest.

Is anyone thinking the sample test case #2 for D is incorrect possibly?

Here is my understanding for the second sample test:

  • students at 0 bus at 0 at time 0, 1 person gets on bus 2 walking
  • students at 3 bus at 6 at time 3, 1 person on bus arrives at end 2 still walking
  • students at 4 bus at 4 at time 4, 1 person gets on bus 1 walking
  • students at 5, bus at 6 at time 5, 1 person on bus arrives at end 1 still walking

this is already more than the answer the sample case gave.

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

    I misunderstood the problem in the same way.

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

    That's how I understood it as well. Maybe we're just thinking about it wrong? But that's the only way I can see it.

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

    I think the return of the bus can be neglected.

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

    Bus can go non-integer amount of time.

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

    I still don't understand how you get that low number. The lowest I could get is:
     +   +   = 3 + 1.5 + 0.75 = 5.25

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

      I thought same at first.

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

        Same here.So I left it and went for E. But was too slow.

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

        its easy ... SPOILER (HINT) ahead . . HINT : all of them (all n) and the bus will reach destination at the same time ...think about this..

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

    Yes, I also thought so. In fact, according to that, the time only dependes on the last guy and there are some inequalities with the others. It was so weird :c

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

    Students can get off the bus at any point. You are assuming that students gets off the bus only at the end.

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

      I strongly believe that it should be mentioned explicitly to avoid those confusions. But, I understand that it is part of the contest.

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

      So how about the bus take a student 3 unit far everytime, shouldn't it take 4.5 time ?

      t x1 x2 x3
      0 0  0  0
      
      // take student 1
      t   x1 x2  x3
      1.5 3  1.5 1.5
      
      // take student 2
      t x1  x2  x3
      3 4.5 4.5 3
      
      // take student 3
      t   x1 x2 x3
      4.5 6  6  6
      
    • »
      »
      »
      8 years ago, # ^ |
      Rev. 10   Vote: I like it +13 Vote: I do not like it
      • students at 0,0,0 bus at 0 at time 0, 1 person gets on bus 2 walking FOR 1.28s
      • students at 1.28,1.28,2.56 bus at 2.56 at time 1.28, bus goes backwards FOR 0.42s
      • students at 1.70,1.70,2.98 bus at 1.70 at time 1.70, 1 person gets on bus 2 walking FOR 1.28s
      • students at 2.98,4.26,4.26 bus at 4.26 at time 2.98, bus goes backwards FOR 0.42s
      • students at 3.40,4.68,4.68 bus at 3.40 at time 3.40, 1 person gets on bus 2 walking FOR 1.28s
      • students at 6,6,6 bus at 6 at time 4.68.
      • (Calculation is not exact, but I think it wouldn't be necessary)
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, and here I thought "as well as the reversal of the bus ... can be neglected." indicate that it doesn't take any time for the bus to return, there go my first hour into the contest =.=

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

          I spend 1:00 too...(And got 150 points because of 10^-6... :( )

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

          What is it supposed to mean then? "the reversal of the bus ... can be neglected." made me think it took no time for the bus to return as well.

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

            It means that after the bus moves some distance from left to right, it can turn around and start moving from right to left in zero time. The time taken to turn around is zero.

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

        You can do it by using binary search on time. You know the optimal way is to make all students arrive on the same time. So, If time is set, you can calculate the 1.28s and 0.42s in my post when the time is set in 4.68s.

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

Could you please include an explanation for Div.2 D second example?

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

    When the bus takes some students (or maybe only 1 student) it will be more profitable if it doesn't take them to the final. Think on this a little bit and you will get the second example.

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

      I still don't get how I decide where to leave each student then. I thought about binary search but wasn't sure on what to apply it / conditions.

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

        Ok see if the bus takes some student directly to the final then every peace of time after that these student will not be doing anything they will just wait on the final, but if the bus take them some distance between the final they will walk during the transportation of the other students and that will reduce the time.

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

          Ok, I drop them before the final, but how do I know how much before the final? As in, at what position to drop them?

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

            Wait for analysis.

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

            let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.

            I thought of this logic but wasn't able to implement.

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

              This idea is indeed correct. It implies that all persons need to be carried the same distance d. The bus then makes s = ceil(n/k) trips from start to end. The total distance travelled by bus while carrying is then d*s, total distance in reverse is d*s - l (since we ended at distance l from the origin). Total time is then T = (2*d*s - l) / v2.

              Now lets take a look at a passenger. It is carried by bus for d meters, and walks distance of l - d meters. Total time is T = (l-d)/v1 + d/v2.

              We have two equations with unknowns T and d, we solve for T which has exactly one solution (provided that v2 > v1) and voila, we have a O(1) solution.

              I would say it is not particularly easy for a Div1A problem.

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

    It's not productively always go to end of way by bus.

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

      Can you explain more? I figured out this has to be the case but couldn't use it to solve the problem. :/

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

Good contest with good problems! Hopefully everyone did well and learned a lot today. :)

»
8 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Could Div 2 E be solved by keeping count of number of childrens if a subtree that are in the 2*k vertex list. And then counting how many times an edge u-v would be used depending on something like min(count[v], unpairedLeft — count[v])?

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

    Do you mean problem E?

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

      Yes sorry

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

      Any ideas about this solution by ainta? It pairs university i with university i+k on the Euler tour.

      It makes sense intuitively, but why is this correct?

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

    can you elaborate your approach. ?

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

      I tried to explain it better here. That unpairedLeft should have been 2*k only.

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

        Can you explain the correctness ? What if that particular edge isn't included in the 'best' solution ? Like 2 nodes in the subtree of v pair among themselves ?

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

          This was the same reason why i couldn't submit this during the contest. However thinking now, lets suppose that we have choice to go through the edge u-v or pair 2 vertex in subtree of v (name them as a and b).

          Assume we pair a and b directly. Distance b/w a and b would be depth[a] + depth[b] — 2*depth[lca(a, b)]. Notice lca(a, b) is always in subtree of v, so we can reduce the subtracted term 2*depth[lca(a, b)] to 2*depth[v] if we consider using the edge u-v and also depth[v] <= depth[lca(a,b)] Hence choosing the edge u-v will always maximize the answer

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

            To what are you comparing depth[a] + depth[b] — 2*depth[lca(a,b)] ??

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

              If we pair a and b, addition to answer would be depth[a] + depth[b] — 2*depth[lca(a,b)]

              However if we don't pair them directly, but pair each of them to other vertex on other side of u, then addition to answer would atleast be depth[a] + depth[b] — 2*depth[v] + 2 (the 2 for edge u-v)

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

Many thanks to GlebsHP for a nice round.

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

My code fails for pretest 11 for problem C .ANY idea? http://codeforces.com/contest/701/submission/19344527

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

    I failed the same test, I am very curious. Seemed like an easy problem

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

    isn't it "baacdabc"?

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

    I found a counterexample for mine.

    6
    abcaab
    

    My solution says 4 but correct solution is 3.

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

    Your code finds some interval, not necessarily the shortest one. Consider an example: 8 abcaabbc Your code will first move l from 0 to 4, leaving r=7, and then stop on "abbc" getting 4 whereas the returned value should be 3 (the first three letters "abc").

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

Beautiful Div1-B. The problem seem impossible at first, but after you switch your point of view (from vertex to edge), it become very easy.

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

    would you mind explaining a little bit why?

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

      For each edge, we want to count how many time it is used in the maximal sum, and that number equal the min of university count for the subtree from each vertex of that edge.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Because there is no hack in Div2-B, can we consider Div2-B's pretest is system tests?

UDP: I know the answer now. The author may add some more tests.

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

Implemented a solution for Div2-D using ternary search optimization, really nice problem, unfortunately my solution works but it is too slow i didn't even submit it (a lot of recursive calls going on). Curious to see what the real solution is :D

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

    A O(1) mathematical formula exists.

    T = el / (ev1 + v2 - v1)

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

      Can you explain your formula?

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

        Let us try to make all people reach the end at the same time. So every person has to travel by bus(at most once, as given in statement) by the same amount of time.

        So, let distance travelled by every person in bus be P. If bus picks up some people at point A and they disembark at point B, then it needs to travel (v2 - v1) / (v2 + v1) * P(let this be equal to Y) back to get to other left people, because they would have travelled some distance on foot with speed v1.

        Let Z denote the number of trips bus has to make, it is equal to ceil(n / k). Therefore we have a relation, bus goes forward Z times, and goes back by the amount Y, Z - 1 times. Add these up, and they should equal L.

        That is, Z * P - (Z - 1) * Y = L. So we can find P now. Once we know P, we can find the answer easily.

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

          Could you, please, explain Y = P  ×  a bit more?
          Why do you divide by v2 + v1?

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

            Take a paper and pencil, draw a line segment AB of length P. Now we will imagine that bus goes from A to B, leaves children at B and then returns and meets other children who started from A at some point C on the line segment.

            Time at which they both meet will be equal. So equate time( = distance travelled/ speed ) of both and you will get the formula.

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

            Time for bus to travel from A to B and return back to meet students who travel on foot (at point C) is

            Time for bus to travel from A to B is

            Hence, time for bus to return from B to C is , which equals to .

            Therefore, DistanceBC  =  t * v2  =   * v2  = 

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

          I understood everything before this equation Z * P - (Z - 1) * Y = L. How is the difference(or sum, since its written sum above) equal to L?

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

            Z = ceil(N / K).

            As everyone reaches the end at the same time, we have to make exactly Z trips in the forward direction. Naturally, when the bus goes forward the last time, it should reach the end point with all children and it won't go back.

            Therefore trips that bus makes going back is Z - 1. Therefore, bus goes Z times forward and Z - 1 times back. We have to subtract them and it should equal L. Try drawing it on paper, by making exactly ceil(N / K) trips forward and ceil(N / K) - 1 trips back.

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

      a simple mathematical formula:d = [(n-1)/k]+1 ans=l/v2*((d*2.0-1.0)*v2+v1)/(v2+(d*2.0-1.0)*v1);

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

Isn't div 2 D binary search on time ? But can anyone layout the conditions ? Same as div 1 A.

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

    I was thinking that you should drop them off at a point b such that the time remaining after you drop them off multiplied by the walking speed of kids is equal to the remaining length.

    http://codeforces.com/contest/701/submission/19348156

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

      Yes. I solved it like that by fixing time using binary search.

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

      Div2D/Div1A: Can anyone explain what is wrong with this approach?

      2 groups of walkers, front and back. In the beginning all pupils are in the back group. Then the bus picks k pupils and moves them to x distance from the goal (binary/ternary search for best x). This group is now the "front group". Both groups walk continuously. The front group stops walking when they reach the goal. As long as there are pupils in the back group, the bus keeps moving pupils from the back group to the front group.

      WA test #7: http://codeforces.com/contest/701/submission/19349308

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

        I think the best distance x depends on the time remaining so the drop off point wont be the same for all the kids

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

          Right. The front group is continuously walking, so the drop off point won't be the same for all pupils. In my previous comment "x" refers to the first drop off point.

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

        I give up. Got as far as test #9. If anyone has an idea of where this rounding error comes, I would love to know: http://codeforces.com/contest/701/submission/19350779

        edit: nevermind, solved it

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

Anyone please explain the 2nd test case of Problem D (Div-2). In which way the ans is 4.7142857143 . My calculated ans is 5.6666664444 :( .

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

    5.666644 was coming only if you assumed bus will always reach towards the end of destination. Answer could be reduced if the bus leaves those k persons somewhere in between

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

    ans is 33/7.0 and theres a O(1) formula

»
8 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

WTF with DIV2 A? Almost all people in my friend list have it wrong on system tests :O Edit: Seems it is fixed now! phew :D

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

Haha, is there anyone notice a small bug in the very first seconds of system testing? All of the accepted submissions are shown to be hacked!

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

Is there anything particular about Div1,B testcase 10 or is it just a large test case? I'm pretty sure my code was O(n) and I couldn't think of any exceptions.

19346020

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

    I can't find any exceptions too... How about changing recursive function to loop? If It still gets TLE, then it will have an exception.(I'm just saying that recursive depth 200000 is dangerous)

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

      I resubmitted without using std::pair and going threw only one dfs. I think the complexity was the same but the use of stl, etc. just increased the time constant a lot. Thanks for the help

      19367422

»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I think problem setters should not add unnecessary character set like in Div2 C. Either keep a-z or A-Z , but why both? >( ..

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

Am I the only person who understood the sequence: "...reversal of the bus, take place immediately and this time can be neglected" that it takes 0 time to reverse (go backwards) no matter how long?

I know that it would mean a very strange bus, but I lost 25 minutes before noticing it :(

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

    I interpreted it the same way. Although I probably wouldn't have been able to do it even if I had interpreted it correctly :P.

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

    WTF!! I came to know now!!

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

    So ... what does it mean in the end ?

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

how to solve div 2b?

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

    Denoted by x the number of rows where no rook is placed, denoted by y the number of columns where no rook is placed. Answer = x*y.

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

    In total (in the beginning) there are n * n cells.
    These n2 cells can be viewed as n rows of cells and n columns of cells.
    When we place a rook, it destroys completely 1 row and 1 column.

    Let's keep 2 arrays which will tell us, whether the row/column was destroyed or not:
    bool destroyedRows[100000];
    bool destroyedCols[100000];

    After you place the first rook at cell (r0, c0), we can destroy row and column like that:
    destroyedRows[r0] = true;
    destroyedCols[c0] = true;

    The amount of alive rows decreases like that:
    long long cellsLeft = n * n;
    cellsLeft -= n; // for destroyed row
    cellsLeft -= n; // for destroyed column
    cellsLeft += 1; // because row and column intersect at point where rook stands

    If you place the next rook at cell (r0, c1), you cannot destroy the row r0 the second time.
    That is why you should first check whether it was already destroyed:
    if (!destroyedRows[r0])
    {
        destroyedRows[r0] = true;
        cellsLeft -= n;
    }

    The final idea is to accumulate the amount of destroyed rows and destroyed columns till the current rook.
    Imagine that you have already processed i - 1 rooks. Now, the i'th rook wants to destroy the row ri and the column ci. If the row ri hasn't been already destroyed, you should destroy it now. But some cells on that row ri where previously destroyed by i - 1 rooks before the current rook. When they (previous rooks) were destroying there's columns, they also crossed the row ri! How many times did they cross the row ri? Well, they should have crossed it when they destroyed their's columns and we should just keep track of the number of columns destroyed (which is  ≤ n - 1). We will use this number to add back the amount of destroyed columns:
    ...
    destroyedRows[ri] = true;
    cellsLeft -= n;
    cellsLeft += destroyedColumnsCount; // add back cells that were already destroyed before

    That is the general idea. The rest is implementation detail... =)

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

    I think the basic idea is quite easy.
    Initially, number of rows(n) = number of columns(m) = n

    Then there are only 4 cases:
    1. if you have not visited the row and the column both
    visit them and reduce them, n-- & m--
    output: cout<<(n*m-(n+m-1));
    2. if you have not visited the column visit and reduce the column size, m--
    output: cout<<(n*m-n);
    3. if you have not visited the row visit and reduce the size, n--
    output: cout<<(n*m-m);
    4. if you have visited both the row and column, there is nothong to do
    output: cout<<n*m;

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

    Here is my approach :)

    For each query, you have to find number of cells on the board which do not have their row number and column number equal to any of the positions of the rooks placed uptill then. Actually, I did it by solving its complement, i.e. number of cells on the board which have their either their row number or column number or both not equal to any of the positions of the rooks placed and then subtracting this answer from the total number of cells.

    Maintain two sets for rows and columns. Denote them by r and c. Total cells -> (n*n)

    Cells which their row equal to any of the rooks and column not equal to that of any -> (n-size(c))*size(r)

    Cells which their column equal to any of the rooks and row not equal to that of any -> (n-size(r))*size(c)

    Cells which their row not equal to any of the rooks and column not equal to that of any -> (n-size(r))*(n-size(c))

    Therefore Answer = (n*n) — (n-size(c))*size(r) — (n-size(r))*size(c) — (n-size(r))*(n-size(c))

    On further simplification, this turns out to be,

    Answer = n*n — size(r)*n — size(c)*n + size(r)*size(c)

    Answer = (n-size(r)) * (n-size(c))

    Here is my solution: Code

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

can rating fall over 100?

I think mine will...

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

I started trying problem A after I read it I couldn't understand the second sample, so I decided to move to B, after I solved it I went to read C, I figured out the solution quickly:

apply max flow considering all edges capacity equal to 1, if it's more than 2 then output -1 otherwise try out to remove each edge which became saturated and for each of them find bridges and pick best bridge on the path between s and t of course there's some corner cases to handle.

wow very easy idea I decided to code it although I have bridges and max flow codes beforehand it took me a full hour to code it, after passing all samples I submitted it and got WA after fixing some bugs I still got WA the contest ended but I didn't solving anything except B, if I knew coding C is overkill I would have returned to solve A instead :(

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

    I had the same solution to C as yours, but little bit simpler — you don't have to compute maxflow. If for every "deleted" edge, there is no path from s to t consisting only bridges, then we print  - 1.

    I didn't code it, but it's O(m2). Isn't it too slow?

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

    I had a solution that didn't need flows and works in .

    Get a path from s to t. If none exists, print 0.

    This path will consist of at most n-1 edges. Now for each edge in this path, remove it from the graph and construct the bridge tree of the remaining graph. If s and t are in the same block int the bridge tree then removing this edge is of no use to us. Bridge Tree can be constructed in

    If s and t are in different blocks find the minimum weight edge on the path from block of s to block of t in the bridgeTree. Now you have two edges, compare their weigths with the current minimum and update accordingly.

    Add the removed edge back to the graph and repeat.

    Took too much time debuggin but oh well :/ 19347868

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

div 2 D anyone ?

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

thanks Physics for div2 D ))

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

    let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.

    I thought of this logic but wasn't able to implement. Am I thinking right?

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

      Yes, right idea. You can get it if you go to the frame of reference, where students are stationary. We can solve it by solving equation system.

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

Overflow in B anyone?

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

    Overflow case is already present in pretest 3

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

      I have a case of what I think is an overflow at testcase #31. Its a negative number, and a huge test case, so its the first thing that came to mind.

      edit : Its a case of unsigned integer overflow.

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

Was I the only one who thought "reversal" in Div2 D means "traveling" back to the students after the drop-off? Bad me. :(

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

Why the system testing is stuck at 100% ?? We have been seeing this for the last few contests !! Please fix this issue! :(

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

Getting WA in test case 31 in Div2 B. Can anybody give any insight why? Thanks! :)

Solution

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

    row.size() and col.size() are returned as unsigned ints, and in the worst case multiplying them can make them overflow. Type cast them into (long long)! :)

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

    i too had similar solution....failed because size function returns unsigned int :(

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

petr now

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

When will be editoral?

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

Any hints on how to solve div 2 C ??

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

    I used cumulative sum + binary search on window length approach. But it can be solved using two pointers technique. Hope this will help.

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

    You can solve it by method of two pointers.

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

    It can be solved using 2-pointers technique.

    We keep 2 pointers : left and right, which indicate that currently we're working with the houses(string) with indices [left, right].

    Also, we maintain an array to keep a count of all the pokemon's(letters) that we've caught so far, and a variable min, to keep the minimum substring length which includes AT LEAST 1 pokemon of all types.

    Then, inside a loop for left which goes from 0 to n — 1 (n = length of the string), we run another loop and increment right and add the pokemon at index right, until we don't have AT LEAST 1 pokemon of all types or right becomes equal to n.

    At this point, we update our min variable if the current substring [left, right] includes all pokemons and it's length is less than min.

    Then, we decrease count of the pokemon at index left and then increment left.

    Again, we check and update our min if needed.

    We do this inside a loop for left as stated above.

    Since right goes from 0 to n — 1 once and also left, the total complexity is O(n).

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

      I dont understand how the complexity of your algo is O(n). If i am not wrong it is a nested loop. right ??

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

        You're wrong, because both pointers only move forward, which means that the complexity is O(n).

        UPD: We don't move right pointer everytime from left, we keep its' position saved.

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

        No, right is initialised only once, outside the first loop, and inside it is only incremented. We never reinitialise it or decrement it. So, right goes from 0 to n — 1. And the other loop is for left, which also goes from 0 to n — 1. Hence, O(n).

        You can refer to my code : 19349919

        P.S. : I actually initialised right to -1.

        I hope it's clear now. :)

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

      I tried something like that , but it's O(n^2)?...here is my code that took TLE;

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

        Actually you are setting your right variable to n — 1 multiple times and then are iterating it down to i for 0 <= i < n

        so, for i = 0, you have n — 1 loops, for i = 1,you have n — 2 loops and so on..

        So your worst case time complexity is O(n^2).

        You need to increment both your left and right variables from 0 to n just once. if you still don't get exactly how it's working let me know, I'll explain :)

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

    Move across the string recording the last position of each character that occurs in the string. Once you have seen each letter at least once, each time you move take the difference of the biggest last position and the smallest last position. The smallest such difference is your answer. This is worst case O(52*n).

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

    Binary Search + Segment Tree Problem-C

    I don't like 2-pointers

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

      that's just wrong man...

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

      two pointers much simpler than seg tree+binary search.

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

        ofcourse , but I was bored a little bit and I had the seg-tree code ready

        just the final touch

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

upset..I got rank 10 too but not on the winners' board..Orz

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

rest in pepperoni petr :'(

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

Hi, can anyone tell what may be the cause of this error in the Div.2 task A?  19333396

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

In recent rounds I have seen a glitch in the standings. When the system testing starts all queued submissions turned to failed. May be it's not a big deal but I wonder why this is happening?

NB: The round was great. I'm looking forward to seeing so many rounds like this one. Thanks for the round :)

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

can anyone explain the approach to Div2C?

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

    Go through the sequence and push symbols into the queue one by one. When it contains all types of symbols, this means you found a subsequence that satisfies problem statement. Now you can crop it from the beginning to make it as short as possible — just delete front symbol from the queue while it still contains all types of symbols. When done, check if this snippet is the shortest that you found so far. To continue searching, just remove first symbol from the queue (it should miss one type of symbol now) and continue pushing them from the given sequence. All the procedures can be performed quickly using STL structures like queue and set.

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

    I will explain my solution (binary search + sliding window) at first, its obvious the answer is the size of some contiguous subsequence that have all types of pokemons.

    if you try every range with size 1, then every range with size 2, .. until have range with all types of pokemons you can get the answer. but this is to slow which takes O(n^2).

    so you should do binary search on the size of the range, which takes O(n*log(n)). http://codeforces.com/contest/701/submission/19338973

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

approach for div2E ?

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

    Find a node such that all subtrees have <= K universities. Answer is sum of all depths. Complexity : O(N).

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

      Nice explanation, thanks!

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

      It took me a couple of minutes to figure your comment out, but this is beautiful.

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

      I tried finding a node such that it has exactly K on one side. Can you figure out my solution fails?

      Your node will also have this property. 19342855

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

        I think you meant K and not K / 2 ? Also, there may not be a node such that exactly K nodes lie in one subtree.

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

          Yes, but there is always a node which has a subset of sub-trees having exactly K nodes and exactly K in other subset when the tree is rooted at this Node.

          In un-rooted definition , if we remove this node all the components have <=K nodes.

          Is anything wrong in this hypothesis?

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

            What if the subtrees have the following count of nodes : 2,2,k-3,k-1 ?

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

              Thanks.

              So close yet so far from the solution. :)

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

      Could you more explain the algorithm?

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

      can you prove that such node is optimal choice?

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

        Yes. When we choose such a node, we know that each subtree has <= K universities. For a university in any one subtree, we have two choices : To pair it with a university in a different subtree or to pair it with a university in the same subtree. You can see that pairing universities among different subtrees maximises the answer, which is what is required!

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

          how will you prove that it always give maximum sum

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

    Suppose there is a edge u->v and there are count[v] vertices that are in subtree of v and also in the 2*k list, then the edge u-v would be used (added) in the answer min(count[v], 2*k — count[v]) times only since we can always select min(count[v], 2*k — count[v]) pairs such that one is from each side of the edge

    Link to submission

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

Div2D: What is the significance of "In order to avoid seasick, each of the pupils want to get into the bus no more than once"? I can't think of a case where shuttling a student more than once would be useful.

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

    For example, let there be three students, but let the bus carry only two simultaneously. Intuitively, a good solution would carry each of the subsets {1, 2}, {1, 3} and {2, 3} on the bus for the same duration. However, this is impossible given the constraint.

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

      Because the bus takes time to drive back the constraint doesn't matter. Makes the problem easier though, otherwise you'd have to figure out yourself that it doesn't matter...

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

        It does matter. I think the point in Gassa's example is that without the constraint we never have to drive a half-empty bus. So the bus is always driving at 100% capacity.

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

          It's impossible to drive the bus at 100% capacity if there's 2 seats and 3 pupils. The bus will always have to drive back to get the last pupil and drive at 50% capacity.

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

            Right, when the bus is driving BACKWARDS it's always empty.

            When the bus is driving FORWARDS we have a capacity problem. Without the constraint we could always drive forwards with 100% capacity. With the constraint we might sometimes have to drive a half-empty bus. In Gassa's example, we might first drive {1, 2} and then drive {3}. Even though we have room for 1 more passenger, we can't take anyone, because 1 and 2 have already been to the bus and we have no-one else we could take.

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

              'The constraint' meaning 'each of the pupils want to get into the bus no more than once', even without the constraint the bus cannot always drive forwards with 100% capacity.

              There's no better solution without this constraint, just like you stated in your original comment.

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

                Read Gassa's example again, it's very short and it illustrates the problem perfectly. It has the bus always driving forwards with 100% capacity. Add the constraint and the capacity drops.

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

                  After reading Gassa's example again (and again) I still don't understand. Could you give me an example of how the bus will always drive forwards with 3 pupils and 2 seats?

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

                  I wasn't able to construct an example. I may have been wrong about the capacity thing.

                  Let's say we shuttle {A,B} for some distance. Now we have to shuttle {C} for the same distance on its own. We can't shuttle A with C at this point, because A is ahead of C.

                  So now I'm back to square 1, wondering what's the significance of the constraint in the first place.

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

      This looks impossible even without the constraint. How does the carrying of each of the subsets {1, 2}, {1, 3} and {2, 3} looks like?

      Do they need to travel backwards with the bus? Does it add efficiency?

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

        I wasn't able to construct a speedup example so far.

        My point is a bit different: when the constraint is there, it is irrelevant whether or not it's possible to get faster without it. So this investigation happens after the contest, not when solving the problem. Which is a good thing, especially if there is indeed no faster solution without the constraint.

»
8 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Who else has noticed that tourist has become top on the rank table even without participating!?

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

can someone explain me the process to solve div1 D? i was thinking mo's algorithm but can't figure out the calculations. please help :(

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

    By mo's algorithm, you can know the occurance of each number in the query interval [L, R], and also you can know which kinds of occurance has appeared. Since , the number of different occurance is no more than . So you can use pair < occ, cnt >  instead of only occ to represent a node in priority queue. And every time you pick up a node from the top, you can simply do this : occ *= 2 and cnt /= 2, if cnt is odd then you should split it. The whole algorithm is about .

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

      thanks :D nice explanation :)

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

      Did someone actually fit this exact complexity in TL though? This last part (with priority_queue or w/e else) seems a bit too slow for me, I spent quite some time trying to make it work (I've heard the solution, but I'm really curious if it can be passed in )

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

        The priority queue can be replaced by two queues. And this whill be .

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

          How do you bound number of Huffman's vertices? Is it surely ? Won't it be multiplied by some small nonconstant factor?

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

        I made it work. The only part which is beyond n sqrt(n) is the sorting — I perform O(n) sorts on an array of length O(sqrt(n)), which works really fast. Other than that everything else is O(n sqrt(n)).

        Oh, and using a custom list implementation instead of std::list resulted in a 20x speedup :D

        Link: http://codeforces.com/contest/700/submission/19373681

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

can someone help me out im getting WA in #17 test case in DIV2-C 19356617

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

    It can be solved using binary search. map all the characters and store an array dp. where dp[i][j] represents the number of occurrences of the ith character from index 1 to j. Then run a loop from 1 to n and for each i find out the lowest index r, greater than i where each character occur at least once. the complexity is O(n log n), so it easily passes. there might be two pointer solution but, binary search seemed easier and safer to me.

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

    Line 28: r<=n is causing problem.

    You have to stop the loop when r hits n, remember to care of the cases where string[n-1] is part of the optimal solution.

»
8 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

When will we read the anlysis of the problems?

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

My approach on Div2E/Div1B, not necessarily correct, maybe I just slither through the system test cases.

Step 1:

Set a node which is only connected by an edge as the root of the tree.

Step 2:

DFS from this node, for each subtree count it's amount of university inside the tree. Select the minimum among all the nodes which has at least k university. (This is probably the node which every pair in the optimal solution will past... I say PROBABLY because I don't have a strong prove for this, but I can't think of a counter case.)

Step 3:

DFS from this node, the answer is the sum of this tree.

My submission: http://codeforces.com/contest/700/submission/19363132

A kinda similar question I would recommend to try out: http://codeforces.com/problemset/problem/685/B

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

Any tips on Div2F/Div1C? Cycles in the graph seems to be a huge obstacle in the problem.

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

    For simplicity assume that there is no multi-edge nor self-loop (they can be handled in the beginning).

    First idea: brute force — remove every edge and look for bridges between s and t and find the best option. Iit can be done with standard dfs with low fuction, but -supposing you start if from s — you also need to remember if there is t in the subtree you've just visited. Complexity: O(m^2)

    Better idea: take a path P between s and t (if it doesn't exist — output 0 0). Observation: At least one edge from P must be removed. As the path contains at most n edges, we get O(n*m) which easily fits the limits.

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

      Hope you don't mind that I'm asking, but how do you get O(n*m)? I'm only able to get O(n*(n+m)). After I remove and edge from the path I have to redo the DFS and this leads to O(n*(n+m)).

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

        Yeah, but n<=m so it is fine to write O(m) instead of O(n+m). Of course I also have the same complexity as you.

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

dude , where is the editorial ?

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

How long we wait for the editorials??

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

Will Editorial be published this time? Waiting...............

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

Editorial will be published soon, I guess. Another question is "when is the next round?"

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

Hints for E and F div 2 ?

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

    E and F div 2 = 7. That's all I can tell about that :(

    However, you can check out these hints: E and F.

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

    Hint for F: Let find any path P from S to T: O(M + N). The length of P will be less or equal to number of vertices. Try to remove any edge in P: O(N). For each removed edge in P find all bridges in resulting graph: O(N + M). Check if removing the bridge will disconnect S from T (it is possible at O(1)). Don't forget to check special cases: 1) There is no path from S to T. 2) Removing some edge in P disconnectes S from T. So this solution will work at O(N * (N + M)).

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

      How did you check if deleting an edge would disconnect S from T? I did this while building dfs tree: if recursive DFS on edge has found T and that edge is a bridge, then account it.

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

        I did it exactly the same as you did

»
8 years ago, # |
Rev. 6   Vote: I like it +19 Vote: I do not like it

D solution:

Note these observations:

  • The total time is set by the worst kid travel time.
  • The optimal solution doesn't need to make the bus go to L on each trip. It may leave kids in half way and go left to take another kids.
  • The optimal solution should end in L on the last trip. Proof by contradiction: If we don't end in L on the last trip, then we are leaving kids half way at speed V1, that could go at speed V2. Such proof do not apply to the other trips because time is set by the worst kid. The kid we are helping is the worst kid only in the last trip.
  • Each kid will travel at speed V1 some time, and travel some time at speed V2 until it reaches L. If a kid travels more time at V2 and less time at V1 it will always be faster. the proportion t2 - t1 defines the kid's time to target. V1 * t1 + V2 * t2 = L
  • If we increase V2 time of some kids, then we are reducing V2 time of other kids, Some kids are traveling more time at the bus than others.
  • So, now I want to prove that in an optimal solution all kids must travel the same V2 time. I will do this again by contradiction. Imagine, that we have an optimal solution where two kids travel at different V2 times and one of them is the worst kid (if not all kids reach target at the same time, then there should be one or more kids to call the worst kid). Then we can always improve the worst kid travel time by increasing it's V2 time and reducing the V2 time of other kids. Improving the worst kid travel time implies improving total solution time, and as we reduced V2 time of kids that are not the worst, they don't affect the total solution time. So this is only valid if there are kids to be called the worst, and kids that are not the worst.
  • We have just proved that any solution where the kids V2 times are not equal can be improved, this means it is not optimal. So the optimal solution must make all kids to travel the same time at V2.
  • So now the solution is simpler. All bus trips with kids must always last the same and we could compute a growing F(x) = y where x is V2 time, that is bus trip time, and y is the position where the bus end in last trip. You need to see that if x (aka V2 time) is bigger then the bus travels more time to the right, so Y will be bigger.
  • As F(x) is a growing function, then we can binary search x until we find F(x) = L, and the bus last position is L. This is the only solution with all V2 time equal that end in L, this means, it is a valid solution. AS all other valid solutions don't have V2 times equal, they are not optimal, what means F(x) = L computed by binary search is the optimal solution to the problem. As the statement do not ask for x (aka V2 time) we should do the extra calculation of the travel time, but if we compute the F(x) = y we can easily compute F(x) = t where t is the total bus traveling time, or another option is to compute V1time = t1 using V2time = t2 and t = t1 + t2 (note that all kids reach target at the same time as the have the same t1 and t2!)
  • I recommend in binary search to use fixed number of iterations. It is the simpler solution, and we avoid the use of EPS (if you don't know what it is ignore this last comment).

Code:

  • F(x) = t manual calculation 19373739
  • F(x) = t based on v1t1 + v2t2 = L 19374507
  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    In the second test. Why can't I take each pupil on the bus per 3 meters?

    let (p1, p2, p3) positions of the pupils i

    t = 1.5 — (3, 1.5, 1.5) — p1 in the bus

    t = 3 — (4.5, 4.5, 3) — p2 in the bus

    t = 4.5 — (6, 6, 6) — p3 in the bus

    total 4.5

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      You are ignoring Bus return time. Bus can not teleport from one kid position to another instantly. You need to add to your calculations meeting time from the bus going left and the kids going right.

      " as well as the — reversal of the bus, take place immediately "

      The reversal is the time to the bus to flip, not the time to the bus to return to search for more pupils.

      Your example of V2 time = 1.5s (3 meters) would be

      t = 1.5 — (1.5,1.5,3)

      te = (3-1.5)/(2+1) = 0.5

      t = 2 — (2 , 2 , 3.5)

      t = 3.5 — (3.5 , 5 , 5)

      te = (5-3.5)/(2+1) = 0.5

      t = 4 — (4 , 5.5 , 5.5)

      t = 5.5 — (7 , 7 , 7)

      You end in position 7, so you need to reduce V2 time.

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

        You are right, I misunderstood the problem statement. Thanks a lot.

»
8 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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

Any ideas on how to solve Div2F/Div1C?

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

    Find any path from S to T. Try to remove each edge of the path, In the resulting graph try to remove each bridge. This solution complexity is O(N * (N + M))

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

waiting for the editorial and next context ...

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

Why does python submissions for div2 problem E gets runtime error in test 11? n is 200000 and my code: http://codeforces.com/contest/701/submission/19425329

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

    I know nothing about Python, but it seems that you are not using 64-bit integer to store the results: Test case 11 is the first case where you need long long to store the answer. If Python has RE when there is overflow then this is probably your answer.

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

      There is no overflow in Python. Python's integers can store any number.

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

    The RTE is because of recursion depth limit reach in your case. This happens mostly with me I used to switch to c++ with same logic!

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

      Thanks! How do you overcome the problem or how to increase the depth limit?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

11