MinakoKojima's blog

By MinakoKojima, 12 years ago, In English

Three drops in a line, back to yellow so quickly ...

Anyway, Codeforces Round #183 will be take place on Sunday, May 12th at 17:00 MSK(21:00 CST). Right after the Google Code Jam Round 1C.

Setters are:

  • Yuzhou Gu sevenkplus (For Problem B && E)
  • Yuping Luo roosephu (For Problem A && D)
  • Jiatai Huang CMHJT (Problem C)

Testers are YuukaKazami, havaliza, Velicue && me.

We gratefully acknowledge Gerald Agapov(Gerald) for his help in giving advise about the problems, Delinur for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

We strongly recommend you to take a glance over all five problems, there must be one suitable to your taste.

Oh one more thing, this time, scoring will be dynamic, but problems are sorted by increasing order of their difficulty as usual.

Good Luck!

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

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

Great!! I think it will be a great contest while the setters and testers are very good. Thanks for your soon post :)

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

Not in midnight in Japan(and other far east Asia and Australia) Great!!!

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

Codeforces Round #183?

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

Are you sure in number of this round? Think, it should be 183.

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

Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.

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

Haha noone even mentions Div2 A and Div2 B problems :D

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

I think the problemset is easier but much more interesting this time..

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

Am I right that original statements will be in english?

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

Why this blog was not on home page ?

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

The first time I can participate in

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

Hmmm contest time changed? 6AM in California...

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

Why time is non-standart?

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

    There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.

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

It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.

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

I wondered why comments by MinakoKojima got so many negative feedback?

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

A question : is MinakoKojima (Feihu Tang) boy or girl?

I thought the name is a boy's, but in his(or her) photos shared above it's a girl....

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

    You can see that her name is 唐菲蝴(beautiful butterfly Tang),then everything goes right.

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

    She's really a girl, believe me.

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

I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)

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

It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.

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

=w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T

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

are there any mistakes in sample tests in problem B div 2?

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

Congrats for making unrated contest.

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

The contest was perfectly prepared and tested :D

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

Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.

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

    Same here. I don't know why this is incorrect...

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

      The sad part is that a lot of people solve it and I don't even know how to interpret the statement — should the rectangle be the closest to (x;y) or lexicographically minimum..

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

        I spend a lot of time to guess — but i still don't know why... Sent clar, let's wait

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

          I sent one an hour ago. Guess what the answer is? You're right, "no comments" :)

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

            For me, they said, that my answer is not optimal..

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

              Did they explain, why?

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

                I sen't another clar 15 minutes ago, still no answer. UPD: Got an answer : We need first maximize the sub-rectangle, then take the lowest distance.

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

                  Damn, missed the word 'maximum'. Thanks, man.

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

    because you should select biggest rectangular possible

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

      Thanks for the answer. I feel like a total loser.. Ah, anyway, this will be a good lesson for my future contests.

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

    From the problem statement . . .Your task is to find a maximum sub-rectangle on the grid (x1, y1, x2, y2). . . .

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

Missed the round — no mail?

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

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

How to solve Div2 D?

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

    first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0

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

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

Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.

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

    python lol)))

    from datetime import date
    
    a1 = map(int, raw_input().split(":"))
    a2 = map(int, raw_input().split(":"))
    
    print abs((date(a1[0], a1[1], a1[2]) - date(a2[0], a2[1], a2[2])).days)
    
»
11 years ago, # |
  Vote: I like it +108 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.

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

Because of so many mistakes, I strongly think this round should be unrated.

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

    if so, this will third continuous unrated contest :)

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

    I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.

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

Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?

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

What a funny round!

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

Great round, interesting problems. :-)

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

The problem is nice,but clarifications too disturb.Waiting for next round.

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

My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...

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

    an O(n^2+ans*k^2+a_max ln ans) solution was expected.

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

      Sorry, I mistook the analysis of my order... My solution was your order, thank you.

      I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...

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

        Try to use array instead of vector, it speed up performance of my code dramaticaly in this problem.

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

          Oh, thank you for your advise.

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

Nice problems. A lot of maths, but It's enjoyable. :)

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

Intereting problems!

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

The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".

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

What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?

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

System testing of Div.2 was very bad.it was finished , but final standing was not ready!

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

Div.2 A

My code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....

TvT

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

    Check out mine 3706566. I think problem is in ceil() and floor(). Got AC replacing floor(c) with (int)c3712951. I would like to say : Authors, How about increasing time limit to 4s ? but it's too late. I have already got my Wow you have +67.

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

    i too used ceil() function and TLE...

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

    It would be better that you check your solution in custom test before submitting....

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

ORZ failed div.2 A

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

For Div2 C, now I understand why I could not find any formulas for even values of n..

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

Weak pretests :(. B-Wa 11 because of mixing up n and m.

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

Wow constraints were really strict.

My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...

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

my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...

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

    Are you sure your solution is your own, not copied from others?

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

How to get full test cases for: http://codeforces.me/contest/304/problem/E?

Thanks!

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

Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:

wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'

This doesn't look like a correct probability, does it?

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

    I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.

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

    All tester's program have different solution so you know

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

    the model solution of E is wrong...it has precision problem.

    the setter is trying to fix it... but still rng58'solution seems has precision problem too...

    actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.

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

    I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:

    int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }

    My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).

    Currently I guess it's impossible to solve this problem precisely under the given constraints.

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

    Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.

    So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible.

    Thanks for the notification!

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

    I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE (the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.

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

      It seems that my solution's running time doesn't depend on the actual test case as long as li ≠ lj, ri ≠ rj and li < rj for all i and j. A gap of 110 ms is not big enough, though :)

      Your optimization is nice, thanks! Now the problem is really solved.

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

        I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.

        Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)

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

    We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.

    My appologize for this situation. And great thanks to tourist for the notice!

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

    Can you write tutorial for this problem?

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

It seems I solved 303C - Наименьший модуль with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.

Is there any testdata which challenges the program or I calculate the complexity wrong?

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

    Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.

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

Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.

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

    EDIT : The proof I have post is wrong. See the comment below.

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

      Please correct me if I am wrong, but I am not getting the proof.

      When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.

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

        You are right. Sorry for having post a wrong proof.

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

          No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.

          I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.

          If you get the proof using the above logic please let me know.

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

    If , then or just , where S = 0 + 1 + ... + n - 1 = n(n - 1) / 2. So, there must be . But when n is even, .

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

      Where S=0+1+2+3+...n-1=n(n-1)/2

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

        Thank you, fixed.

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

          there must S = 0 mod n. But when n is even, S != 0 mod n. I do not understand the above statement. Could you please elaborate more. Thanks

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

            When n is even, S = n * (n — 1) / 2 let n / 2 = p which is smaller than n S = p * (n — 1) Clearly, S in this case is not divisible by n.

            • »
              »
              »
              »
              »
              »
              »
              18 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But also when n is odd. The sum formula stays the same. or I am getting this wrong ?

            • »
              »
              »
              »
              »
              »
              »
              18 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ahh Now i get it. S = n(n-1)/2 this sum is divisible by n because S/n = (n-1)/2.

              Now if n-1 is even then n-1 is divisible by 2. else if n-1 is odd(n is even) the sum is not divislbe by 2. thus not divisible by n.

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

      this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.

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

        for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1

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

          Why is that? How do we come to this?

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

            I had the same doubt. But I guess it is expected that we try the obvious permutation first and observe that its the required one. When N is odd having the permutation

            0 1 2 3...N-1

            0 1 2 3...N-1

            gives a permutation of required category. While it has been proved above very nicely that for N-->even there won't be one

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

For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.

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

How to solve div2 E-Minimum Modular? Thanks in advance.

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

    means "ai - aj is not divisible by m. So calculate the differences of all pair of integers.

    We check that "if we choose m to modulo, we can do the array satisfies conditions?" for all integer m until we find m from (n-k).

    Answer ≤ 106 + 1 because if we choose 10^6+1 for m, obviously it satisfies condition.

    When we search about m, all we have to do are research about multiple of m and get the array of "Which pair of integers are same modulo m". If the size of array exceed 10(), give up search.

    In this solution, the order is O(N^2+a_max log a_max+k^2 a_max) because O(1/1+1/2+1/3+...1/a_max)=O(a_max log a_max).

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

      Similar solution of mine in Java (3754545) gets TLE. I think time limit is very tight for java solutions. Any thought?

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

        Replacing ArrayLists to Arrays makes it much faster. I got AC. Lesson learned.

        Thanks.

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

When will the editorial be published? I really want to know how to solve Div1E...