vovuh's blog

By vovuh, 9 years ago, translation, In English

Hello, Codeforces!

5th august 2015 at 19:00 MSK Codeforces Round #Pi will take place for second division participants. Participants from the first division are able to participate out of the contest.

This is my first round on Codeforces. I hope you will enjoy the tasks and this will stimulate me to prepare new rounds! Wish you quick Accepted verdicts and successful hacks.

I want to thank Michael Mirzayanov (MikeMirzayanov) for wonderful platforms Polygon and Codeforces and for help in preparing the tasks, Maxim Akhmedov (Zlobober) for help in contest preparation, Maria Belova for translation statements to english, and also my friends Danil Sagunov (danilka.pro) and Vitaliy Kudasov (kuviman) for solving the tasks.

Participants will be given six tasks and two and the half hours for solving them. Scoring system will be announced closer to round start.

UPD: Scoring: 500-1000-1500-2000-2500-2500.

UPD Editorial

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

| Write comment?
»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?

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

    Maybe because it's round 314.

    As a remainder PI = 3.1415...

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it -7 Vote: I do not like it

      Oh, it seems so :) I thought that round #314 will be held after Pi-round, but I was wrong.

      P.S. Thanks for clarifying. Perhaps, I would not participate in this round because Pi-round sounds like a Math-round. And I'm weak at math :P

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

        So, next PI round will be at 3141 th contest ... about 3000 rounds later :v :P

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

          Looking forward to participate in that Round :)

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

            Well, that would be more than 50 years from now. So, I don't want to miss today's Pi round. Let's hope that, we can see our grandchildren participating in a CF Pi-round :P

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

              Too bad ;( We lost "Round #e" (271). I love "e" more than "pi".

»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Hopefully there will be interesting and original math problems!

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

    What is the point of hoping for something like this; this is not IMO. Instead, you should be hoping for an interesting and varied problem-set — one consisting of other things as well.

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

      Because it is Pi round, hope for comp geo :O

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

nezt PI Round #3141 ?

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

Hello! Should I pronounce your name as Pi-kachu?

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

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

    I like this picture very much but what does it mean here??????????????? :|

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

      this contest prepared by P1kachu :)

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

        Oh I realized :( Thank you for your answer :) Nice picture ;)

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

          welcome~ hope you have a good contest!

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

    so cute ^_^

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

I think I'll skip this one and wait for Codeforces Round #Tau

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

Is it a rating round?

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

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

    Nice try Internet Explorer(or Edge)... Very nice try...

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

      Speaking of internet explorer reminds me this pic:

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

    Codeforces Round #FF also instead #255.

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

W<...

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

Maybe there will be a problem about circles ? :-)

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

So this contest will be all about math problems? (#Pi)

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

I think that this round shuld be irracionally long. Lets say 3h 8m 30s or 3.14h :)

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

i'm thinking what will a Codeforces Round #i be like... i'd be imaginary for sure :D

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

"Wish you quick Accepted verdicts and successful hacks." — interesting combination. To hack successfully, I need to lock a problem. Then someone hacks me (according to your wishes) and I can't correct my solution because I've locked it before. Very sad scenario.

Anyway, have fun everybody :)

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

    paradoxical :p

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

    What bothers me usually is when authors wish high ratings for all of the participants :-/

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

      How does Tourist get rating rise?

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

        Well, I assume he wins contests.

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

          You get rating rise when you perform better than your expected position in a contest. Tourist's expected position=1. He can't be better than 1. Yet, he gets rating rise. Am I missing something?

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

            I really do not know how the rating works, but I guess that expected position doesn't have to be an integer. He'd get precisely expected position 1 if he were to compete alone, any participant added should change his expected position a bit, but in the end it probably stays in the interval [1;2], so getting 1 is the only way to score better than his expected position :)

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

    So lock in the last 5 minutes, and spend 2hr 25 minutes before that making sure your answer is correct :)

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

    You solved C in 3 minutes!!! What is this sorcery?

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

      totsamyzed had A after 2 minutes (1:56). I was ~80 seconds slower in task with roughly the same amount of code needed. It doesn't look like sorcery.

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

why 2:30 ???

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

So i guess in each of the problems today we have to be introduced with the person "Mr. PI" :D :D :D

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

when you are wishing for some body successful hacks you are wishing for some body else unsuccessful

submits!!! i don't think it's a good wish!

thanks ;)

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

2.5 hour = 6 problems? So I guess P1kachu prepare a nice problem F for us to solve...

»
9 years ago, # |
  Vote: I like it -50 Vote: I do not like it

define in_round_#pi ++

int RP;

int main(){ while(RP)RPin_round_#pi; return 0; //By the way,thanks to writer }

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

Round #404 will be declared as round #Error or round #NotFound

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

    Nice idea !!

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

    numbered rounds of Fibonacci numbers: round #Fibonacci

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

      P.S. Next Fibonacci round is 377 *

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

      now I found out first comment in blog create other comment first comment: "I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?" other comments also are about name of contests

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

That proud moment when a blue coder prepares a CF round :D
Hats off !!! keep it up :D

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

This is the first contest i join ever on codeforces :)

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

It has been a long time since the last Div2 contest.. It's obvious that the number of registrants is very large this time and people are eager for such an event.. Let's enjoy

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

So since there are 6k+ participants, on a scale from Google.com to contest.Bayan.ir, how down is Codeforces.com going to be ?

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

6278 people registered which is more than 6274 people registered for good bye 2014

out of 6278 registrants 935 people are unrated

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

The first round was written by Expert user that I have ever participated!

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

What on earth is pretest 19 in Problem E?

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

    I guess you're not finding the bridges correctly. I got WA 19 because of a caveat in my solution, I only check for edges that definitely are on the shortest path ONLY from the start and the end, but there could actually be bridges in the middle of the path too. An example edge formation , start = 1 , end = 8 : 1 2 1 3 2 4 3 4 4 5 5 6 5 7 7 8 6 8

    The edge 4 5 is definitely on the shortest path since it is a bridge in the shortest path graph. Hope it helps .

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

      No, I think I took care of that. Oh well, will wait for the editorial for E.

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

Problem E with modulo based hacking was pretty funny.

I had a generator that generates a input for any mod. Some guy from my room sent his solution in the last moment to make sure that I can not hack him. :)

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

    Is there a solution without modulo calculations?

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

      What is a solution with modulo calculations?

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

        @ikbal can you show how you made the generator?

        Also I used doubles to calculate number of paths. Paths can be at most 10^500 which fits in a double.

        With modulo calculations, you just mod this number continuously.

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

        We build DAG where there is a directed edge (u,v) if there is an edge (u,v) in graph and dest[s,u]+dest[u,v]+dest[v,t]==dest[s,t]. Then we say that edge (u,v) is a bridge if number of ways (s,u)*(v,t)=(s,t). But this values are large, so I took them by modulo

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

          Instead of counting number of ways you can change this DAG into undirected graph (all edges become bidirectional) and just find all bridges in this graph.

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

            Can you please explain why this is correct ?

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

            I got a WA using an undirected graph. Can you explain the proof of this?

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

      Yes, there is. And not only one.

      1) You can find all edges that can be in shortest path and then find bridges in this graph.

      2) Find all edges that can be in shortest path. Then realize that we are on this edge in fixed interval of time. Edge is in all shortest paths if its interval doesn't intersect with other intervals. (It's my solution, you can read it).

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

    Was my solution also hacked because of modulo? It would be quite strange since I used both overflow hash & modulo. I even changed modulo after getting hacked, but still got WA (on your hack).

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

      Just create two paths one with 10^9+7 and one with 2^64 ways. If we merge them together from their ends by an edge new long path would have (10^9+7 * 2^64) ways.

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

    What sense not to be hacked if solution is wrong?

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

      Because usually it's impossible for problem setter to create tests against every modulo.

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

    I'm wondering if his code gets accepted after all. :/

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

Finally solved C with 2 seconds on timer :( That's embarrassing.

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

Spent 30 minutes trying to find the problem with this attempt at problem C. Can someone lend a hand?

http://pastie.org/private/mmg81uzwfniinmxabqa2rw

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

    k * k overflows.

    EDIT: Result (num) could overflow too.

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

      It returns 0, regardless of input. I didn't even have time to consider overflows haha.

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

What was test case 5 of D? I used a solution that kept track of valid intervals where battleships could be placed: if bob's shot interrupted an interval, then I split it into 2 intervals, and for each interval I calculated IntervalSize / SizeOfShip. If this was less than NumberOfShips, then I printed that index and stopped the program. At the very end I printed -1 and ended to catch the case where it is undeterminable. What is wrong with this approach?

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

What's the intended solution on D?

I tried keeping a sorted vector of pairs, representing all uninterrupted segments where you can place ships. Every time you fire a shot, you find the segment that shot is in and split the segment in two. Used binary search to make the segment searching faster, but my solution was wrong on case 5.

Is the idea wrong, or did I mess up my implementation?

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

    How do you calculate the number of ships that can be placed into one interval?

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

      interval size / size of ship

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

        Yeah, that's wrong. They must be non touching. I saw this only after a lot of wrong submissions :D

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

      Let there be maximum of x ships of size a in the interval of size n.

      Then x*a+(x-1)<=n

      hence, x=(n+1)/(a+1)

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

    Idea is ok. Alternative solution is to do binary search over result.

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

    I processed the queries from last to begin and kept a disjoint set for the connected parts and instead of splitting merging.

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

    Apparently, you can't have 2 ships RIGHT next to each other, so when calculating number of ships possible in an arrangement, you had to make sure you left 1 space in between each(so you had to add extra logic for both inside the interval, as well as between consecutive intervals.

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

    My solution was binary searching for the answer. You fix the amount of shots fired then you mark those cells. Once you've marked some cells as shot you can get the maximum amount of ships that can be placed in O(N) using greedy approach.

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

    1) Let's find the asnwer by binary search (answer — k) 2) Each iteration of search we will check by function CHECKING that says TRUE if we can't place all ships with k turns and FALSE if we can. If True, you should make left_border=k, and if False — right_border=k+1 3) How does CHECKING work? Make a vector of field and fill it by 1(free place) and 2(place where Bob shooted). Then in cycle just greedy fill it by ships from left to right and calculate its total. Return total<number_of_ships 4) PROFIT!

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

Eh, I believe the "two weapons cannot touch" part in D should have been explained more clearly... I was thinking it just meant a cell cannot belong to more than one weapon (and I guess so did everyone getting WA on pretest 5).

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

    The same thing happened with me. I spent 2 hours making numerous test cases and my code was working for all of them.
    So , after the contest , upon asking adurysk I realized that two ships could not "touch" meant they couldn't be adjacent . Facepalm

    Needed to change (N/K) to (N+1)/(K+1) to get it Accepted :P

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

      It was written both in statement and in input section. How could it be explain more clearly?

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

        It just said "the ships cannot intersect and even touch each other"- it would be better if the problemsetter explicitly mentioned that you cannot place two weapons right next to each other.

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

          The author separately mentioned intersecting and touching, shouldn't that be a hint that these describe two distinct situations?

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

The round was awsome. I enjoyed a lot E and F. Congrats for the round. Also , was F a dp in O(N^3*K) ?

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

Can someone help how to solve C ?? :(

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

    two maps

    m1[x] = y <=> count of subsequence of length one finishing at x equals y

    m2[x] = y <=> count of subsequence of length tho finishing at x equals y

    So, we getting num a. Then ans += m2[a/k]; m2[a] += m1[a/k]; m1[a]++

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

      sorry but i didnt get u ??

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

        If we've got num a, how many subsequence of length one finishing at a? As many as subsequences of length two finishing at a/k. So ans += m2[a/k]

        Analogycal, how many subsequences of length two finishing at a? As many as subsequences of length one finishing at a/k. So m2[a] += m1[a/k]

        m1[a]++ because we've got new subsequence of length one finishing at a.

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

What was the idea for keeping track of the number of shortest path? Does it use Dijkstra?

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

Can anyone who solved F explain a solution? The problem seemed like hell to me :D

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

    DP; you put the pairs from largest to smallest. States are "the blocks you put so far are in the interval [i,j]". There are just 3 possible transitions from any state and you just need to check if any in/equality becomes invalid for each of them.

    The simplest implementation is O(KN3), which definitely passes.

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

    dp[left][right] — in how many ways can we fill blocks 1... left and right... 2N with small numbers (numbers lower that those left for interval left + 1... right - 1. We must consider 3 cases: adding two new equal numbers in left + 1, left + 2, or in left + 1, right - 1, or in right - 2, right - 1. For all 3 cases we must check is everything would be ok for them — those two places are equal to each other but lower than remaining places in left + 1... right - 1.

»
9 years ago, # |
Rev. 4   Vote: I like it -7 Vote: I do not like it

OMG i forgot to remove debugging code and the stderr flushes made me TLE on problem D.... ;(

for(auto i:my)cerr << i.first <<":"<<i.second<<endl;

http://codeforces.net/contest/567/submission/12367438

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

    use tab indent to understand your bug!!

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

      There are no bugs there, its just that i'm writing a bunch of endl's to cerr (which i used while working in the problem), and i didn't remove them before submitting....

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

Can anyone explain me how to solve problem D??

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

    One way is to find result by binary search. Then, we mark some cells as blocked and we need to count maximal possible number of ships. Say if you need more explanation.

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

      Yeah can you elaborate it more??

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

        which part?

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

          Here binary Search will be applied on what?And then How cells can be marked as blocked??

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

            Binary search on result — size of prefix of given blocked cells. Cells can be marked as blocked with array of booleans. Then we iterate from 1 to size_of_grid and calculate number of ships we can have.

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

    The rough idea is to maintain the maximum number of ships you can put on the board.
    Notice the fact when you hit a spot, you are splitting an interval(between 2 previously-hit spots) into 2 intervals. With that, you can calculate how many ships can be put on the original interval and on these new 2 intervals, and update the number we're maintaining.
    Use std::set to store previously-hit spots.

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

    Let's use a some set, which will keep disjoint segments.

    Also let's keep some value T which means what is the maximum number of ships we can arrange on a board.

    When we add a segment to the set, we must increase T by some value x, which means the maximum number of the ships we can arrange on current segment. This number is equal to (len + 1) / (a + 1) where len is a length of the segment and a is the length of the ship

    At first let's add segment (1, n) to the set.

    So, when the cell c is coming, let's find a some segment(l, r) which keeps c (l <= c <= r). We decrease T by (len(l, r) + 1) / (a + 1).

    Then we add segments (l, c - 1) and (c + 1, r) to the set and increase T by appropriated values.

    If we processed current operation and T is less than k, answer will be equal to the number of operations we processed already.

    For keeping segment we can use a simple set of pairs. My solution: 12365410

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

      Wow, I used to write a segment tree in that problem, but your solution is much more simple than mine, thanks!

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

        Of course, you can use segment tree, but I think set is the simplest one.

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

Nice problems vovuh! I like C and F especially. Hope to see more rounds from you.

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

I got stuck (kept failing test case #13) in problem B. Embarrassing, but this was my first contest. Here is my solution:https://ideone.com/G5fuEl Can some one give me any ideas? I can't sleep, keep thinking about it :|.

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

    You can view small inputs after the contest. Scroll to the end here: 12373900

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

    In the if at line 29 you should add :

    p[abs(arr[i])]-=arr[i];
    

    This is because the person left, but you never marked him coming in. So in the beginning of the iteration you added arr[i], marking him leaving, once you understand that he's been in all along you should make up for his coming.

    Feel free to ask questions :)

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

      Just one question I had in mind.. did you guys used some debugger when you were starting out?

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

        Debug output is usually the fastest way. Just add some safeguards to your template to prevent it from working on the server side:

        #ifndef ONLINE_JUDGE
        #  define LOG(x) (cerr << #x << " = " << (x) << endl)
        #else
        #  define LOG(x) ((void)0)
        #endif
        

        ONLINE_JUDGE is defined in the Codeforces environment.

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

    Your if "if(p[abs(arr[i])]<0){" should be done at most once for every arr[i]. You have WA for test

    3
    - 5
    + 5
    - 5
    
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea of E?

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

    My solution is to dijkstra 2 times, one from s and one from t

    for each edge u->v if dist(s->u) + c(u,v) + dist(v, t) == dist(s, t), u->v may be a "sure" edge

    Take all those edges and eliminate the direction, we can find the bridge by simple DFS.

    Note that there may be multiple edges between two vertexes. I failed E during the contest because of that :(

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

In problem C, what would be the answer if k=1 ??

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

    You could easily count how many times a given numbers repeats using a map, then it's basically C( [amount of repetitions of this number], 3) which is equal to [reps * (reps-1) * (reps-2)/6] when you simplify the formula.

  • »
    »
    9 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it
     for(int i=0;i<n;++i)
            {
                scanf("%d",&t);
                if(k==1)res+=(a[t]*(a[t]-1))/2;
                ++a[t];
             }
    cout<<res;
    

    For k=1 this program gives correct anserws. PS.a is map<long long,long long>

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

public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { String s = in.readLine(); String[] ar = s.split(" "); if (ar[0].charAt(0) == '+' && !t[Integer.valueOf(ar[1])]) { cur++; t[Integer.valueOf(ar[1])] = true; } else if (ar[0].charAt(0) == '-' && t[Integer.valueOf(ar[1])]) { cur--; } else if (ar[0].charAt(0) == '-' && !t[Integer.valueOf(ar[1])]) cap++; cap = Math.max(cap,cur); } out.print(cap); }

my code above for problem B is incorrect, because the bold line, without that line, the code is correct. But the number assigned to people is unique, why can someone take same number twice?

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

Wow the problemsets are really nice. It's hard to believe that it's prepared by a blue coder.

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

    That's because, this rating shows the measurement of competitive programming skill which is different from problem inventing skills. There are many cases where enough knowledge doesn't help the subject to do better in competitive programming.

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

Was this contest Unrated???

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

Can someone point out the mistake in this code?

Problem D

Thank you in advance.

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

    it=s.upper_bound(mp(mov[i],-1)); should be it=s.upper_bound(mp(mov[i],n+1)); in order to find the intersecting interval after decrementing it. If you have an interval that starts at mov[i], upper_bound will return it and decrementing will miss it.

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

      Thanks a lot. Silly mistake, could have been avoided during the contest.

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

While solving E, i had to keep track of number of shortest paths passing through a particular edge. But this value can exceed 10^18. I used hashing modulo 2 large primes to keep track.

Is there any other (deterministic) workaround to this?

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

    Yup, Bridges in the "shortest path graph" are guaranteed to be on every possible shortest path.

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

used coordinate compression in c :P

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

It's just div 2, but I'm very happy anyway. Nice problems! :D

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

Thanks for a great contest!

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

Hello, this is my first contest. I'm just curious about one thing : when does the rating change after a contest?

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

    Hello, dear newcomer! You should now that right now Mike Mirzayanov, Zlobober and others are sitting at the round table and hotly-debate everyone's rating change. It takes a lot of time, you know. It was my not serious thought of things when I took part in my first contests. Now I think, that the question of looking for cheaters is hardtime. Maybe anyone know another 'why'?

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

      Thanks for the answer, I expected it to be more automatically updated. Great to know that they look for cheaters.

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

    Mia rating

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

Your problems are really amazing. Thank you :)

»
9 years ago, # |
Rev. 5   Vote: I like it -7 Vote: I do not like it

Thank you for the contest. Can you update top 5 contestants as well :D ?

Update: Down voters, so you don't want to see your name when you are in top 5?

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

Can anybody help me check my code of problem E: http://codeforces.net/contest/567/submission/12382102

Thanks!

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

    You haven't taken into account multiple edges while checking the YES condition

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

      I think my code has covered this case. Can you give me a test case to illustrate it?

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

        Yeah you are right you have taken that into account.

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

    Deleted

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

Could someone explain this testcase (which is the 37th) of Problem E?

10 10 1 10
1 5 178
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157

The output is NO for all edges except the two that lie on the unique shortest path of length 378, for which the answer is YES. What I don't understand is why the answer for all other edges is NO. Let's take for example the path (1 — 5 — 3 — 10 ) of length 470. The first and the last edge could be reduced by 93 to give a path of length 377 in which case they lie on the unique shortest path. I probably misunderstood something in the problem statement. Thanks in advance.

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

    I had the same problem.

    In the statement it says The road is directed from city ai to city bi. In this test case you can't go from 5 to 3 and therefore the path (1 — 5 — 3 — 10) doesn't exist.

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

It's my first contest in codeforces and I enjoyed it very much. Wish your next round,and I hope I can do better then.

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

could someone tell me why this solution gives TLE for problem D? It's run in O( m log(m) ) 12387839

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

I am not from the top 5, but I love to see the winners' names in the updates :)