jzzhu's blog

Codeforces Round #257
By jzzhu, 10 years ago, In English

Hello everyone! Codeforces Round #257 is coming soon.

In this round, you are going to meet our friend Jzzhu. Though my id is jzzhu, the real Jzzhu isn't me, and he is a very cute boy. Now he is facing some challenges. Can you help him to solve the problems?

The problem setters are gagaga5-gagaga and me, and thank ydc, jzc, fanhqme for testing.

Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform.

Have a good time with Jzzhu!

UPD

In Div. 1, scores for each problem will be 500-1000-1500-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-2500.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

1.semiexp

2.kutengine

3.rowdark

4.YuukaKazami

5.mruxim

Division 2:

1.swenyoo

2.chm517

3.Shinka

4.TBH

5.silly_girl

You can find editorial here.

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

Comments Comments (207)
| Write comment?
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Wow! Another Chinese round!

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

    But Codeforces Round 256 (Div. 2) was a combobreaker :D

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

      Another combobreaker is just coming =D

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

      a Div-2 only round cannot actually be called a combobreaker :D

      Still, Div 1 rounds are all Chinese :D

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

    I think the reason of the continous Chinese Rounds is Stand Alone Complex ( a name of a interesting phenomenon in Ghost In The Shell TV version ).

    → Reply
»
10 years ago, # |
  Vote: I like it +32 Vote: I do not like it

chinese round month..

and maybe MinakoKojima's round will be come out this month

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

    I hope not :(

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

      Gold Bear!!!! Amazing!! I feel surprise to see such amazing id in codeforces

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

    I have thought the #257 is MinakoKojima's round..... Wish his round come soon~ And the multi-university training come soon~

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

jzzhu != jzzhu ("the real Jzzhu isn't me")

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

I like Chinese rounds because it starts early, but Div1 E is always too hard :v

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

    Seriously, Are YOU talking about Div1 E?

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

      Yes, although I'm at Div2 :v

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

      seriously , why a Div2er like me can't talk about div1E ?

      → Reply
»
10 years ago, # |
  Vote: I like it -83 Vote: I do not like it

Chinese round, Interesting.

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

    Why do you idiots give me negative points? Fucking shit.

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

      You are a Fucking shit.

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

        Look at ur poor rating, WOW such a idiot! Do you think you "Expert" have the right to scold me?

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

          Look at your poor minus contribution, WOW such an idiot! Do you think you "Jackass" have the right to leave a comment?

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

            You life quality depends on your skills (your rating replies parts of it), but not on the fucking voting system. Just idiots with blue or green or even less like voting all the time, because they do not have the ability to solve problems HAHA!

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

              Well, I downvoted all of your comments here except the first one (not because I like it, just because I don't care). Also, if I was a mod, I'd ban your sorry ass into the worst corners of Internet! What do you say to that?

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

                I would say you are just a fucking shit.

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

                  Suddenly quiet about rating, are you?

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

                  Why are you guys quarrelling about nothing?

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

                  Nah, I'm just teasing him :D

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                  ← Rev. 2   Vote: I like it -19 Vote: I do not like it

                  Let's solve problems.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                  ← Rev. 2   Vote: I like it +18 Vote: I do not like it

                  This is codeforces but not /b/

                  → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              ← Rev. 3   Vote: I like it -9 Vote: I do not like it

              Hey, Of course having strong communication is a skill and if you can call it "fucking voting system", It's much easier that call ratings "the fucking ratings system".
              But something makes me think, Your rating is just 1766 and just with 2 contests that is shows there is not stability in your rating necessarily but you are this kind of proud of your self and self-conceited. I hadn't seen even tourist speaks like that.

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

    Seems that Chinese rounds are interesting, but you guys are more interesting! 233333333333

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -17 Vote: I do not like it

    _

    → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It is the third contest which I can not participate because of IOI's schedule. When this contest started, we was on the bus.

I can't participate last 2 contests too, because I must sleep enough to participate IOI contests.

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

    Best wishes~! Gl&&Hf in IOI~!

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

      Thanks. I won a Bronze medal.

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

        Is it the last IOI that you can participate? If you were born in 1997 according to you id, you may participate in ACM-ICPC next year~

        → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Another chinese round. I like chinese rounds because it can involve math and sometimes good problems.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

A Fermat prime number round!

For more info about Fermat theory, click here. It's a theory about prime numbers that are a power of 2 added by one.

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

    Hah, came here to say that we should celebrate that round, because that is surely last Fermat's prime number round in our lifes :P. Rounds FF, then 100000000, then 2^2^3 + 1, which is Fermat's prime. Nice combo. Does anyone know interesting properties of 258 :P?

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

      Depending on what's interesting:

      Wolfram Alpha says that it divides 85^2+1. And its prime factorization is quite simple.

      OEIS gives just 1 interesting result: the number of Delannoy paths from (0,0) to (4,4) that don't start with a (1,1) step.

      The worse thing is that we'll probably never get rounds 109 + 9 and 109 + 7. In any base.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it +74 Vote: I do not like it

      Since Codeforces round 255 everyone is finding an interesting thing about the contest number and it remembered me something!
      Few months ago, our teacher proved us that every number has a interesting properties!
      For example 1 is the first number, 2 the first even number, 3 the first prime odd number and so on.
      And the prove:
      Assume that it's not true! So, spot the first number that has no interesting properties, This is an interesting properties itself!

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

        cool)

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

        This seems familiar to me, may you name the teacher?

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

        Is your teacher name َ"Ali Ghasaab" :)? He knows me very well :) give my regards to my best ever teacher...

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

          No, But he was my teacher 3 years ago.

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

        It reminds me of a theory like this: every number can be named not more than 50 chars. The proof is similar: if there exists a number that cannot be named less than chars, it can be named as "The first number cannot be named in 50 chars". It is 44-chars name.

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +150 Vote: I do not like it

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

    hard contest or easy!!!

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

      Yes. Or medium.

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

        256؟؟

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

          ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็ส็็็็็็็็็็็็็็็็็็็

          What, are we having a contest in posting random stuff?

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

            what???are you seying!!! ???

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

              No, that should be my question. When your post only contains a number and 2 weird characters, I can only reply in kind. Except my weird characters break through comments :D

              → Reply
»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Chinese here, Chinese there, Chinese everywhere :P after these 3 contests my mom will see me just like JACKIE JOHN

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

hope an easy contest! :)

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Chinese round again.I'm glad to see it.RP++

→ Reply
»
10 years ago, # |
  Vote: I like it -11 Vote: I do not like it

just Ten minutes remain but a problem rush in my mind: But i will be glad if any of you answer my question : http://mirror.codeforces.com/blog/entry/13102

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I like Chinese round! Good luck and have fun for everyone!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the problem with hack???

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    div2 B with

    1000000000 -1000000000

    3

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

    For Div2, Problem B.
    A lot of participants didn't noticed that (x-y) can be less than -(10^9+7).

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round! I submitted three. Hope they pass systests!

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any hint on C except for Blossom Algorithm? Nice round anyway.

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

    I think we can do a bipartite matching using dinics etc. Too bad I couldn't implement it during contest though :(

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

      I thought of that too, but how would you be sure that if A-B was chosen (like A in the first set, B in the second), B-A won't be?

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

        Yes, you are right. Maybe this is not the intended way. Now I too am confused.

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

        you can consider only the edges that connect a smaller number to a bigger one (not vice-versa)

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

          I think that it still won't work this way. Think about connecting A-B and B-C (both of them forward edges).

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

    I used sieve of Eratosthenes.

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

    Since you want a hint: Greedy. And prime sieving, yes.

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

      I solved it in a greedy way — by "solved" I mean it got accepted. But I have no idea why it is correct. If you know why, can you write why it works? Thanks

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it +60 Vote: I do not like it

        Here's a quick proof:

        Clearly we cannot do anything with primes greater than . (Let be a prime, then it can only be matched with an apple with number at least 2p. But 2p > n. So we cannot match p.) We can't do anything about 1 either, and if there are an odd number of apples remaining, we must remove one (since all groups have two apples and thus the total number of apples used is even). My solution makes sure that all the remaining apples are matched, which due to the above proof, is maximum.

        My solution works as follows:

        • Generate all primes below n and reverse the order, so we process from the largest prime.
        • For each prime p > 2, observe the apples p, 2p, 3p, ..., kp where kp ≤ n < (k + 1)p. We ignore all apples that have been used before. Now, greedily take the two apples with largest numbers together.
        • In the case we are left with a single apple p, then observe that 2p must be used in the previous group. Replace it with p, so we keep 2p to be used later in the final pass.
        • Finally, for prime p = 2, we greedily match every even apples remaining.

        It shouldn't be hard to see that all apples not in the form 2p or 2k are used in step 2, and all remaining apples (except probably one) that are not used in step 2 are used in step 4.

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

      Sorry for double post but... Chaotic_iak, you made over +500 in less than two months! Amazing progress, my huge congratulations :)

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

        Thanks! I think that's because the problems I did fit with my ability, and the remaining problems I didn't do are hard enough that not many other people did those. :P

        → Reply
»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it

very WEAK pretests....I'm really afraid of systests...

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

all problems was tricky thanks

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what was to be done in div-2 C ....

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The solution doesn't exist if k > n + m - 2. In the ideal case, after making k cuts, the remaining pieces have equal area. Sometimes, this is not possible.

    First, try to make only vertical cuts in the best way (i.e the minimum area is largest). If k < n - 1, we will have ⌊ m / p⌋ columns in the minimum area. So area is that number multiplied by n. Same way try to make only horizontal cuts.

    In some cases we cannot make only horizontal or only vertical cuts, so we have to do both. Which one to do first? Try both possibilities, i.e. first vertical then horizontal and then first horizontal and then vertical, and then print the maximum resulting area (of the smallest piece) as answer.

    My solution: 7171855

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the approach for DIV2 D ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used Dijkstra algorithm to find the shortest paths from the capital to every city. Then I destroyed the trains which aren't used in the various shortest paths. I'm not sure, however, if this works.

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

    Nevermind I got WA

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Dijkstra... When we finish it, we must calculate unused train roads.. And if we have a choice what type of road to use we must use not-train road..

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

    You can use Dijkstra to determine the number of trains are used in the shortest paths from the capital to the other cities.

    Plus a little modification that if you can reach a specific city as fast as the train, you pick the road not the train.

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

    If you need it, here there is my fixed code: http://mirror.codeforces.com/contest/450/submission/7179339

    → Reply
»
10 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Problem D is very well known. Have no idea where the tester was looking at. Also naive solution works 3.3 seconds on Java, while TL is 2 seconds. I guess, one may got AC with the same written in C++...

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Pretest can be weak because I don't trust my code but I accecpted

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think there will be a lot of problem C div2 fails.

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

    me too, because I think I will fail div2C

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

    By the way, what was the intended approach for A div1? The limits suggest some kind of greedy formula.

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

      Either put as many horizontal cuts as possible (obviously with extra vertical cuts if there are too many cuts to do), or put as many vertical cuts as possible (with extra horizontal cuts if necessary).

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

        "Proof": With a horizontal cuts and b vertical cuts, you divide the chocolate into (a + 1)(b + 1) pieces, so the minimum area cannot be larger than . If you want to maximize this, intuitively you need to take (a + 1)(b + 1) as small as possible. Since a + b = k is fixed, the best you can do is to minimize one term as much as possible, because .

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it +13 Vote: I do not like it

          Note: My solution failed, so this might not be correct.

          EDIT: Note to self: n rows mean n - 1 horizontal cuts, not n. 7174814

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

          I used the same idea and also failed, but it is not a proof because nm/(a+1)(b+1) is just an upper bound and you cant conclude that much.

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

            That's why it's only a "proof", with quotes, and that I say about "intuitively". It's not rigorous yet, although I felt I was confident enough with the intuition that I went with it.

            Accepted with a fix (was a faulty reasoning that n rows means n cuts): 7174814

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

              I fixed mine too, didn't notice int could overflow! :'(

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

          My accepted solution has a similar idea. Assume that our solution is obtained by t horizontal cuts and k-t vertical cuts. Then, the maximal smallest area is f(t) = n/(t+1) * m/(k-t+1). Note that, 0 <= t <= n-1, and 0 <= k-t <= m-1, then lo = max(0, k-m+1) <= t <= min(k, n-1) = hi. Finally, the solution is max(f(lo), f(hi)).

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

      Mine is to try 4 cases:

      1. Use all cuts across vertical side.
      2. Use as much as possible cuts across horizontal side and the rest across other side. 3-4. Same as 1-2 but in other directions, i.e. "horizontal <-> vertical"

      This seems to give the same answer as naive approach for all 1 <= n, m <= 100, 1 <= k <= 200. So I didn't look for anything else.

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

    I use greedy for this problem and don't know it is false or true

    → Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

http://mirror.codeforces.com/contest/449/submission/7169365 — that code will surely get accepted :DD

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

    How did you know? :-O

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

    IT GOT ACCEPTED :O00OO00OOOO!!!???????

    "3+m*(27-6*n)+n*(-17+4*n))%mod))%mod*powmod(180,mod-2)"

    Unbelievable :P.

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

      Nice chinese problem with short and beauty solution, isn't it?)

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

      I think Mathematica is your good friend in dealing with this kind of problems. :P

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the observation in Div1 D that it is enough to sum the groups of k from 1 to 20 instead of n, correct ? If it is correct how will it help in solving the problem ? I tried to use the dp state (index,k) but I had no idea how to keep track of the mask till this index.

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

The system testing is start

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

was there an easier solution for div2 B instead of doing matrix multiplication w/ the linear recurrence? I thought this was a hard topic for a div2 B problem D:

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

    Yes, the sequence is periodic. You could calculate only first six terms.

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

    Actually there was a trick:

    Every sequence is the repetition of 6 numbers:

    x,y,y-x,-x,-y,x-y,...;

    so you could just find which he was trying to search (using division and mod). Hope this helps

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

problem B has 4 pretests.....WTF!
WHY????????

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

    such weak pretests... that make a lot of coders FST 5.....

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

    I'm only sad I had no idea pretests were this weak, otherwise I would have hacked Div1-Bs like crazy :P

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

    I forgot int64 but got AC :)

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

    I've seen a guy whose 4 solutions falled on finals.

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

Back to home (div 2) :D

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2-C problem?? please with proof 233333

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Back to Newbie.

la la la..

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

    Back to Specialist.

    la la la..

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

      Back to red.

      la la la..

      :P

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

        Back to blue lalalala :D With 1500 points ahahah. A point less and i was still green lol

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

          Back to Blue lalalala :D 1699

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

      Hope I can become specialist after rating update. :P

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

      Hey you got three accepts you will either go to Candidate master or your rating will increase !

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

    I become green !

    la la la -_- :'(

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in Div 2 what is the solution for problem C i got WA what i thought of is there is a 3 cases

1) not applicable if k > m+n -2 2) 1 if k > max(m,n) -1 3) n*m/(k+1) else

?!!

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    3 3 1: Correct answer is 3. Your case 3 gives 4.

    4 4 4: Correct answer is 2. Your case 2 gives 1.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C in Div 2 was crazy ;(

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the system testing so slow..?

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

Congratulations semiexp !

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -70 Vote: I do not like it

In my opinion this round should be unrated because it wasn't an unusual round...there were very few pretest. What do you say?

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

    IMO no. weak pretests allow hacks!

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

    "it wasn't an unusual round" = "it was an usual round" ?

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

      Yes. Also, "usual" rounds have weak and few pretests.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Thanks to your hack, I've fixed my Div2 B :D

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

          no problem, i also got 100 pts. :) so you should always write weak code and correct it at last moment. may be not as i might not be able to help again.

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

    Very funny.

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

    Anyone saw you before you come ?

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

    Thanks to week pretests, I was able to enjoy hacks.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find a flaw in my solution to Div.2 D / Div. 1 B? Link to code: http://ideone.com/opD81j

My approach was to calculate the shortest paths to every node from the capital with and without train tracks. Then I delete off as many tracks as possible.

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

    try this testcase out

    3 1 2
2 3 1
2 1
3 2
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you explain more?

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

        as he use the calculated shortest paths to every node from the capital without train routes, it'll be wrong in case the graph is not connected without some train routes :)

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, help me the problem C div 2? :( I'm try it in 1h30 but it was wrong :(

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

EDIT: Resolved now.

I got WA in http://mirror.codeforces.com/contest/450/submission/7160858, but seems other solutions are accepted with same answer ?! What am I missing ?!!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be any editorial for these contests?

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nearly back to grey...... Anyway just keep on fighting!

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I was a green coder before this contest,but now I'm purple!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain div2D/div1B?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Although problem C div2 was hard, but I enjoyed the problems. Especially problem B div2. Thanks for your nice problems.

Won't there be any editorial?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hard round i ever seen... very tricky ..but interesting problems..thanks for setting this contest...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish the pretests for B and D weren't pointless... I got first submit AC on all pretests, and systest fail on the first non-pretest. THE VERY FIRST ONE. TWICE.

And it's not like there were too many pretests, D had 7 and B just 4. Would it have hurt too much to add several more? Not to mention, there was no real maxtest (just one with unit lengths) included in the pretests of B, which is IMO not a good idea regardless of the problem.

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

    BTW, many wrong solutions failed pretests on B)

    I think it was made this way to increase number of challenges. But most of us just did not found out during the round that pretests are so weak.

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

      Yes, it's a given that many solutions would fail if there are just 4 pretests, out of which 2 are samples. Which is why I'm complaining that the pretests were few and bad. Usually though, it should be "it seems this problem has many tricky situations -> let's try hacking", which doesn't seem like the case with B.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For those who got why Div1 A failed so many times: why did Div1 A fail so many times? What's the general flaw pattern?

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Nice round, but how about editorial?)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please any one explain me how to solve div2 C briefly . waiting for editorial but of no use.

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

    I just a few words, you simply have to observe that you divide up one side of the chocolate as much as you can and use the remaining cuts on the other side of the chocolate. You do this for both sides.

    The intuition behind this is quite simple. I think someone above this has already explained but I will explain it here as well. The number of pieces after you make a cuts on one side and b cuts on the other side is (a + 1) (b + 1), leaving the min area to be (nm) / ((a + 1) (b + 1)). You want to thus minimize (a + 1) (b + 1) which is equal to ab + a + b + 1. Since a + b = k, you just need to minimize ab.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      bboy_drain We need to minimize the value expr=ab i.e expr=a*k-(a*a).How can we say that value of expr is least when you divide up one side of the chocolate as much as you can?( I'm talking about the case when k>m-1.In this case,how can we say that by keeping a=( k-(m-1) ),we get the least expr value? ).

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

        This is through intuitive math thinking. Let's say k = 6. Let's list out the possible values of ab, such that a + b = k.

        a = 1, b = 5, 5 a = 2, b = 4, 8 a = 3, b = 3, 9.

        So as you can see, the smaller a is, the better, thus we maximize the cuts on one side to minimize the cuts on the other side. The proof is basic math, see if you can prove it yourself.

        → Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

gagaga5-gagaga, jzzhu any updates regarding the editorial?

→ Reply
»
10 years ago, # |
  Vote: I like it +58 Vote: I do not like it

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think the pretests are becoming too much weak. Sometimes it makes me wonder if they are even necessary at all. I think they should be made a little more stronger. Recently I've seen many codes of strong coders who are way beyond my level to pass on pretests on one shot but fail within a few cases of the main test cases. And after checking them, the cases were actually simple rather than medium or strong corner cases. Sometimes this becomes a little upsetting. I don't know if others feel this way but this is just my opinion.

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

    It depends on what they are trying to achieve. In the competitions I've participated in the past the solutions were only checked on the samples from the problem statement, at best, so you had to be think carefully before submitting. However, you also got partial score if the solution failed some tests, and no penalty for late submissions/resubmissions.

    It certainly makes more sense to have stronger test cases here, since even a small mistake means you get 0 for the problem, and you get penalized for resubmitting the problem anyway. Still, it doesn't mean that they should include all corner cases (which seems to be the Topcoder approach).

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

      In haven't participated in almost any competitions where the solutions would only be tested on samples. IOI, ACM ICPC, CF rules aren't like that, and many competitions use one of them. TC doesn't really count, because they often have many samples, including large tests. Yandex Algorithm, not. GCJ, not. CodeChef: ACM rules. Various ACM trainings: ACM rules. Most secondary school competitions: IOI rules. Uh... Hackerrank: even more detailed than ACM rules. To be honest, I haven't participated in a competition without feedback for months, and I do almost all there is.

      There are just a few secondary school competitions (like COCI or USACO) that have no feedback.

      The reason for it is clear: you don't have to think carefully before submitting, because a small unnoticeable bug can make you fail easily. If you understand the problem incorrectly and it still fits with the samples, nothing can help you. If you have a small bug that only shows with large/specific cases (yes, there are such situations, converting subtrees to intervals by inorder traversal is an excellent example), you don't have to find it even if you generate dozens of tests and check your code against a bruteforce. Your code can fail on large corner cases. Etc. Even if the problem has partial scoring, you can still fail horribly because of missing a special case (I got 0/100 on IOI 2012 Rings, with exactly one WA in each of 5 subtasks, even with full feedback, and you can easily guess why).

      I don't know if TC really includes all corner cases in samples. It's usually "several small samples demonstrating the problem, sometimes some corner cases, 1 or 2 large samples". I've even had solutions that were so horribly wrong I fail to understand how I could ever write such bullshit, and yet passed all the samples. Besides, their samples are supposed to be the same thing as pretests here.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D1-D using inclusion-exclusion? What's the idea?

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

    Let X denote the input set. . allzero(y, S) returns true if and only if the i-th bit of y is 0 for (similar definition for allone). Then the answer would be . requires m = 20, but I will use m = 2 for better illustration. It's trivial to generalise to the case where m = 20.

    By inclusion-exclusion principle, we know:

    .

    . . . .

    If all Tmask are known, we can simply loop over all possible mask values (220) to get the answer.

    Now let's turn to Tmask. Tmask is the number of element x, such that x&Tmask = Tmask. Informally speaking, if some bit of Tmask is 1, the corresponding bit of x must be 1, otherwise there's no constraint on x. 

        for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
    }
    for (int j = 0; j < 20; ++j) for (int i = two(20) - 1; i >= 0; --i) {
        if (getbit(i, j) == 0) cnt[i] += cnt[i | two(j)];
    }

    Prior to the j-th iteration, cnt[mask] would be the cardinality of the set of x, such that bit 0 to j - 1 meets the condition I mentioned above, bit j to 19 must match precisely between x and mask. Executing the j-th iteration would loosen the constraint in 0 values at the j-th bit of mask.

    The overall time complexity is 20 × 220.

    → Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

My rank changes from 192 to 191 and silly_girl is not from top 5 as writer mentioned is this a cheating case ?

→ Reply