tunyash's blog

By tunyash, 12 years ago, translation, In English

Hi all! This round was prepared by me and KAN. I hope, you will enjoy our problems.

I want to thank PavelKunyavskiy, who tested our problems, readed statements and so on. Moreover, alger95, Skird, fdoer, sand-martin tested round too, I thank them for it.

And of course, I thank Gerald for organising our work, MikeMirzayanov for the great system and Delinur for translation of the statements.

I hope, result will be better than results of our previous round. Good luck!

Pay attention, round will be held at unusual time.

Scoring:

div1: 500-1500-1500-2000-2500

div2 : 500-1500-1500-2500-2500

My congrutulations for leaders.

div1:

  1. al13n
  2. tomek
  3. niyaznigmatul
  4. voover
  5. Egor
  6. Zlobober
  7. White_Bear
  8. seanwu
  9. wjmsbmr
  10. peter50216

div2:

  1. fotiIe96
  2. zfmdhy786
  3. wzc1995
  4. gjh
  5. mynameisverylong

Full english editorial: here

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

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

although the starting time of the contest is not as usual , I hope it will be a great contest and GL & HF to all participants :)

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

I hope the host could change the start time once again like a last year's contest.

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

I expect a very technical and hard round. I liked your last round! :-{)

»
12 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Great, I like the time of the contest! What are the scores? 500 — 1000 — 1500 — 2000 — 2500? or something else?

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

I like this starting time of the contest ^_^

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

I'm not sure if i'm going to stay up all night or take some sleep before this round.

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

Starts 450 minutes earlier than the usual time . Hope , there'll be some surprise in the problem statements too as well as the starttime :)

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

@ Mike Mirzayanov

sir, why dont we have variable time for 'codeforces contests' like topcoder? is it because the usual time attracts lot of participants or it's just to distinguish Codeforces from topcoder?

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

    I totally agree.I'm excited because this round is at 12.00MSK.We Chinese coders don't have to stay up at 23.30(Chinse Time) to participate.At first I thought this round is by a Chinese or Janpanese coder,but it seems I'm wrong.Thank you tunyash for this round at such great time!

    I think,if Codeforces can have variable contest times like Topcoder,more coders will participate and Codeforces will become better.It is necessary to do so if Codeforces is to overtake Topcoder and become the first largest online programming competition site.

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

    agree too

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

:(((( at this day, tomorrow i have maths olympics :((( it begins at 10 o'clock and end at 2 o'clock :((((

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

I like this starting time of the contest! Hope the starting time will be variant,(not limited to 7:30pm in Russia) so that more US or Chinese coders will attend the contest.

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

Will points distribution be standard or dynamic?

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

last contest was great.I hope it will be great too

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

I hope for a more organized editorial this time ... Guys take 1 day but give us good editorials .

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

As you can see many people couldn't participate this contest ... It might be good for some countries but it's not for most ...

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

    I mean variable contest times.I'm not suggesting we always have contest at 12.00MSK,there's no doubt we need 19.30MSK contest time.For example,I suggest 30% contest set at morning of MSK Time.

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

    As lsmll said, it should be good to everyone, so it's fair enough to variable the time so anyone will have a chance to participate. It's 5 A.M here in Brazil but i'm still gonna participate even though this time I really should be sleeping.

»
12 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Test photo.

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

good for Chinese users.

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

By the way, past tense of "read" is "read", not "readed".

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

My first contest in travel! Good luck!

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

Time limit for Div2 B is too long :( even brute force from k to 1 can pass :(

Got an Unsuccessful Hacking Attempt when trying to hacking one of those brute force solution :(

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

    can you give me the link of this solution i think brute force will get TLE

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

      Here is one .. Actually it's kinda weird O.o , I implemented this solution in the practice and got TLE , but when I tried mikhail's code got AC .. I think it depend on the optimizer somehow!

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

        same to me got TLE :D with same solution

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

        The reason for TLE in your case is, if I'm not mistaken, the use of long long in the line for (ll i = k - 1; i >= 2; i--) { whereas the AC solution uses int for i. As a long long takes up more space in the memory in comparison with integer, it also takes longer to perform calculations with it (here: 'i--'). In this case it makes the difference between TLE and AC.

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

          Yes you are right about this .. But I think in general the intended solution is binary search , and the brute force should't pass.

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

            You know, there is an O(1) algorithm (as opposed to the algorithm of binary search), if you want to do some math. My submission, for example, is the implementation of the result: 3390910

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

              Is sqrt really O(1)? I guess you could argue it's really fast, but actually it uses binary search (which is O(log k), not O(sqrt(k))).

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

                Square root is O(log k)? I have always assumed that it's (along with the four arithmetic operations) constant. My bad. Thanks for clearing it up!

                Also, yeah, I meant O(log k) for binary search. I must have been in a hurry to type O(sqrt k) instead.

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

                  I think the sqrt function calculates the square root with fixed relative error, so it's O(1).

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

              Here is a c++ implementation:3396062.

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

    Even this Solution passes. Time:2000 ms :SS

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

Those who like permutations should be quite successful this time :)

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

wow! All System Testing was only 4 minutes!!! Thanks for this great testing!!

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

    probably because there were fewer participants than usual....i myself didn't participate as it was at a different time and i forgot about it...

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

      I agree with you, The time of the contest was good but I forgot it too!

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

Systest complete within just 2 refreshes :D

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

Fast system test... Great!!!!

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

To those who solved div1 A quickly e.g. within 20 minutes, how did you observe the trick(when n%4>1 return -1)? Thanks.

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

    I think writing backtracking may be useful here.

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

    Use next_permutation to do brute-force first.

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

      With this method, did you manage to quickly find the pattern?

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

        Of course, we can use this method to find all solutions (n <= 13) within a minute. And the pattern is very clear. Try it.

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

    Well I didn't solve it within 20 minutes (and I'm div 2 anyway), but I suppose it's pretty simple:

    Suppose f(i) = pi. We have f(f(i)) = n + 1 - i, so f(f(f(f(i)))) = i. So the permutation is effectively cycles of 4, 2, 1. However, there can be no cycle of 2 (otherwise f(f(i)) = i ≠ n + 1 - i if , and if , then it's a cycle of 1), and the only cycle of 1 can only be done if , so there is at most one cycle of 1. Hence everything is in cycles of 4 except for possibly one element. This means or .

    When in the contest, I visualized it by an n × n board where you put a piece on row i and column j if pi = j, and noticing that everything are the vertices of squares except for probably the middle element.

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

      This is a brilliant idea. However, I still have two questions.

      1. What's the meaning of the cycle? Seems like some kind of abstract algebraic construct like group?

      2. I don't understand your last sentence above(i.e. and noticing...), can you clarify it?

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

        First question:

        Let's see a permutation 2, 3, 1, 4, 5. Note that p1 = 2, p2 = 3, p3 = 1. So from 1, we can get to 2, then to 3, then to 1 again, and it repeats forever. So (1, 2, 3) is a cycle, of period (or you can say "size") 3. p4 = 4, so (4) forms a cycle of period 1. Also note that we can multiply the period of any cycle by simply extending it: (1, 2, 3, 1, 2, 3) forms a "cycle" of period 2 × 3 = 6. I'll refer to a cycle with the smallest period (it cannot be broken into cycles) to be a "proper cycle".

        If f(f(f(f(i)))) = i, then i must belong in a cycle of period 4, or in other words, a proper cycle whose period is a divisor of 4, hence why I can deduce that there can only be (proper) cycles of period 4,2,1. If the problem has been made such that f(6)(i) = i (6 iterations of f), I'd look for proper cycles of period 6,3,2,1.


        Second question:

        See the given permutation 2, 4, 1, 3 in the test case and what I made in my scratch paper:

        .O..
        ...O
        O...
        ..O.
        

        As you can see, I put a piece (O) in row 1, column 2, indicating that p1 = 2. Another one in row 2, column 4: p2 = 4.

        After making this, I noticed that everything is vertices of squares except for probably the middle piece (if there is any).

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

          Elegant explanation, thanks.

          I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest.

          But I still don't know the meaning of "everything is vertices of squares", which squares?

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

            Well, you can see that the four pieces in the above grid are vertices of a square, tilted a bit clockwise. Another example for n = 9:

            .A.......
            ........A
            ...B.....
            ......B..
            ....O....
            ..B......
            .....B...
            A........
            .......A.
            

            Observe that A's make a square, and so are B's.

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

              I finally understand. It's just a visual way describing the cycle of size 4 phenomenon. However, it's more precise to use the term "parallelogram" instead of square, isn't it:)

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

                Actually you'll find that all the parallelograms will be squares (try to prove it :) ), but you can use "parallelogram" too if you prefer. Yes, it's my visual way of describing a cycle of period 4.

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

            "I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest."

            Of course. The pi-th element is ppi, which by condition is equal to n + 1 - i. It is obviously the i-th largest element.

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

    Number of inversions in a square of a permutation is even, and number of inversions in permutation (N, N — 1, ... , 1) is N(N — 1)/2. It is clearly odd for N = 4k + 2 or 4k + 3.

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

      That's correct. But could you explain the reason using no. of inversions to judge? I don't figure out the connection.

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

        I don't quite figure what is the question about. If a permutation has an odd number of inversions, it can't be a square of any permutation. Therefore for N = 4k + 2, 3 answer doesn't exist.

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

          Actually I don't understand what "square of a permutation" means.

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

            A permutation applied twice consequently, like ppi in the problem statement.

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

            The square of a permutation p is the permutation pp; that is, if originally the permutation p has pi = j, pj = k, then the square of p (which I denote q) has qi = ppi = pj = k.

            For example, if p = (2, 4, 1, 3), its square q is:

            q1 = pp1 = p2 = 4

            q2 = pp2 = p4 = 3

            q3 = pp3 = p1 = 2

            q4 = pp4 = p3 = 1

            I assume that you already know "inversion". The square of any permutation has the property that the number of inversions in it is even. Meanwhile, by the condition of the problem, the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1), which has an odd number of inversions for or , so they certainly can't be equal. So there doesn't exist any permutation whose square is the reverse identity permutation if or .

            (EDIT: I keep making long comments and getting "ninja-ed" by people -_- But who cares.)

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

              It's clear. All understood except "the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1)", the reason?

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

                Because the problem says that ppi = n + 1 - i.

                If we expand this for all i, we get that (pp1, pp2, pp3, ..., ppn) = (n, n - 1, n - 2, ..., 1); in other words, the square of p is the reverse identity permutation.

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

                  About the parity of square of permutation, is there any proof? Given a permutation, how to decide whether it can be a square of some permutation?

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

                  That's the thing. I only recall that it is an established theorem, but I forgot the proof. Searching in Wikipedia also yields no result (although I think I saw the theorem in Wikipedia).

                  ...Ah ya, here it is. I rephrase the (trivialized in Wikipedia) proof:

                  A permutation can be described by a number of adjacent-element transpositions. For example, (2, 4, 1, 3) can be described by (3, 4), (1, 2), (2, 3):

                  From (1, 2, 3, 4), we transpose elements on indices 3 and 4: (1, 2, 4, 3).

                  We then transpose elements on indices 1 and 2: (2, 1, 4, 3).

                  We finally transpose elements on indices 2 and 3: (2, 4, 1, 3).

                  To prove that we can always do so, it's simple: Just build the permutation we're going to make from the end (or from the front). The above sequence uses this algorithm: It constructs the permutation by first moving 3 to the end (as it's the last element), then 1 to the second-to-last index, and so on. (It's just lucky that after we move the 1, the permutation has been built already.)

                  Now, we note that the number of inversions changes by 1 for every adjacent-element transposition we made, so the parity of the number of inversions is equal to the parity of the number of adjacent-element transpositions we made. So, the parity of a permutation is equal to the parity of the number of adjacent-element transpositions. (This number may vary by simply adding something like (1, 2), (1, 2) as many times as you like, but the parity of the permutation always remain the same.)

                  Now, the composition of two permutations is just the product of their transpositions; in other words, the parity of the composition is equal to the sum of the parities of the two permutations used to build the composition.

                  Now, recall that the sum of two equal parities (even+even or odd+odd) is always even, and the square of a permutation is the composition of a permutation with itself. It's obvious that the parity of a permutation is equal to the parity of the permutation itself, so its square, which is the composition of the permutation and itself, must be even (as it's the sum of two equal parities).

                  I'm not sure how to determine whether a permutation is a square of another permutation or not though. I originally suspected that all even permutations are squares of some permutations, but (2, 1, 4, 3) doesn't satisfy it, so I don't know.

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

                Oops, I got it now. Because P(P(i)) = n-i+1, so applying P(P(*)) on 1 through n, the result is the reversing sequence (n,n-1,...1). Thank you for the reply.

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

    Each of the elements, for which i != n -i + 1, needs to be in the cycle of size exactly 4. So we need to partition all elements (or all but one) into such cycles.

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

    I just didn't prove anything and submitted it on 10th minute :) My prove was like «can it be that there won't be any 2 (mod 4) or 3 (mod 4) tests in pretests? :)»

    (Disclaimer: I use this only on contests)

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

    eg. 5

    1 -> ? -> 5
    2 -> ? -> 4
    3 -> ? -> 3
    4 -> ? -> 2
    5 -> ? -> 1
    

    Case1:

    1 -> ? -> 5 -> ? -> 1 2 -> ? -> 4 -> ? -> 2

    merge above

    1 -> 2 -> 5 -> 4 -> 1

    Case2:

    3 -> 3 -> 3

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

It seems that m = n in all pretests of D. That may explain for some WA on test 7 I think.

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

Nicely done problem setters, that was an absolutely amazing contest. It was worth staying up all night.

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

Congratulations to al13n! 2 victories in a row seems impossible if you're not Petr or tourist but he did it!

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

Div 1 B can be solved by the naive algorithm...

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

This contest was great! nice problems !

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

Div1 B can be solved by Brute-Force?

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

Question could have been little more clear.. at last i figured.. !!

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

ACRush was in my room today and he became WARush today!!!

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

DIV 1 problem C TLE for using cin...

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

    You should use cin with ios_base::sync_with_stdio(false);

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

      why " ios_base::sync_with_stdio(false) " is makes cin fast ?

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

        This link explains that if this flag is true, it maintains the stream state in both cstdio and iostream so you can mix scanf/cin calls (or printf/cout). Turning it off means cin won't advance stdin, so it does less work to read the input.

        I failed the same problem as olimpo because of being slow with input, but it's nice to discover something new like this...thanks, shervinkh!

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

        In default case, cin and cout don't use buffering. This behaviour enables programmer to use scanf, printf and cin, cout in a program simultaneously. Using ios_base::sync_with_stdio(false) tells cin, cout that you don't want to use scanf, printf with cin, cout. So cin, cout use smart buffering with lots of speed up (more efficient than scanf, printf). I think the latter case should be default. but its the decision of C++'s creators.(may be because of ability to use cin, cout in old c programs that use scanf, printf). for large inputs and outputs (1e5 or 1e6 or more words) that is usual in algorithmic contest program buffered input and unbuffered input differ a lot in the speed. so in every algorthmic contest program it is recommended to use that call in the beginning of the program.

        EDIT: It seems that while i was writing this, Quelloquialism has written the answer.

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

Div2 C says "any integer i" meets the condition, not "every" or "all". I thing it's not even ambiguous, I did the wrong algorithm because of that :s

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

Nice Contest! For 286A - Lucky Permutation, I'm quite interesting on how to prove that there's no solution when n % 4 equals 2 or 3.

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

!!!!!!!!!!!!!!!!!!!!!!!! The problem D has n, m to read, but read m variables next and read n variables next. The pretest do not contain the situation when n is not equal to m... TAT TAT TAT

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

    I'm sorry, I didn't noticed that. My fail.

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

The input format for 286D - Tourists's is a bit strange - {#queries, #events, events, queries} instead of the more usual {#events, #queries, events, queries}.

Typical: The one time I'm good enough at algorithms to write a correct Div1-D solution, I'm also not literate enough to read a Div1-D statement properly.

Upd1. Looks like Martin also had this problem, and I don't type as fast as him.

Upd2. There are 12 contestants affected: Contest Status (look for WA#7)

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

Could someone help me? my submission 3392032 got TL on test 41 in system testing but my next submission after the contest 3392661 got Accepted I just changed the size of my arrays from 1000005 to 2000005, but I think 1000005 was enough! wasn't it?

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

    replace "cin" by "scanf" first, then submit again

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

      Thanks, got Accepted! but why did this submission (3392661) get accepted? I just increased the size of array!

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

        Maybe server was too busy first time? (see 41 test "Time: 1921 ms, memory: 23488 KB")

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

    Your first submission is also accepted.

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

Enjoyed doing this contest.. Nice questions !! :)

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

drop 3 times in a row

lose IGM title so quickly

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

    Looks like your ability has been transferred to wjmsbmr

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

      Actually she is my girl friend :)

      But she is better than me >_<

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

Is today's contest unrated?

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

    Why! ... no reason for what you say

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

      Up to now, the rating wasn't changed.

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

        Usually it will be updated an hour (or even later) after contest...

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

          It's already more than two hours (almost 2.5 hours) and the rating haven't been updated yet..

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

good problems! thanks :D

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

How did this person become a candidate master even with a rating of 1555 ?

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

Can anyone please explain this to me :-

For every unsuccesful submission , theres -50 so why does a user gets same score as me when he has 4 unsuccesful submission and i have none and the only question we both have solved is done at same time!

More specifically here , user 'abhinav92003' and i have got same score/rank. Hows this possible ?

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

    You don't get -50 when you eventually don't succeed to solve the problem. Here, you both solved one problem in the same time so you have the same score. He tried to solve B unsuccessfully, you didn't try, I don't think you really deserve a better score than him...

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

      @Nicolas16 , okay i get what you have said. And is there -50 for 'Failed System Tests' ?

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

        What do you mean by Failed System Tests? Actually, when you solve a problem, your points for this problem is equal to the score corresponding to the time you took to solve it, minus 50 points by previous failed submission (unless it is on the first pretest). And there is a minimum so that someone who solve a 500 point problem with 10 wrong submissions don't get 0 but 150.

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

          vote ups

          No , i think you got it wrong . By 'Failed System Tests' , i think @IITian meant that one gets AC during the contest and after contest , at final testing , compiler judges it wrong! For that i think he was asking wether or wether not is -50?

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

            I believe that it doesn't give any penalty, much like unsuccessful problems (submissions that don't pass pretests and the problem is eventually not solved) don't give penalty.

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

    Points are deducted for unsuccessful submission only when you have solved the problem. He has not solved the problem.

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

Can someone explain me how to approach problem D of division 2?

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

it passed almost 2:30 hours after the contest and still the rates are like before!!! why ?

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

ratings were updated

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

I enjoyed this contest very much! Thanks :)

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

Hi everyone! I realized during the contest that problem B Div. 1 could work using a brute-force approach, however I was unable to maintain the cycles without moving too many elements at once. Could anyone who solved the problem correctly give me a hint on how I could achieve this?

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

    If you look at some of the accepted solutions you will notice that you can think of each move which is performed as follows: Let's say that the elements which are the first in their blocks are on positions P(1), P(2), ..., P(Q) (obviously, P(1)=1). Then, instead of thinking about cyclic shifts, imagine that all the elements stay in place, except:

    • the element from position P(Q) goes to position N+1

    • the element from position P(Q-1) goes to position P(Q)

    • ...

    • the element from position P(1) goes to position P(2)

    This way, you only get to move the elements on the positions P(1), ..., P(Q), and your sequence can now be found on the positions 2, ..., N+1 (instead of 1,...,N, as in the beginning). At your next move you will simply have to consider the fact that your sequence does not start at position 1.

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

I got hacked in Div 2 A . this is my solution , can anyone tell me the test case or my mistake

int main() { char a[6][6],c=0;

for(int i=1;i<=4;++i)
{for(int j=1;j<=4;++j)
cin>>a[i][j];}

for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
{   int c=0;
    if(a[i][j]==a[i+1][j])
    c++;
    if(a[i][j]==a[i][j+1])
    c++;
    if(a[i][j]==a[i+1][j+1])
    c++;
    if(c==3 || c==2)
    {cout<<"YES";return 0;}
}
cout<<"NO";

}

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

    In this case, first 2x2 square is a possible answer. You should also check if 'c' is 0.

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

    Here the answer is YES but your program prints NO:

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

    just amended this line

    if(c==3 || c==2) to this line if(c==3 || c==2 || (c==0&&(i!=4 &&j!=4))) and got accepted

»
12 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Most of the times i see the code of a problem not solved by me , i notice that around 90% of the code of 90% coders is same . e.g in Div B 2nd problem .

I m a newbie coder , plz tell me something that i m missing .

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

please tell me anyone...>>>>>> at first i submit the problem,then accept. but it hacked. after i submit the problem then accept. when the code check,then all correct. but when given the rating ,show solve is 0; when i see my submission then see that skipped. what's the of the side.not only today,but also before a day can happen. i am very very dishearted.....>>>>>

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

    Maybe rating is not that important, right? The things that you learned is what matters.

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

When will the editorial be published?

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

    I think, it will appear tomorrow. We have editoral in russian, but we haven't translated it yet.

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

Can somebody tell me some more problems like Lucky Permutation to practice.

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

please see comments of user: SROPRO ! I think He's Activity isn't good for this site!

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

can't connect the editorial ...would you publish the editorial at codeforces blogs

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

    Me too , please publish it at CF blogs.

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

In 287E - Main Sequence can {-1,-1} be correct bracket sequence?

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

There is a problem in the explanation of the C problem in the editorial. You must insert {2,n+4} at the beginning and {1,n+3} at the end as the second step to form a (n+4)-lucky permutation from n-lucky permutation.