Zlobober's blog

By Zlobober, 9 years ago, translation, In English

Hi everybody! There will be a Codeforces Round for both divisions today at standard time set up by me.

My teammates from ICPC team Moscow SU Trinity sankear and malcolm helped me a lot while preparing this round, also there were lots of useful tips and advices from MikeMirzayanov, applause for them. English translation was made by our veteran translator Delinur.

As usual, there will be five tasks for two hours. The scoring will be announced later.

See you on the round! I hope that each contestant will be able to find something nice in ongoing problems.

UPD: Scoring is standard.

UPD2: Due to technical issues the round is delayed by 15 minutes. We are sorry for an inconvenience.

UPD3: We are sorry for an inconvenience with the task Div1-D. The pretest #16 wasn't satisfying the constraints n, m, k <= 200000. The system testing for the first division will be delayed. If you think that you were affected by this test, you may write me a message and we will make this round unrated for you.

The system testing for the second division will happen shortly, as usual.

UPD4: System testing is complete. Congratulations to the winners!

Div1:

  1. piob

  2. PavelKunyavskiy

  3. dreamoon_love_AA

  4. mnbvmar

  5. aid

Div2:

  1. happyBirthDayBeni

  2. ExfJoe

  3. _0029

  4. tudort

  5. kill-z

UPD5: the English editorial was added.

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

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

First contest without saying thanks to Max Akhmedov (Zlobober) :)) ;) :D I'm really looking forward to participate in this contest ! \:D/

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

Wait for a div1 round for a long time! I can't wait any more!

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

Waiting...

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

this contest is for Iran Good Bye 1393

happy new year!

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

    actually Good Bye 1393

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

    happy new year! :D ( 4 shanbe sooriam hast :-P )

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

I love your contests,very nice! Zlobober ,you are my idol :P

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

I missed CF' rounds. It is good to see new round. HC && GL to everyone :)))))))))))

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

at standard time T_T...

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

Great thanks Maxim Akhmedov Zlobober preparing the contest :D

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

"Moscow SU Trinity sankear и malcolm"
Please change this to
"Moscow SU Trinity sankear and malcolm"

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

    Done, thanks.

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

    All non-russian-speaker codeforces users became to know that "и" means "and" so there's no problem

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

My first Contest! Yay!

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

    Your user name and the way you comment sounds fishy. But I'll just let it slide.

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

Finally ... we are so thirsty for contests. I think that I will not be able to live without codeforces.

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

This is the first time I do with contest Div.1. I hope will get some interesting in this contest.

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

    what is difference between div 1 and div 2?

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

      If your rating is >= 1700, you will compete in Division 1. Else, in Division 2.

      Both divisions have 5 problems but Division 1 has harder problems. In fact, usually the first 3 problems of Division 1 are same as the last 3 problems of Division 2.

      Here's more information regarding rating.

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

what is the diffeerence between div1 and div2

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

    Hey, what are FAQ for?

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

    lets define function F — number of different characters between two strings, then we could do something like that:

    difference = F("div1", "div2") // should be 1

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

Why all of these peoples speak english ?

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

I missed many CF rounds becoz of internet & load-shedding problem..Thanks @Zlobober for this round. Hoping for nice problems..Wishing Good Luck & High Rating to everyone !! :)

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

div2终于来了

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

Exactly on 4shanbe-soori!

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

Thanks for contest. This contest is on our(Iranian) National celebration ( charshanbe suri).

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

"Before contest" countdown actually doesn't correspond to the time on the timeanddate.com, the difference is about 2 minutes. (I noticed because I realized that my PC time is not equal to the codeforces one, but I have synchronization enabled :)

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

Delay

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

time extended

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

Wow added 15 minut

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

15 minutes delay, why?

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

Forgot to register, why God why ? :/

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

Hi, I could not register in time because of the technical issues (and i logged in late). It says div 1 registration is still open but div 2 is closed? Edit: its open, thanks!

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

The contest is not started right time.15 minutes late will be started.

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

Some people might have thought that "in at most an hour" means at least half an hour. I would suggest postponing it further to start at 19:00, so that no complaints can be made.

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

It's too late in China. 8 hours later I have to have class...

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

I was late to join contest. Therefore I entered into the codeforces to see about the condition of my friends. But now I can see it is 15 minuets late again!!! Now I can participate to the contest. First time the delay of codeforces becomes good for mine. :-)

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

The contest is not started right time.15 minutes late will be started..

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

"We have to upgrade infrastructure...

Let's do it 5 minutes before the contest!"

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

I must go to sleep because I will go to school in 5 hours later.The sadness of UTC+8.

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

tqvenii deda movtyann D amocanis 16 testis shemdgenels movutyann suyvelaperiii,2 saati tyvila gvawerinebb xalxss tqvenii suyvelaperi movtyan,mtestavidan dawyebuli mtargmnelidan damtavrebuliii,puiii

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

Usually after contest there are lot of guys who complain — Why there were no maxtest among pretests?

And today, in order to prevent such comments, authors decided to put into pretests not only maxtest, but even test larger than maxtest :)

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

It was Good contest but I wish it had more time

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

Any hints for Div2 B?

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

Div2 C: Time Limit Exceeded in pretest 11.

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

How to solve DIV2-D/DIV1-B ?

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

    Let's reverse a problem:

    Points a and b are connected only if distance between them is smaller than sum of their weights.

    In this case, we can imagine one point as interval [x - v, x + v].

    When two intervals overlap, corresponding points are connected.

    To find a result, we need to find the largest subsets of intervals that are not connected (in original problem — the largest where every two are connected).

    Why do we need reverse problem? Because it makes everything much more easier. Every point correspond only with one interval (in original problem — with two) and simple sweep from left to right will do whole job.

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

    First of all, if x_a < x_b < x_c and a connected to b and b connected to c then a connected to c, so if we have connected sequence of points it's a clique. Now we should find largest connected sequence of points. Let us consider the points with weights as segments with length as two weights and centered in point. We are looking for max set of non-intersecting segments. Here we get events: starts end ends of points. Sort them and go from left to right. When segment starts, answer for this segment (size of the max set of non-intersecting segments from segments from most left segment to segment under review) is max from already closed segments plus 1. It's just a variable, which is updating then segments closes. 10322276

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

    Sort the point by the coordinate. Consider 3 points i, j, k (i > j > k). If there are edges (i, j), (j, k) then there'll be also edge (i, k). Because:

    x[i] - x[j] >  = w[i] + w[j]

    x[j] - x[k] >  = w[j] + w[k]

     <  =  > w[i] - w[k] >  = w[i] + 2w[j] + w[k] > w[i] + w[k]

    <=> there is edge (i, k)

    That means if we add i to the clique which contains j, when we'll have a new clique.

    Now everything left is a simple DP with Fenwick tree :D You can check my submission for more detail :D

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

      :D This is so overkilled.

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

        That's how I made it too, and it took me about 10 minutes :))

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

          I also spent a long time thinking about the meaning of that formula. Suddenly I realize that they are just circles center at xi with radius to be wi

          And answer is the maximum subset of circles that doesn't intersect with each other =)

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

      QAQ , Consider 3 points i, j, k (i > j > k). maybe it is x[i]>x[j]>x[k] ???

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

        Sort the point be the coordinates. Then it's the same :D

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

      Its a lot more intuitive than converting the problem to counting non-intersecting circles, according to me.

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

Is the contest unrated for div2 participants??

Really hope not!

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

    Contest is rated for Div2 participants.

    Contest is unrated only for those Div1 participants who write me a private message shortly.

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

    Why would it be unrated?

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

      You can get the answer at UPD3 :)

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

Huh, 67 people did problem with FFT :o, nice.

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

    I solved it with brute force. Ran max test in 1.6s in Custom test.

    UPD: It passed sys test.

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

      Yyyy, seriously xd? Just check every occurence naively xd? I hope it's not offensive, but I really hope that this won't pass :p.

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

        It's not very naive. I did it with bitmasks, so runtime is T(N2 / 32). This solution does not depend on any property of the test, so unless custom invocation runs faster or I made some stupid mistake, it'll pass.

        This problem reminds me of 472G - Design Tutorial: Increase the Constraints. They feel very similar to me, with solution being FFT (which I don't really know), and looks possible to solve with bitmask stuff.

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

          What is the meaning of T(), I have seen it a few times ago?

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

            T is number of step, meaning it doesn't ignore constant factors.

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

              Huh, funny, I didn't know this. Is it formally defined or is that auxiliary notation introduced for competitive programming purposes?

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

                I think I have seen them in OCW videos, though not sure :P

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

                T(n) is used as running time on problem of size n in "Introduction to Algorithms", so I think it's not limited to CP purposes.

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

                  I think that this is something different. T(n) as you described now can be equal to O(n2), it is not consistent in any way with the meaning of T(n2 / 32) you used before.

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

                  Disclaimer: I'm always confused by these things, so I may be speaking non-sense.

                  Since O(N) is upper bound function, we can have f(N) = N = O(N) = O(N2). And in here T(N) means true value of runtime (?) So what is wrong with T(N) being equal to O(N2) ? For me, this only means that, in most cases, we should use Θ or T instead of O.

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

                  What I'm saying is that you wrote T(n2 / 32) while you should have written sth like T(n) = n2 / 32, because n is T(n) means size of the problem and n2 / 32 ain't one.

                  By the way I think that Θ would be more appropriate here, because for me T is used rather to write down some equations for complexities like T(n) ≤ Θ(n) + T(3n / 4) + T(n / 5) like in algorithm of finding median. T could be used as O(sth) as well, doesn't have to give strict bound.

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

                  Ok, I see the problem now. Thanks! :)

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

              Thank you, and Swistakk too! :)

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

            I guess the most common notation of complexities are
            O for upper bound, Ω for lower bound, and Θ for strict bound

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

      If you used the bitmasking optimisation, it's not really brute force. It's as if you said you ate pancakes: yes, the meal is called that, but pancakes themselves usually make up just a small portion of the meal :D. That you used a clever trick to make a brute force algorithm run fast, it doesn't mean you solved it just with brute force.

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

    I am surprised that this problem was used for today's contest; its solution is described at e-maxx.ru (one of most popular sites with algorithms for competitive programming in russian) in article about FFT, so it should be well-known for russian-speaking participants.

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

      As for me, it's completely unclear how the problem is related with FFT... So existance of solution on the internet does not help much

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

Div1.D was FFT, right? I don't know FFT but knowing what problems can be solved using it, I think so.If no, how to solve it? :)) all the problems were nice except of div1C which would be nice if it hadn't had the case with self loops.I solved it fot the tests which didn't have that case but, of course, I didn't get any points...

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

    What is your solution? I wrote Euler path and for my solution it doesn't matter if graph has self-loops.

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

      Woow, it seems that you have a very nice solution.In this case, C was very nice too :)) My solution was some strange thing, sth like this: I was making a bfs, building the tree and the edges out of the tree were chosen random(or from x smaller to y bigger) and I than, using these edges, I was fixing juste the sense of the edges of the tree, from leaves to the top.Can you please explain your solution?

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

        Firstly, link all vertices which have odd degree. Now graph has Euler cycle. Suppose it's c1, c2, ..., cm. Then we output edges . But there is a problem when graph has odd number of edges. In that case we need to add edge .

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

          Thanks :) I understood and the idea is preety cool

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

          Actually, there's a bit more. Consider a test

          6 4
          1 2
          2 3
          4 5
          5 6
          

          Here 1, 3, 4, 6 have odd degree. If you connect 1-3, 4-6, then you'll have to add two more edges to deal with components with odd number of edges. However, 3-4, 1-6 yields a single component of size 6, so this is better.

          In general, it is optimal to connect all odd-degree vertices in such a way that all components involved merge into a single component.

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

            But there is only one component in the graph.

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

              Indeed, it was easy to miss something in this kind of statement. Also, the announcement said something about "the construction should not be connected in any sense", which I fail to understand in this case.

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

                They probably meant that your orientation of the edges should not guarantee strong connectivity or something like that.

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

            The graph is connected.

            The cables are put so that each computer is connected with each one
            perhaps through some other computers.

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

          Other possible solution, without Euler cycle, after linking verticles with odd degree: in DFS tree, make all edges that are not in the tree go up (towards the root). Then, for each verticle, starting from the bottom, direct the edge to the parent either up or down, such that # of incoming and outgoing edges is even. The only possible case where we need to add a loop is the root.

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

    Yes solution for Div1.D is FFT.

    1) Iterate over 'A', 'G', 'T', 'C'

    2) Let's denote current letter c. Construct new string a' and b': a'[i] = [exist a[j] = c and |j — i| <= k], b'[i] = [b[i] == c].

    3) Now lets apply b' to a' with offsets 0, 1, ..., n — m and calculate scalar product for each offset. If the value of scalar product is not equals to the number of ones in b' than offset is bad.

    4) If offset is not bad for all four letters than it's good.

    Third step can be processed in O(n * logn) time: let's duplicate string a', reverse string b and multiply them. Now in positions from m — 1 to m + n — 2 we have the scalar products that we need. Multiplying we can do using FFT.

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

      Hi, may you elaborate it a little bit?, please

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

was difficult. can't solve Div2-C, what is needed there? map?

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

    I answered queries in reversed order with disjoint set union, but I think that there is simpler solution.

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

    I used multiset for distances between cuts and set for coords of cuts

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

    I used segment tree to solve it, I hope it will pass. The idea is for each column to store the maximum width of a rectangle using this column. It is the same for the rows. When I was reading the codes of people in my room, I saw solutions with sets or priority queues. Can somebody explain such solution?

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

      My solution:

      set HCut, WCut — coords of cuts (at first (0, h) and (0, w))

      multiset DistancesH, DistancesW — distances between adjacent cuts (at first (h) and (w))

      If we've got query (H x), we:

      1. Search in HCut iterators, pointing at two elements which less and greater than x (We always can do it). Suppose, we found it1 and it2 (*it2 > *it1).

      2. We delete from DistancesH (*it2) — (*it1) and add (x-(*it1)) and ((*it2)-x)

      3. Print max(DistanceH)*max(DistanceW)

      4. Add to HCut x

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

        Hi, can you please tell me whats wrong with what I've done? I got a TLE on this: http://ideone.com/SHyKGR
        My algorithm is the same as what you've suggested. Thanks for the help in advance.

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

          lower_bound() is too slow for set operation because set<>::iterator ain't random access iterator

          you can first insert pos into the set, then go up and down a bit.

          10332363

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

          You can also change lower_bound(XXX.begin(),XXX.end(),pos) to XXX.lower_bound(pos). It will get AC.

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

          Oh so my lower bound was doing a linear scan. Thanks, guys. I got it accepted by changing that :)

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

      The smartest solution I saw someone using was using DSU.

      You could solve the problem backwards by merging X-axis and Y-axis intervals and updating the largest intervals if the merged interval is larger than the current one.

      The algorithm itself is O(nα), isn't it?

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

    thanks 4your ideas.

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

First time of playing hacks, so interesting.

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

Btw you can check your div. 1 A,B,C solutions in upsolving of div. 2 contest.

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

    It's also tested almost instantly there, looks like all submissions are already tested and results are cached.

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

i know its silly -> a little hint about A-Div2 ?!? so, this is math , no programming -_-

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

    here is pseudo-code for Div2 A

    while(a>0 && b>0) { if(a>b) { res+=a/b; a%=b; } else { res+=b/a; b%=a; } }

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

It was nice. Thank you.

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

Div2-B — TLE54

Div2-C — AC

It is sad when you can't solve easy tasks:D

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

I can't understand this test in Div2B: 2 xy zz

Why is the answer: 1 1 2 ?

We transform strings as xy->yx and have: yx zz

And the Hamming distance IS THE SAME!!!

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

Check out my crazy div. 1 B solution, lol 10326839

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

How to solve Div1 B?

Update: I missed this comment where tom describes his idea.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it
    • Suppose we're comparing two points and x1 ≤ x2, then x2 - x1 ≤ w1 + w2, which can be transformed to x2 - w2 ≤ x1 + w1. So, build a pair<int,int> array with the values {x - w, x + w} for all points.
    • Sort that array.
    • Let DP[i] be the maximum clique we can build using points with indices  ≥ i. Let's iterate the elements from the new array from the last one to the first one (from N to 1) then if we're processing index i, we do a binary search to find the first element j such that xj - wj ≥ xi + wi, and set DP[i] = max(DP[j] + 1, DP[i + 1]). The answer will be DP[1].

    Sadly, it took me an hour and a half to figure what to do with the values x + w and x - w (the last step)...

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

      Thank you, this idea seems to be similar to tom's. Instead of DP, a priority queue can be used. Sort the segments by their left coordinate and the queue's top element will be the one with the smallest right coordinate. At each step, pop the top element while it's right coordinate is less that the current's segment left coordinate. Then, insert the current segment and compare the size of the queue to the answer(I just described the algorithm that I always use to find the number of maximum segments that intersect).

      Unfortunately, I didn't figure out the {x-w ; x+w} representation of the points... :)

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

will you post the editorial ?? the problems were really hard for me :3

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

In problem 527B - Error Correct System, what would be the correct output for the case:

4
dbea
bddb

10318065 this Accepted submission gives:

3
1 3

Is it ok? Zlobober

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

      We will add investigate this test and probably add it, thanks.

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

    I also thought on this problem, too.

    Didn't realize why 10315968 got accept until reading this thread. My test case is:

    4
    acbc
    bbaa
    

    I thought the correct output should be:

    2
    1 3
    

    But the below output also passed:

    3
    2 3
    

    The problem says it must be "as small as possible" not just "reducing some".

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

      Will system testing run again with more comprehensive test cases?

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

        Never, for sure! past is past! Codeforces always thinks about future! :D

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

This contest is just a disaster. Problem C in div1 is written so badly. I am just shocked how could the author write such a long dummy boring story instead of just a few lines?

And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!

Because such failure in both C and D, I suggest an unrated contest for all div1 contestants.

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

    The storyline is okay. The world would be boring if every problem has a description like "Given blahblah, you need to find blahblah". The real problem is the key point was hidden in one or two unremarkable phrase, make it difficult to understand.

    I (blindly) guess that the original problem statement was written in Russian and this is a translation issue.

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

      You are right. Russian statement was very clear.

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

    Unrated contest because of long statement? Isn't it too forward? Indeed some people were affected by wrong test, but that is a small amount and most of them ended up with a decent position, so it is not helpful for them to make contest unrated :P

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

    I strongly disagree:

    1) "And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!" — problem D is expected to be pretty hard and most people in Div1 know it, those who decided to try it and actually got a solution are very small amount of all Div1 participants, and those who didn't try it — didn't even realize that there was a wrong pretest. Of course it's unfair for those who've tried it, but an option to unrate their participation is available, so why make other people (like me) who didn't even attempt the problem unrated?

    2) Problem C while a little bit confusing had an amusing story and the pictures cleared it up for me. I think if you read it carefully you would also find it understandable. The problem is very nice actually and I enjoyed coming up with a solution for it even though I couldn't debug it.

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

    I agree with 1st point. I misunderstood problem statement of C and tried to solve a different problem, until I saw the announcement :(.

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

    Like! But I really don't wanna this contest to be unrated. I believe many contestants having the same idea with me.

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

I used to think 40 minutes is the longest time for me to understand a problem...until I spent almost one hour in reading problem C again and again

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

    Hah, yes, that one was pretty confusing, I needed to read this many times too :P.

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

Why you finished testing div2 before starting test div1? We can self test by submitting div2cde and we can message you to unrated if there's something wrong in the programme.

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

    I think that the unrated option is only in case the test for Div1 D affected you and the code for Div1 D cannot be submitted in Div2.

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

      If my ab are wrong and I have submitted d using fft, then I will certainly try to be unrated

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

Finally I know my program of finding Euler's circuit used several times is O(nm). What a sad story.

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

Zlobober why my rate still the same .. is it unrated contest

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

What a fantastic round for Poland! Never seen such performence earlier! :)

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

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... :D/

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

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/

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

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/

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

I have a question about the next contest:

"VK Cup 2015 — Round 1 (online mirror, Div. 1 only)"

Can a Div. 2 contestant take part in this contest?, at least 'out of the competition'?. Thanks.

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

I was afraid to become orange when I finished debugging C 30 seconds after the contest has finished.

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

can i have some help on Div 2 D it gives WA, first sort due to coordinates then the idea is to run dfs from (n-1, ..., 0) considering that (i, j) is connected if (x[i] — x[j] >= w[i] + w[j]) and we know that if (i<j<k) & (i, j), (j, k) are connected then (i, k) is connected and maximize the counter this is my code where is the wrong part ?!

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

During the contest, I thought bitset couldn't be used to solve problem D. Its complexity is , and I thought it would take at least 10s.

However, after the contest, I found it could pass system test actually and took about only 1.5s.

How can it be so fast......

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

I still can't understand what's the meaning of div1C...

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

http://codeforces.com/blog/entry/16996 the problems were nice but the pretest 19 for Div 2 problem B was glitchy. for pretest 19 I got the answer(output) for the minimum hamming distance to be 524. The output given by the codeforces system too is shown to be 524. but then next line i am shown this error :

"wrong answer value presetned by contestant is different from the actual hamming distance: contestant = 524, actual = 526"

even though before this the pretest logs show this:

Test: #19, time: 46 ms., memory: 32 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 1000 bbabbaabbabbabababaabbabbbbbaabbaaaabbababbaaabbabbbabaaaabbabaaaaa....

Output 524 1 2 Answer 524 999 1000

so my output matches the system output yet i was given verdict of wrong answer...

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

    I believe it means the 524 doesn't match with 1 2

    Although you give the correct answer, but the index of i and j are wrong

    EDIT: changing print i+1, j+1 to print ind[i]+1, ind[j]+1 will correct the problem, but result in TLE. The double for-loop makes this approach very slow. The complexity is O(N^2)

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

      i checked other peoples code too they have given answer 524 but the second answer is different from what the system has given but even then their answers have been corrected.

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

        The second line can be different because multiple answers could exist.

        In your case, you answer is wrong. I have corrected it for you in the last post.

        EDIT: To be specific, the minimum value after at most one swap is indeed 524, but exchanging the letter at index 1 and 2 won't achieve the minimum, it was 526

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

Editorial?

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

For div2 C, I just used priority_que and set to simulate cuttings, and got AC.10325360 But I made a data: 200000 200000 199999 V 1 V 2 ... V 199999 I run it locally, write the output to a file and got nearly 4 seconds..(turn off the output, and got 1.9 seconds) 199999 pops and 399998 pushs in total.. So that was really lucky..

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

some1 needs to do something about these fake winners,i mean unrated

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

    I am waiting to be able to solve at least two out of Div.2 C/D/E . Then I will submit. What do you mean by fake?

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

Now that I read one solution to Div.2 C , it seems so easy. Why didn't it click earlier? :(

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

When will the tutorials be available for div2 problems?Especially for C,D,E problems.

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

I am still stuck on Div.2 E:

Idea so far: Start with the original graph. I. While there is a pair of nodes with odd degree add an edge between them. (Observation: because of the pair of cables condition we need at least that many new edges.) II. Find an eulerian tour. Create the graph defined by that tour. III. Follow the tour and whenever we leave a node with odd indegree / odd outdegree reverse the current edge to fulfill the pair condition on the node we left. IV. When we are back at the start node it's in/out degree might have become odd. In that case add a self edge to that node.

And here I am stuck: Does this give an solution or might it have one edge more than a solution? Maybe trivial and I just don't see it.

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

can't see the editorial :( who can help me explaining the DIV2-B case 1&2 ,why both of the output is 1.

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

I really enjoyed the problems although I was to noob to manage to solve C,D,E div 2. A friend told me that in order to solve them I required to know FFT. Can anyone explain me the solutions to these problems based on that algorithm?

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

where are the editorials