malcolm's blog

By malcolm, 9 years ago, translation, In English

Hey there!

Today at 19.30, Moscow time there will be Codeforces Round #319 and it's strongly disadvised to skip it.

I'm the author of this round, my name is Dima Gorbunov and it's my first round on Codeforces. I really hope you're going to like it and everyone will find a satisfying problem. In order to increase the probability of finding that task, please read all of the problem statements.

As usual, I'd like to thank Zlobober for his invaluable help and his special sense of humour, sankear for coding additional solutions, Delinur for the English statements and MikeMirzayanov for amazing systems Codeforces and Polygon.

You're going to have two hours to solve 5 problems. Good luck!

UPD. The scores in first division are 500-1250-1250-2000-2750.

In second division — 500-1250-1500-2250-2250,

UPD2. Because of large size tests for some of the problems, system testing will be slow (it's possible that it will take several hours). Thanks for your patience!

UPD3. English editorial is also accessible.

UPD4. Winners!

Div1:

1). Marcin_smu

2). mnbvmar

3). I_love_Tanya_Romanova

Div2:

1). latisel

2). wrong_order

3). ntitry826

A special respect to al13n for correct solution of Div1.E during the contest!

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

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

Registered with bells on :)

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

If it can be postponed for 24 hours, that will much better. Friday is not weekend. Go to school or go to work prevent us from getting up late, even though we participate in Codeforces Contest in the evening.

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

    Please do NOT postpone it.

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

      Of course it won't be postponed. I just complain about the time for me~ However, I am curious for the reason why you disagree with postpone?

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

        What about the fact that after moving it 24 hours forward it will clash with TC SRM?

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

          Oh......What a busy weekend!

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

          I want to start doing TopCoder, but its awful interface discourages me as soon as I open the site. And its applet isn't that good too.

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

            You shouldn't worry about interface, but rather the problems. In general, topcoder problems have better english and more clear explanations, and the challenge phase is a rather interesting element.

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

              Do u know any tutorial about playing Topcoder? I have tried several times but still dunno how to start.

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

                Have you tried reading the official guide? It is a bit outdated but still conveys the idea.

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

        Oh I have mentally prepared myself for this evening. :P

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

    for me and a lot of contestants Friday is weekend :)

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

      Why? Don't you need to go to school or work on Friday?

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

        In Egypt our weekend is (Friday & Saturday) not (Saturday & Sunday) :)

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

        In Muslim countries weekend is Friday

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

    Usually I tend to miss lectures that has CF rounds conflicting with them.

    It certainly feels different and the rush is better :D

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

Thank you for contest, I think in this contest will be interesting and a lot of hacks. Sorry for my poor english

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

    Why do you think that there will be a lot of hacks?

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

      I like hacks , they save u getting system test failed.

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

        I didn't say that I don't like hacks. I just wonder why he is in this thought..

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

    this contest had more system test failed than hacks.. :(

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

Will the problems be sorted in an ascending order of difficulty?

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

    the statement in the post: "In order to increase the probability of finding that task, please read all of the problem statements" means alot

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

      I think it doesn't, since "that task" refers to "everyone will find a satisfying problem". The question wasn't if the problems will be sorted in ascending order of satisfying-ness.

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

weekend or not weekend ,i hope contest will be running.

Because it is div2 round and it will happen after a long time.

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

Thanks for this holding this CF round and hope everyone can get good score!

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

I hope the problems will be short and to the point. Not with long stories.

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

    But I hope The problems will be short and the point. Not with long stories.

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

    But I hope the problems will be short and intersting, Not with direct statement "please calculate something"

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

Wish me positive contribution :P

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

looking forward for your first set of problems :D

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

Hope that more contests will be scheduled at 11:00 instead of 11:30

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

Time to lose red!

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

hope understand from first time read :3

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

Did you notice that registration finishes as time contest starts not 5mins before...
P.S No That was an error I think? When I looked both times were same..

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

Thanks to author!

contest was great

,how to solve "Modulo Sum"?

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

    I used set, but might TLE. Saved all possible modulo remainders for each element, basically.

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

      That's not enough. You need to combine each remainder with each remainder to get new remainders.

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

        Yeah that's what I did. Instead of iterating over a 10^3 array, I used set, that's all. But sets have a huge constant associated with them, which is what is making me nervous.

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

          And you can also combine the remainder with itself certain number of times. I cannot view the solutions yet, but I'd like to see how you solved that.

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

            "And you can also combine the remainder with itself certain number of times." why?

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

              For example,
              3 3
              1 1 1

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

                There was given sample test
                6 6
                5 5 5 5 5 5
                So obviously, he must have considered that.

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

            Actually, you can't sum one number more than once, the only strange thing was that after n, the subsecuence could continue in 1, but without repeating any number.

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

              its actually coin-change. treat the remainders as the coin that you have, how many numbers can you make. check through these numbers to see which are divisible by m. and you are done.

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

                NO, is not like that, because is a subsecuence, not a subset, a subsecuence is of continuous numbers.

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

                  It didn't have to be a contagious subsequence. One of the examples had a non-contagious solution:

                  4 6
                  3 1 1 3
                  
                  YES
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, but I thought It could be circular, so, after the final 3, continues the first one.

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

                  contagious=transferrable, like diseases contiguous=one after another

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

                At least that is what I thought, but now I see my answer received a WA in the 39 tests

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

    I think there's no way it's impossible if N >= M. My not-very-rigorous-but-you-get-it proof:

    Imagine you're doing a simple dynamic programming solution, with the elements sorted in ascending order first. If a number's multiples "circled back" all the way to 0 (this might mean going around the modulo space several times), we're done. So assume that didn't happen yet. If we can prove this means we'll always get at least one possible new modulo value when adding each number, it's proven. So take a new number X. There are 3 possibilities:

    • This number already occurred. It can't have circled back, so by adding it to the last iteration, we get a new value.
    • It's a multiple of a previously occurring number. Since that number hasn't circled back, we can get several new values just like we did in the first case (from the last few iterations).
    • It's a relative prime to all that occurred before. Obviously, X%M hasn't occurred before, so that's a new value.
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      i found this during the contest http://math.stackexchange.com/questions/699857/proof-subsequence-of-n-integers-is-divisible-by-n

      if you understand the proof please explain it here in plain english. thanks.

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

        this is a different problem. for this subsequence, it doesnt have to be contiguous, whereas the link that you have shown seems to talk about subsequence in contiguous form.

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

          But if there is a contiguous subsequence, then there definitely is a not necessarily contiguous one. I fail to see how this is not relevant.

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

        Appears I was right, yay! :D Anyway, what I posted above is a plain English proof of this statement. But I guess the one given on Math SE is simpler, so I'll explain that one as well:

        Let's assume M == N. I'll only use N in the proof.

        Let's define the series R_1, R_2 .. R_n like this: R_k is the remainder of the sum of the first k elements, that is, (a_1 + a_2 + .. + a_k) % N.

        If for some k we have R_k == 0, take that subsequence and we're done.

        Otherwise, there are N numbers in the R series. They can have N-1 possible values (since none of them was 0). This means there are two equal numbers in R, so there are two prefix sums in the original series whose remainder by N is the same. Let's say R_i == R_j, and i < j.

        This means that adding a_(i+1), a_(i+2), ... and a_j to R_i didn't change its remainder by N. So the subsequence a_(i+1) + a_(i+2) + ... + a_j has a remainder of 0 by N.

        This also showed that there must be a CONTAGIOUS subsequence that satisfies this.

        EDIT: ffao managed to explain this proof much simpler than I did, look at his explanation if you don't get it :)

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

      The (easier, I guess?) rigorous proof:

      Let the sum of the first i elements modulo m be S[i]. There are m different possible values of S[i]. If we find S[i] such that S[i] = 0, we're done. So suppose none of them is zero. By the pigeonhole principle, at least two of S[1], S[2], ..., S[m] must be equal, say S[x] = S[y]. But then a[x+1] + ... + a[y] = S[y] — S[x] is divisible by m!

      So it's always possible if n >= m.

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

        Thanks GrandMaster ffao

        For the case of n < m, can i add dummy values of 0 so that n >= m and then argue that if we can't find S[x] and S[y] then it was not possible with the initial sequence ?

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

          Adding dummy values of 0 is not a valid modification as it changes the answer to the problem. That happens because you can always select your newly added 0 as the divisible by m subsequence, which will make it always possible.

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

What is happening? Why the contest is still running when everybody stopped and there was even a window with information that coding phase has finished?

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

    I haven't seen any notification about extending the round and a lot of people too. Was it a bug or there was no notification at all?

    Nevertheless, I think that the submissions after the original time should not count...

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

    The system gone to total gc on 1:23 :( We are working to reduce memory consumption and prevent such situations.

    We increased contest duration while backed was restarting. Unfortunately, we were unable to send notifications.

    Right now our highest priority task to fix it. Sorry to inconvenience.

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

Was the round extended? Cause I did'nt get any notifications.

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

Seriously, no adding minutes for the round? And system is not available last 5 minutes of contest.

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

Are you going to cancel submits after 2:00?

Btw. I lost 5-6 minutes not knowing that round goes on. And I found a bug 10 seconds after the final end. I hope it wouldn't get AC — http://ideone.com/6DVME8

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

I hacked 2 C-div1 problems with carefully written cases to solutions close to what I believe is the correct answer (somehow partitioning the space in chunks of size 1000xsth and move around them properly).

However, if they are partitioning them in chunks of something different but close to 1000, my test cases probably won't work because their structure is completely messed up,since they are meant against partitions of 1000 (could have been 1001, nothing special in 1000).

Can you come up with a way of creating a challenge that doesn't assume a particular number with which partitioning space? There should exist some of those in system testing, but I cannot come up with them.

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

    PS: the system test probably didn't have them because one of the programs I hacked got accepted just by changing the partition number from 1000 to 1500.

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

When will editorial be available?

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

For C div2, My solution is to print all prime and perfect square numbers that are less than or equal 'n'.

Why is it wrong ??

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

How solve problem C div1 ?

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

Wow , do we have a new dreamoon_love_AA : .o. ?

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

The problems are awesome. Hard to believe none of them had been used before. =)

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

    Why do you call B and C awesome? Some arguments? B is 'write two if-s', C is 'think of the correct partition', both are boring and non-interesting for me.

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

      Well, B ends up somewhat involved while being really simply stated (also I tend to like problems somehow connected to graph isomorphism =)), and C has a constructive flavour which is always nice. The 'think of the correct partition' is for sure more creative than 'implement the segment tree for the bazillionth bloody time'.

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

        I agree that such original problems are the best. Like misof said, "The less it resembles anything I've seen before, the better!"

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

      It is because you are too good For beginner, like me :'( , they are too interesting

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

    The idea of E is old though. For some reason it's still not very overused, I've only seen it maybe four times.

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

      Can you provide some links? malcolm and sankear invented this idea while solving some completely different problem (having nothing common with this kind of semi-online dynamic connectivity) in a pretty complicated but elegant manner.

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

        http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf

        (for the dynamic connectivity; the DSU with flags is new to me and was a nice touch)

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

          Of course the dynamic-connectivity-offline itself is well-known thing, we do not pretend on inventing it. What I asked you is idea that while traversing the tree of divide-and-conquer we can still modify information in the future in a manner similar to segment tree. Did you see such approach before?

          BTW, DSU with flags (as I understand you mean a data structure for adding edges and checking if the graph is bipartite) is described on e-maxx.

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

            Oh, ok, I guess that's new. Sorry, haven't thought about it as a separate idea. Probably because in the implementation I'm used to it's a straightforward modification.

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

How to solve Div1-D?

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

Div 2 D anyone??

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

please make testcase so as to fail all n*m solutions mine n*m failed while this HURTS

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

    That solution is not n*m. That solution is min(n*m, m*m). (The loop will always break after at most m iterations, for reasons discussed above).

    In other words, that solution is correct.

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

Anybody who solved C(Div 1) as follows. Divide into 1000 blocks with 10^6x1000 rectangles. in each rectangle sort points by (x[i]+y[i]), I think it can be proven that will give 2n \sqrt(n) bound.

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

    No, you can create a test giving 3E9 if you don't alternate the sort order.

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

      It seems that it works if each block is 1414x10^6.

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

Why there wasn't any announcement for the extra 10 minutes!!

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

    I tried to submit solution 2 minutes before contest end and I could not do it. 15 seconds before end I could submit, but I was not fast enough. I waited 2-3 minutes to see if contest is extended, but it was not. The only good think is that my solution would be incorrect anyway as I checked.

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

Div 2. A. What is a worst test case time complexity for this solution? 12930538.

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

    It seems to be that the worst case for that solution is a n = 10⁵ and x = Highly composite number below 10⁹. It may be something like divisors(x) * n. On a quick analysis it seems that x has more or less 10³ divisors. So, the result should be 10⁸.

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

LoL, why this solution gives TLE:12934189? Is it because of using vectors?

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

    No, because you did O(n*m). Beign n <= 10⁶ and m <= 10³ you have a 10⁹ solution. That's slow.

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

    You are dividing 1E9 times but divisions are expensive so you can't make a lot more than 1E8 of them per second.

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

      But my solution is O(m^2)( I consider case when n>m).

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

        Ah sorry, I think the problem is that you are reading a million ints using cin, c++ streams are often too slow for such huge input.

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

          that would be really sad as i also seem to have O(m**2) but i am reading data with cin :(.I also think this should have been covered in pretests

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

            cin is fine; just add this magical command:

            ios_base::sync_with_stdio(false);

            See here.

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

              Magical command helps a lot, but anyway cin is much slower then scanf, even with command.

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

                Ironically, I've had my first experience with that just now.

                But it is fairly rare. Still, I'll use scanf from now on.

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

    Do you ever clear xp? I think xp might be getting really big near the final iterations...

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

Ugh, I only had a bit less than one hour for the contest. To be precise, I'm travelling and the only place where I could do the contest was one train/bus station (next to each other). But the train station's net hotspot didn't work and the bus station only has a 3rd party connection with 1 hour free, then nothing. So I hurried a lot and I think I'm going to fail both B and C.

Why couldn't the round be 2 hours earlier... I could've done it at home then...

UPD: yes, I failed both B and C.

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

    Why didn't you leave this one for virtual contest if you were travelling?

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

      Because it'd be yet another one. Most CF contests have had awful dates for me recently (which means the last few months, because there have been so few). When I'm home, there's nothing, then I leave somewhere without net for a few days and a CF contest is guaranteed.

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

2s * 617sols * 50tests ~ 900 min testing (task C)

Where am I wrong?

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

    Ok, I can't into parallel calculations and good solutions which work fast (or fail early), but it still slows testing, thank you for the limits

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

Am I the only one who mistakenly read the constraint in problem C as 2.5·108 instead of 25·108? The common agreement about scientific representation of real numbers is to use normalized notation and according to it the constraint in problem C should've been 2.5·109.

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

    You are not alone)

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

      And our solutions is very similar. We both tryed to solve it O(n*logn), TL.

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

    At first I also misread it, but the points (1000*i, 1000*j) with 1 <= i,j <= 1000 are such that the shortest Hamiltonian path has length ~10^9

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

    In fact it was possible to understand that you understood something wrong by noticing that for the 1000x1000 uniform lattice (all points of form (1000a, 1000b)) the answer has order of 10^9.

    Nevertheless, you are right, writing 2.5 * 10^9 could've been much better.

    UPD: oh, Nicolas16 said the same thing before me.

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

      Well, the statement said "it's guaranteed that the answer always exists for given input" so I didn't worry too much about that :)

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

        Yeah but then there would have been input where the minimal length is exactly 2.5 * 10^8, which means that we would have had to find the exact minimal path in this particular case (which did not seem to be the the goal of the problem).

        However, I had to remark all these things during the contests and I lost some time before understanding I misread the bound, so I am not saying you are wrong :-)

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

    I thought it was a trick to obscure the desired complexity. 2.5·109 looks pretty much like while 25·108 is «what the wierd constant is it?!»

    I really thought of it as a nice beautiful obfuscation, no irony here.

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

Too scared to look at my submissions page.

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

Those permutation problems are cool

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

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

What is special at test 9 from div1B? I looked at my source 10 times bbefore submitting it to be sure I don't miss anything. I've even hacked some sources=)))

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    printf ("%d %d\n", nod1, nod2);
    for (int i=2; i<=N; i++)
    

    Isn't this going to miss node 1 if it is not either nod1 or nod2?

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

      Yes, it does...stupidest bug ever.Thanks.I don't know why I pressed 2

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

I might be the happiest blue coder to-be ever!!!! Should be out of green right??!!!!

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

"and it's strongly disadvised to skip it."

Nice trap

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

Look, the green coder latisel is the winner of a Div2 contest!, oh wait look at his previous contest here.

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

I passed D with "bad" solution :) Only optimization is order of for loop in matrix multiplication — I remember reading somewhere that you can make naive multiplication cache-friendly by switching order of for loops from i, j, k to i, k, j. And after that, all that's left is a trivial if statement that checks a[i][k] isn't 0 before multiplying it with the for loop with j.

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

    I thought about submitting that, but I was pretty sure it wouldn't pass... Guess I shouldn't underestimate the CF servers after all :)

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

      Looks like that is the wanted complexity... Makes me think D is a pretty bad problem now, is it just "submit the obvious solution and hope that it passes"?

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

        There is a typo in editorial I think. It should be "it's not enough", not "now enough". So /32 was intended.

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

          Yeah, it's definitely a mistake, thank you.

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

    I think I have the same solution (12942073), but it got WA44 and I can't find the bug now...

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

for DIV2 B: can any one find whats wrong with this submission: http://codeforces.me/contest/577/submission/12944993

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

    What is this?

    for(int j=1;j<= ht[i];j++)
      sum = (sum + i);
    
    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      after putting number into buckets within %m.....

      I am iterating over each bucket for count of #'s in it...this loop is for that....

      Thanks for your reply...

      I can understand if this goes on and gives TLE but i want to know why WA....

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

      Hi....thanks again for looking into my code....it turns out just a shift of loops here and there and it got AC.

      here is the submission: http://codeforces.me/contest/577/submission/12963454

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

why does the use of pow function from math library give a WA while without that its AC... Ans 1 : with pow func http://codeforces.me/contest/577/submission/12941362 Ans 2 : without pow func http://codeforces.me/contest/577/submission/12947283

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

    Its happening with me too!!!!!

    codeforces is giving me this output for test case_ 7_**** 19 32 16 8 4 27 9 24 2 3 5 7 11 13 17 19 23 29 31 37

    but my system is giving this output! 19 32 16 8 4 27 9 25 2 3 5 7 11 13 17 19 23 29 31 37

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

      for me its test case 4... cf : n=15 -> 9 2 3 4 5 7 8 9 11 12 ideone : n=15 -> 9 2 3 4 5 7 8 9 11 13

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

    Pow uses floating point values and you round them down when you convert them to ints. It should pass if you add an epsilon.

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

    Try using powl()

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

al13n got 90 tests on problem E, but Endagorion got TL on 96 test, wtf?

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

    We are already investigating this.

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

    Fixed. That was not a judgement error, but only an error of verdict page showing information not for all testcases.

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

hi.. i think that there is something wrong with codeforces compiler this code gives wrong answer on test4 problem C http://codeforces.me/contest/577/submission/12937746 i tried the same input with the same code on my computer and on ideone (http://ideone.com/hIQ3BM) and it gave the right answer.. could any one pleas tell me what is going on?!!

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

    You can't trust the pow function since it uses floating point arithmetics.

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

      Thanks JohStraat..but i can't really understand ..is using pow function causes undefined behavior?? ..so what do you suggest instead using pow function in general?

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

        as suggested by dushyant use powl or make your own pow it will be a short function

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

Div1 C checker is awesome!)

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

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

I didnt became div1, but I am too close. I hope at future to be :) Thank you for the great contest!

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

Finally got into Div. 1 ..

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

Thanks pretests...

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

2496501499 in C, seems legit :D

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

    With 999 endings instead of 500 in 44th test it would go up to ~2990*10^6, buckets should be sorted to avoid that. Solution of Marcin_smu looks hackable too.

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

This is really bad in cf. TLE with cin and AC with scanf for div2 B. These are the solution links 12935258 12951554

My rating also went down. It could have gone up

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

    First know how cin works vs how scanf works before blaming codeforces.

    its good thing your rating went down.

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

      Yes I know that but this almost never happens on codeforces. There are cases when 10^9 complexity solutions are also accepted

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

        And part of competitive programming is knowing when it is and when it isn't.

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

      Never a nice thing to say :P