По техническим причинам некоторые языки программирования (Kotlin, C#) не будут доступны во время раунда 877. ×

Блог пользователя zoomswk

Автор zoomswk, 7 месяцев назад, По-английски,

Hi, everyone!

Unfortunately, the round was moved two hours later. Sorry for the inconvenience.

It is my honor to announce that the Codeforces Round #408 rated for the second division is going to take place tomorrow at 16:35 UTC. As usual, participants from the first division will be able to participate out of competition.

As the author of this contest, I (zoomswk) would like to thank poomrokc, nisaruj, and Phoom for testing the problems, KAN and netman for their help in contest preparation, and MikeMirzayanov for the awesome Codeforces and Polygon platforms. Cute graphics in this round are designed by my friend Chonphuech Sripongtanakul, so thanks to her also!

In this round, you will be given 6 problems and 2 hours to solve them. Zane the Wizard, along with his puppy and his crush, will be asking for your help. It is advised that you read all problems and read them carefully.

As per tradition, the scoring distribution will be announced later.

I hope you will enjoy the problems.

Good luck! :D

UPD: The scoring distribution is 500-750-1000-1500-2000-2500.

UPD: The round has ended. Thanks everyone for participating. I'm deeply sorry that the problems turn out to be way harder than I expected. Please stay tuned for the editorial. T_T

UPD: The system testing is complete. Congratulations to the winners!

Div. 2 Winners

  1. Wissenschaft

  2. newcolas

  3. ckw1140

  4. VAVAvile

  5. pantelija

  6. Harmonica

  7. mateuszdanowski

  8. Mohammad_kilani

  9. Al2K

  10. LovelyPLY

Div. 1 Winners

  1. fanache99

  2. HellKitsune

  3. unused

  4. KrK

  5. petrescu

I sincerely apologize that slow input/output methods caused so many TLEs. Unfortunately, it is not possible to rejudge the submissions nor increase the time limit at this point. This is my fault, and I'm terribly sorry. I was not aware of this because my solutions run in < 500 ms of time limit in all problems. I hope you understand.

The editorial will be published in a few minutes, and I'll update this post when it's available.

UPD: The editorial is ready!

 
 
 
 
  • Проголосовать: нравится  
  • +311
  • Проголосовать: не нравится  

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Good luck to you too! I wish your tests to be strong and your problems to be interesting to read, understandable and challenging! :)

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится

It's gonna be my first round after breakup :D

»
6 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Zane is The Wizard but still can't make his crush into his girlfriend. I feel it.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +52 Проголосовать: не нравится

    Don't worry, you'll get to help him in the contest. XD

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

      Why do i get the feeling that he is going to ask our help to make his crush into girlfriend.

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        LOOK AT THIS HANDSOME MAN

        HOW DARE YOU SUGGEST HE NEEDS YOUR HELP IN GETTING A GIRLFRIEND

»
6 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

I can't register to unofficial participation.

»
6 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Div 1 Users are not able to register.

»
6 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How I wish there to be earlier contests since i'm in UTC+8 area.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Delaying it 2 hours makes me able to do this round, thank you! :D

»
6 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Finally zoomswk is writing problems for CF! I heard your problems were really good from some other Triam Udom students in POSN camp 2. Looking forward to participating today!

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the delay zoomswk, I would have missed the round. Sorry for them who had suitable time.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Pleasant unexpected delay. Now I won't have to sacrifice my dinner this time :)

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Too bad, I can't do the round now :(

»
6 месяцев назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

Rating prediction here

Extensions:

Have fun & high rating:)

»
6 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

rip UTC+8

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится -24 Проголосовать: не нравится

div 2 after long days. ;(

»
6 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

1900 a rating everyone must get a lving![contest:408]

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

It's not a good time for Chinese now, so sad. :(

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

Thank you zoomswk for giving us the opportunity to help someone.

»
6 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

We are not able to help our self with our crush. Lets see if we can help the wizard! XD

»
6 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

good luck

»
6 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Such an interesting scoring distribution :D

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

After a long time, a 750 problem.

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

after locking can't see soln of others plz solve this problem as soon as possible

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

in problem b , for eg: 4 to 6 swap takes place then is it sure next swap will be from 6 only to somewhere else ?

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +96 Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

I can't understand how I managed not to read the only word in bold in the whole statement of C and spending the whole contest solving a different problem...

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Look at first and second page of standings :D

remove them pls before rating update ;D

»
6 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

now it looks like 20+ people sit together and code together and submit at the same time :P

why this guy so boring?

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится +109 Проголосовать: не нравится

These Bots!

»
6 месяцев назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

Codeforces Round #408 (Div. 1,5) :)

»
6 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

is there any better order for F that O(n*sqrt) ?

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Am I right that answer for D is always K - 1 (may be someone even can proof that)?
UPD Regarding to comment below that's actually number_of_cities_with_police  - 1.
If so, that will explain why we had to print sertificate for an answer.

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    I guess because the tree is arranged according to the law. So the question is actually how to destroy some roads in order to get number_of_cities_with_police connected components. The best way is to have one police station in every connected component. And because in the tree every city is at most d units away, it is possible to keep this property in partition at the end. I hope you understand :)

»
6 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Including multiple police stations in the same city in D was evil. Cost me 2 WAs. :(
Unbalanced problem set but nice problems! :D

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone please tell How to solve C ???? I spent all time on it ,yet no success :(

»
6 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

WTF is C. C is too difficult

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone tell me how to solve Problem D & E please, I can't wait for the editorial xD

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    In problem D we can run a single bfs from every police station. Then for every city we have its distance to its closest police station as well as the number of different police stations that has its distance equal to the shortest distance. Run a single dfs from vertex 1. For each vertex, let's consider its children. If a children has abs(dis[v]-dis[u])!=1 then we will cut that edge. If dis[v] == dis[u] — 1 then we will count how many vertex like that and we will erase (cnt-1) of them because we only need one of them to maintain the distance. And for (dis[v] == dis[u] + 1), as we already have the number of ways to get to this vertex, we will delete this edge if way[v] > 1 and then way[v]--. That's all!

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    D is a simultaneously BFS from every city with police. Mark each connected city with nubmer of a source police city, then go through edges and if a "police number" on the left != one on the right, then the edge can be removed. You even don't need the d parameter.

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did mostly the same, but only marked cities as "connected" without the number of the source and also marked "used" edges. And if I come upon an unused edge that goes to an already connected city then it can be removed.

»
6 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The girl's cheating algorithm in E is so complex, almost as if you have experience with it :P

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem B, what is the expected output for this input?

4 1 3 4 3 4 1 3 3 2

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    2

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My program prints 2.

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Shouldn't it be 3? Confused.

      When 3 and 4 are swapped, the hole should be underneath cup 3. Again when 1 and 3 are swapped, the bone gets into the hole. Now when 3 and 2 are swapped there should be no change. Did I understand the question incorrectly? :/

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can we use greedy to solve the problem D ?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when will he post the editorial?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain me B? I dont get it completely... more like i thought i knew what was going on there, but i did 9 fails and i dont even know why Was he also changing positions of the holes?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone provide hack case for B?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is problem C just modified BFS starting in the vertex with max guard and max degree, or is there something more? (sorry for my English if it's bad)

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    (wrong solution)

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      No, this is wrong.
      Take the case:
      6
      3 3 3 3 3 3
      1 2
      1 3
      1 4
      1 5
      1 6

      Answer would be m+1(4) for this.

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Indeed, thank you for pointing this out.

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        What is the approach for C?

        • »
          »
          »
          »
          »
          6 месяцев назад, # ^ |
          Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

          Let there be a set of nodes which have equal and maximum weight.
          For each node 'x' from the set,
          Final weight of x: Same as original weight
          Final weight of neighbors of x: Original weight+1
          Every other node: Original weight+2

          Do this for each x in the set and calculate the minimum maximum weight.

          EDIT: I got a WA. The reason is that we have to consider every node rather than just the max nodes.(Imagine case where all max nodes are connected to a single smaller node)

          • »
            »
            »
            »
            »
            »
            6 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Shouldn't that get TLE if all of the nodes are with the same value ?

            • »
              »
              »
              »
              »
              »
              »
              6 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I used multisets so I only had to iterate through first node+neighbours.
              It took 1s but TLE is still a worry.

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      5

      5 5 4 5 5

      3 1

      3 2

      3 4

      3 5

      Wouldn't your algorithm give 7 for this case? I think it should be 6.

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      "If t > 3, then the answer is m+2." I think it's incorrect. For example, there can be 10 nodes with maximum value, and one node which connects with each of this nodes.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think starting from guard with a max strength and connected to maximum number of other max guards is correct, your algorithm will not work for graph: 10 10 10 10 1 1 1 1 ... 1 2 1 3 1 4 4 5 4 6 4 7 ...

    Your algorithm starts from 4, and we should start from 1.

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

-8 in B because i forgot ios::sync_with_stdio(false) D:

»
6 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

it was a big leap from b to C hahaha

»
6 месяцев назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Each Id belongs to one person I guess! but if each code are same then they will be skipped without the first one. But he should get punished -_-

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, Could someone help me out with understanding an optimal solution for D ?

Thanks!

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    I think we can separate the tree in forest, where the root of each tree has a police office in it. This way the answer will always be P - 1

»
6 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

S**t :( Failed to notice that multiple police can exist in one city :'( maybe that's the reason for getting wa on pretest 6

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I don't think it is. I was failing on 6 for the longest time too. What does your solution output for this inout:

    5 2 2
    1 4
    1 2
    2 3
    4 3
    3 5
    

    I believe the correct output is

    1
    2
    

    (EDIT: Fixed it from 5 2 3 to 5 2 2)

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Damn. I failed to notice that too. My program was based on the assumption that there's only one police in one city ;-;

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I believe that it is the same guy who have the ranks between 3, 30 :D

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That feeling when you realized problem A minor bug... in the last 30 seconds

»
6 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

The problem set was really very nice. I have enjoyed all the problems. Thanks for the round. Hope to get such good problems from you again.

»
6 месяцев назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

Submitted D with 9 seconds to spare, let the system tests be kind

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I can't forgive myself for wasting too much time to find out why was my B solution failing at test 3 ..

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same here, did u find out? would u like to share with me?

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was transferring the bone in u->v , forgot that if glasses u and v are swapped then there are two possibilites u->v or u<-v. Used this, pretests passed.

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Consider swapping xi and vi. I was only checking if the bone is at Xi so I move it to Vi. I wasn't checking if it is at Vi.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What was it?

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Fake , fake everywhere ..

»
6 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve E?

»
6 месяцев назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Who dis?

»
6 месяцев назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Поднимите руку те, кто счел, что в задаче D параметр d весьма никчемен.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B? I have wasted 1 hour and 53 minutes for damn pretest 3 on B...

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    1 ≤ hi ≤ 106, so you can keep them in bool array, like holes[hole] = true.

    Then check if holes[bone] = true then print bone, break else continue swapping.

    Link for submission: http://ideone.com/BvFVqI

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I was transferring the bone in u->v , forgot that if glasses u and v are swapped then there are two possibilites u->v or u<-v. Used this, pretests passed. Take care of the current position of the bone.There might be a case in which we are swapping the glasses and neither of them has a bone.If the current pos has hole voila! answer found.Else in the end the final pos is the answer.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1) if first position contains hole , then obviously print 1 , return 0; 2) else -------> keep track of current position of bone in any variable(say boneVar) -------> Initial value of boneVal = 1(given in question)
    ----- > now iterate for k times and take values of cups to be swapped,,, suppose inputs are cup1 , cup2 for(int i = 0 ; i < k ; i++)

    for(int i = 0 ; i < k ; i++)
    { 
             cin >> cup1 >> cup2;
              if(cup1 == boneVar) boneVar = cup2;
              else if(cup2 == boneVar) boneVar = cup1;
              /// now check if the new position of bone contains hole then that is answer
             if(hole[boneVar])
             {
                  cout << boneVar;return 0;
             }
    }
    
    if(cup1 == boneVar) boneVar = cup2;
          else if(cup2 == boneVar) boneVar = cup1;
»
6 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

When system testing will start?

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I think it may take a while because as you can see, there are many many spam accounts in today round and moreover, their owners have used "Find and Replace" to replace names of all variables and functions which will make the CF anti-cheat accept their solutions UPD: All bots have been deleted

»
6 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From rank 3 to rank 30 , will those people be removed and ranks will be updated ???

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

can we use this to solve E?
UPD: It works

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If (p / 2) * k >= n. Obviously, It is the maximal point. Else we use dp with n * p * k states, each state has O(k) transitions.

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Isn't that O(npk^2) complexity?

      I came up with a solution with O(n*p*2*k) states and constant number of transitions but didn't manage to implement it during the contest. And it also took my a while to finally accept it afterwards. It turned out to be pretty messy :/. Here is my code if you're interested.

      UPD: Ok, I missed the point. It's indeed O((n^2)k).

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It is the intended complexity too. Again, timelimit is too strict :). 1000 * 1000 * 50 = 5.10^7.

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

The cheaters are removed from the rankings, except the one who got hacked on C.

»
6 месяцев назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It wasn't that hard I think.

Thanks for you effort :D

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Test 66.........

»
6 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Got to hate getting TLE for using cin instead of scanf

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I think there were some problems with the server during system testing. At B, many people(as have I), have got a TLE even if the complexity was linear in the numbers read.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am rotting at the newbie section

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

TLE on B? What is this dude?

»
6 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

TLE on problem B because I forgot to use fast IO 26261895

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C TL is so tight... my solution passed pretests with 1500 something ms and so did many others. Now my solution got TLE (probably ran a test in about 2100 or so ms) while many others are getting AC with 1950+ms solutions.

Not fair in my opinion.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could , someone please tell me the reason of TLE in this code of div 2 , B? 26277647

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone Please tell me why am I getting tle in Java in div2b problem. My code's complexity is O(K) . Here is my submission. please check Here..

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Time limit for problem C is too strict. Solution use multiset must pass.

»
6 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I got good on problems A, B and D, but after tests i only got A... Failed on TL on B and wrong answer on test 13 on D. http://codeforces.com/contest/796/submission/26274912

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
6 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Why is the system testing so slow? It seems like it is hung...

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

WA on Test 61 on problem B!!! why ??? :( :( 26270333

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why system testing does not finishes?

»
6 месяцев назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

I really hoped the purpose of Question B was more than just rejecting cin and accepting scanf -- it probably shouldn't have been a CF problem if that was really the case.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In fact some codeforces round ends up in first 40-50 minutes.

»
6 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Slowest System Testing Ever.

»
6 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Too long testing today. Eyes are on the screen for a long time, now tired :(

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

B and C are all about file reading optimizations. Had to switch pypy to cpython for it.

»
6 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

It's time to eat breakfast.

»
6 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

They should mention about the faster I/O method in the question

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Is it just me or recently in div 2 rounds the difficulty gap between problems is getting larger?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

They removed bots !

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Seems like they made case #66 of B only for removing solutions with cin/cout >_<

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in C, my O(n) solution with printf/scanf got TLE :|

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I managed to think nlogn. How to solve in O(n)?

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      One possible O(n) approach is realizing that we always start with the node that is neighbouring to the most nodes with maximum value. If the node itself has maximum value it is also counted as neighbouring itself. In the case of a tie choose a node that is maximal itself. Then hack from there.

      This works in O(n) and can be implemented quite cleanly: submission

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem B:

How is this submission displaying an additional "1" at the end? It's driving me crazy.
The output on my IDE doesn't include the additional "1" at the end.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You shall end program here if (holes[1] == 1) { cout << "1" << endl; break; // return 0; }

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Still, the 'break' instruction will exit the 'while' loop to the "return 0" line.

      EDIT: removing the entire if(holes[1]==1) part from the code and running it on codeforces will still display "1" at the end.

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Use this: std::ios::sync_with_stdio(false); cin.tie(0);

        And u will pass tests

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The other 'break', when the ball is dropped into a hole, won't exit the 'while' loop though, since it is located inside a 'for' loop.

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, haven't noticed while at first... But problem still is pretty the same. When you get ans = 55, there is still some data in input stream and while works until the data is gone or hole[1] == 1 case worked

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain to me why I got Runtime Error on test 111 of problem C (div2)?

http://codeforces.com/contest/796/submission/26283235

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yeap... Thought about using scanf(), but was too lazy...

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Пытался загнать в E следующее жадное решение: за линию считаю какое максимальное количество вопросов она сможет списать. Прибавляю к ответу это количество. Удаляю у гениев вопросы, которые она списала. Снова пересчитываю все. И так p раз. Не могу придумать контртест (

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried dfs on the problem D,and got a wrong answer on 6.26286839 I saw the others used bfs.So dfs is a wrong way?Can someone help me ?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Got runtime error test 38 Problem A http://codeforces.com/contest/796/submission/26263998

Later tried test 38 in Codeblocks, works normally and correct

WHY?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can you see the standings (scoreboard) for the Div 1 users?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DIV2-C: Got TLE in testcase 35. can anyone help me in analysing the time complexity of this submission Thank you in advance :)

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello everyone, could somebody tell me why I got AC instead of Time limit after I use scanf instead of cin for solving the problem B — Find The Bone. I'm so confused now, thanks a lot!!

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got a WA on test 6, whose input is: 5 1000000000 0 1000000000 0 1000000000 1 2 2 3 3 4 4 5 and the answer is 1000000002 ; but I think the right answer is 1000000001(with hack order 3 1 5 2 4)....I need help...I can't understand why..TAT

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Read the three conditions carefully. After the bank 3 is hacked, you can only choose to hack banks 2 and 4. Banks 1 and 5 cannot be hacked yet because they are not neighboring to any offline banks.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just wonder if the algorithm still work when the city is not a tree in problem D.

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It will still work. The solution would be more obvious could the input be any graph, wouldn't it? XD

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Got that! Thank you :) Now I see the reason that you make the country a tree haha...

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is problem C in this contest updated ?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I haven't done anything with it. What's the matter? :O

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am so sorry .The wrong with me i thought this is another problem :D.Thank u for caring.