zoomswk's blog

Codeforces Round #408 (Div. 2)
By zoomswk, 7 years ago, In English

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

  3. ckw1140

  4. VAVAvile

  5. milisav

  6. Harmonica

  7. mateuszdanowski

  8. Kilani

  9. Al2K

  10. ubzdld672

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!

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

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

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

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

    Thanks! I'm trying my best to make all that happen. ;)

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

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

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

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

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

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

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

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

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

        LOOK AT THIS HANDSOME MAN

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

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

I can't register to unofficial participation.

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

Div 1 Users are not able to register.

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

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

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

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

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

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!

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

    Thanks! Hope you'll like my problems too.

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

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

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

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

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

Rating prediction here

Extensions:

Have fun & high rating:)

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

rip UTC+8

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

div 2 after long days. ;(

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

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

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

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

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

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

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

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

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

Such an interesting scoring distribution :D

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

After a long time, a 750 problem.

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

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

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

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 ?

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

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

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

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

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

Look at first and second page of standings :D

remove them pls before rating update ;D

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

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

why this guy so boring?

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

These Bots!

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

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

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

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

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

    My solution works in O((n + m)logn). Please stay tuned for the editorial.

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

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.

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

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

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

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

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

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

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

WTF is C. C is too difficult

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

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

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

    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!

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

    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.

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

      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.

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

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

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

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

4 1 3 4 3 4 1 3 3 2

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

    2

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

    My program prints 2.

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

      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? :/

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

        You input n m k then you input the places of the holes.

        In your test case the hole is in number 4.

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

        the hole can not be swapped its constant during swaps

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

        The holes don't move when swapping cups.

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

Can we use greedy to solve the problem D ?

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

Can someone provide hack case for B?

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

    2 1 1 1 1 2

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

    i hack using this : 2 1 1 1 1 2

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

    2 1 1 1 1 2

    the answer is 1

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

    TL hack with 10^6 numbers. OK if solution hasn't scanf/sync_with_stdio.

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

      Wow, absolutely forgot about it:(

      All the contest I couldnt find any other narrow places in B besides the cases above

      I think TL was the main reason for so mane hacks

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

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)

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

    (wrong solution)

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

      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.

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

        Indeed, thank you for pointing this out.

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

        What is the approach for C?

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

          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)

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

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

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

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

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

      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.

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

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

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

    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.

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

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

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

it was a big leap from b to C hahaha

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

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

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

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

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

Thanks!

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

    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

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

      careful with several police stations on same node:)

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

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

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

    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)

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

      1 3 And I believe that's a correct output :(

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

        Sorry, the I actually gave you the wrong input, the first line should be 5 2 2

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

        1 3 isn't correct btw, it should be 1 2

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

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

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

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

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

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

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

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.

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

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

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

Fake , fake everywhere ..

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

How to solve E?

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

Who dis?

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

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

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

    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

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

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

When system testing will start?

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

    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

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

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

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

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

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

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

    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.

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

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

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

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

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

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

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

    koil (save the name to remove )

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

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

    Not for all...:( :(

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

      It's because C question was Tricky one :)

      Contest was solely based on A and B questions for most of the people.

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

Test 66.........

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

Got to hate getting TLE for using cin instead of scanf

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

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.

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

TLE on B? What is this dude?

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

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

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

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.

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

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

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

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

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

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

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

Why TLE? http://codeforces.com/contest/796/submission/26277280

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

    for cin, cout use these two lines in front of main: ios_base::sync_with_stdio(false); cin.tie(0);

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

      The core of the task consist in using these "two lines in front of main: ios_base::sync_with_stdio(false); cin.tie(0);" with cin,cout?

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

        Or you can use old, fast scanf and printf :/ I also got TLE on that problem :/

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

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

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

Failed Test 64 :-(

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

Why?

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

why system testing does not finishes?

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

    Am I only one who couldn't access codeforces for about 5-7 minutes?

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

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.

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

    Really this problem shouldn't be in CF. Today I will become a pupil :'( :'(

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

    I've solved with cin/cout (1185 ms)

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

      You have 

      ios_base::sync_with_stdio(0);
cin.tie(0);

      In your code!..
      But this shouldn't be a problem in CF. Right Algo should get AC :'(

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

        this is very common trick and it known by everyone who use cin/cout :)

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

      What I really meant was that I didn't expect the entire purpose of the question to be testing fast I/O...

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

Slowest System Testing Ever.

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

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

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

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

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

It's time to eat breakfast.

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

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

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

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

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

They removed bots !

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

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

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

    They should have made that test #1 for faster testing :D

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

    I used cin/cout in B and got AC!

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

      How? I used too and go TLE, with scanf it passes tests

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

        Use this in main() to avoid TLE due to I/O!

        std::ios::sync_with_stdio(false);
cin.tie(0);
        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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

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

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.

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

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

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

      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.

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

        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.

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

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 ?

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

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?

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

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

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

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

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

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

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

    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.

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

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

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

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

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

Is problem C in this contest updated ?

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

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

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

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

      → Reply