boleyn.su's blog

Codeforces Round #221
By boleyn.su, 11 years ago, In English

Hi, Codeforces Round #221 will take place on December 24th at 18:00 MSK for both divisions.

Problem setters are whd, oGhost and boleyn.su. This is our first Codeforces Round, and we hope it will be a good one.

We'd like to thank Gerald and alpc104 for helping us prepare this round, and MikeMirzayanov for bringing all of us a place to compete and communicate with others.

The score distribution will be announced before the contest starts.

UPD1: The score distribution is 500-1000-1500-2000-2500 for both divisions.

UPD2:

Congratulations to winnners and Merry Christmas to ones who celebrate it today!

Div 1:

1.Touma_Kazusa

2.al13n

3.rng_58

4.hmspmy077

5.uwi

Div 2:

1.bohuss

2.Tyg3R

3.xhsong

4.adamant

5.Kira96

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

Comments Comments (190)
| Write comment?
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -38 Vote: I do not like it

Hope the contest won't be like the last contest( Hard && Unrated ). Good luck to eveyone!!!

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

Good luck ... :)

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

Maybe people can already assume that every round announcement has some kind of grateful acknowledge to MikeMirzayanov, since it's becoming a bit boring to read that part every single time.

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

    then don't read that part! :D

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

    +1!

    It is more like fetishism. We really have to eradicate this practice.

    UPD: no disrespect was meant to Mike at all.

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

If this is the last round this year...

HAPPY NEW YEAR TO ALL :D

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

    The last round 's Good Bye 2013. It will take place on the last day of this year :-)

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

Why this blog isn't on the home page !?

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

Contest in Christmas Eve? And on top of that — at 18:00? Weird idea. I'm not familiar with Russian traditions, but in Poland at that time we usually gather with family around table and celebrate Christmas Eve :P. Other days will be better or at least earlier hours. Even though I will try to compete :P. In Poland it's not that bad hour, because it will be 15 :P.

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

    Pay attention to where the three round makers come from.

    They come from Renmin University of China

    The round will take place at 18:00 MSK means 22:00 CST.

    BTW, as a freshman,it's always hard for me to make a decision whether I should take part in a round start at 19:30 MSK or not , because if I do, I have to coding from 23:30 CST to 01:30 CST while my roommates are sleeping, which may bothers them.(In my school, a student should never stay outside domitory after 23:00)

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

      Wouldn't the round writers have it better if the round was earlier?

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

      Are you sure that your roomates are sleeping at 23:30 CST? hehe

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

    Christmas is not celebrated on 25th of December in Russia, see this wikipedia link. And even on 7th of January Christmas is not celebrated that widely comparing to how they celebrate it in Europe for example. In Russia people mostly celebrate New Year.

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

    The Orthodox calendar isn't affected by the Gregorian correction (not everywhere, though), so Christmas in Russia should be shifted to 13 days later. Still, 24th this late is not the best choice.

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

    You really are in no position to comment about "no-lifes" on my youtube videos if you plan on participating in a contest on 3pm-5pm Christmas Eve. ;)

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

      OK, you convinced me. Tomorrow at 3pm I'm going to watch your whole screencast :P.

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

      Yay, I participated and took in my opinion really good place — 38th :D!

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

Wow, three problem setters Chinese from RU! Look forward to it!

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

    In fact, RUC is short for Renmin University of China, while RU is not.

    By the way, I was born in Chongqing. It is good to see students from my hometown attending our contest. Good luck and have fun!

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

king base!time is good for chinese,thx for setter

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

Good time for chinese..

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

Люблю задачи от новых авторов)

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

Looking forward to it ! When the contest ends, it will be Christmas in China and we will have to go to school as usual ...

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

I love this contest!

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

Hope a better Contest than the previous one... That was not a Contest...

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

hope every contestant can have fun with the problem set :D

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

Have you changed the contest time or i need some sleep :) ?

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

Up-vote this comment if you can :P

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

    It is very hard. We can't. Sorry.

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

    Let me guess. After seeing some people in the last two contests, asking for downvote and getting them, you thought this would work!? If only it was that easy :p

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

Good Rate on Codeforces and Happy New Year))))

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

10 minutes before the contest and no score distribution published!

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

    Surely we should unregister and not participate in the contest if we don't know the score distribution.

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

    just solve problems and have fun :)

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

Just for Remember you said
The score distribution will be announced before the contest starts.

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

    Chill. 2 more minutes left. That's like 120 seconds. Plenty of time to update the score distribution.

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

      Now it's 30 second only do you still think that ?

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

        I posted it 16sec before contest started.

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

Power belt, I have late for contest and registration. WHY registration starts at late evening? Should it be possible to open registration 1,5 day before contest?

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

Merry Christmas and Happy Halloween (Note : OCT 31 = DEC 25 :D )

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

Maybe I have a chance to go to div1...thx...

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

nice contest!,but what is the algorithm to solve problem C DIV 2 or problem A DIV 1?

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

    C is pretty simple actually if you think of the reason why the setter used the digits 1,6,8,9. You can get all remainders when divided by 7 for some permutation of the digits 1,6,8,9. That is for every number x in {0,1,..6}, there exist a permutation of 1,6,8,9 such that when that permutation is divided by 7, it leaves a remainder of x. I think with this hint you might be able to complete the solution.

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

Will there be a tutorial published?

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

Yeah.. Div1 is too hard to me.. I'd better back to div2...

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

Saw few people use sort in problem B div 1. O(n*nlogn) should get TLE right? I went out of my way to use bucket sort to keep it O(n^2).

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

    Sorting? I'm kinda scared now. I didn't use sorting. At all.

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

    I didn't use sorting too, I think n^2*logn should TLE.

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

    5506448

    Sorting, no TLE =)

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

      Okay this is weird. I generally assume, 10^8 calculations take 1 second. So O(n*nlogn) is (5000*5000*12)/10^8 = 3 seconds. Time limit is 2 seconds. Since it didnt get TLE, I guess CF is a lot faster than I assumed. So how fast is it? I did the bucket sort for nothing :(

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

        It seems like the compile-time optimizations by GNU C++ are able to make up for it somehow.. Even though that some solutions that used sorting were either hacked or didn't pass the systest, so it's kind of tricky to guess whether a solution will pass or not just by looking at the source code.

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

    mine was O(n*nlogn) and it passed... :)

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

Is cin very fast on codeforces? I was surprised that cin solutions worked in B.

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

    At least it is fast enough with this: ios :: sync_with_stdio(false);

    I always use cin in CF and until now I haven't get a TLE by it.

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

    according to my testing, on GNU c++ 4.4 and above cin/cout work very fast and compareable to scanf/printf :p

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

    I think the reason is codeforces judges is really fast.

    At beginning, we do not want n^2logn solution pass, but failed to generate a testcase. I am really surprised by the speed of judge computers.

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

      my n*m got TLE.

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

      My O(N.M.logN) get TLE ! be happy :)

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

      Yes, I saw a solution that uses cin without sync_with_stdio, sortings of n elements n times, and push_backs n2 times — still worked under 2s :)

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

      My solution with cin get TLE. 5505467

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

        It seems it was quite close to the boundary.

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

      my solution 5506320 O(N^2) using scanf("%c",&x); got TLE, change it to x = getchar() got AC 5511177 under 0.5 s, i wonder why is scanf("%c") so slow ?

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

        Cause it parses format string "%c" on each query, at least.

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

        My O(n^2log(n)) solution 5515627 and O(n^2) solution 5515601 actually got the same running time. But during the contest I use scanf("%1d", &a[i][j]) to read the digit one by one, and it turns out the this is the bottleneck in my TLE code 5510016 ..

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

Problem Maximum Submatrix 2 is essentially exactly the same problem as http://www.ceoi2009.ro/tasks/logs.pdf :(

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

Need hints for problems C div 2 :( soon :D

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

    That problem looks very artificial to me, these numbers must have some magic.

    So I submit a crazy solution 5502926: until find a solution, do some random swaps, and if time out then output 0. And it passed system test.

    Seems it can't be no solution, but I don't know why. :)

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

      For every 0 ≤ r < 7 there is a permutation of {1,6,8,9} that (being read as a 4-digit number) yields remainder r when divided by 7. Choose the right one and append all the other digits to it.

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

        Even more than that, for every integer a, there exists a permutation of {1, 6, 8, 9} that is appended to a and makes the result number divisible by 7. :)

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

      You can rearrange 1,6,8,9 to form all mods from 0 to 6 -- so just order the rest of the numbers in any order, then output the correct permutation: http://mirror.codeforces.com/contest/375/submission/5507138

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

      For each 0<=r<7, there exists a permutation of {1,6,8,9} as (r*10 000 + permutation) % 7 = 0
      So, you choose a random order for the initial number (just conserve one 1, one 6, one 8, one 9 and count number of zeros), then you calculate the rest of this number, and you choose the valid permutation of {1,6,8,9}.
      You can then add as many 0 as you want lastly.

      sample: 123456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869
      (and with zeros:) 1230000456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 -> result = 2345718690000

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

Very interesting problems, and no complex algorithm. LIKE it:) [Although i have solved a little tests] Hope u can papare more contests in the future!!

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

Are u kidding? N log^2 N solutions in D that use dat slow c++ map pass with a great handicap. Well, maybe I'm unfair cause I spent alot of time doing N log N solution, but I bet on weak tests.

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

    100000 * 18 * 18 < 100*10^6

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

      That's too rude, u don't assume that map is a redblack tree and we keep pairs in it.

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

        One of logs, which going from merge is very small. Also maps are not very big mostly. Probably this two compensate.

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

          There are even O(n * sqrt n * lg n) AC solutions, I really believe that the nature of the queries, at most n different ranges, (without partial overlaps) really improves O(n sqrt n) bound.

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

        I used a hash map (unordered_map) instead of a normal map, and the fenwick tree is tremendously fast, so the additional log n factor is quite reasonable, I was skeptic during the contest (and even tried to find an O(n lg n)), it also seems that Codeforces got some speedy machines.

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

    I think you did something wrong, O(N log N) solution isn't very hard. See 5512577.

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

      Well done, but that wasn't actually a topic of my message =)

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

      Indeed, but it was tricky to realize that is actually O(n lg n) during the contest, those who saw that all the updates are O(n) amortized mostly implemented an O(n sqrt n), the rest just used a Fenwick tree. BTW it would be interesting to find the worst case input for the O(n sqrt n) approach, here the tree structure makes the query ranges quite singular (no partial overlapping), maybe in this case is even better, O(n lg n) or even O(n)?

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

And for second time in a row a purple coder takes down the Div 1. Congratulations, Touma_Kazusa :).

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

    In fact, she is red for a very long time.

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

      In fact, she is one of the top rated users.

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

        Can you tell us who is that?

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

          YuukaKazami

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

            :(

            Are you sure?

            The rules: "Don't create more than one account, if you have forgotten the password, use the password reminding system."

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

              Even if the rules should be applied more or less to everybody, I don't think it was an attempt to cheat, or because the password was forgotten, but an other reason (which one, I don't really know).
              The only thing that seems unfair it's that will affect rating changes of all others contestants.
              I mean, I suppose that being beaten by a purple when you are red/orange make your final rating lower than if you're beaten by a top 10 user...

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

in problem D,why my O(n*m) solution get tle? 5509804

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

    Try to use getch() or smth other, not cin.

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

      Getch()? Pff. ios::sync_with_stdio(0); is enough to use cin and get AC =)

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

        5511181

        Just as I said.

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

          can you explain me why it is so improtant? and what this doing?ios::sync_with_stdio(0);

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

            It is turns off synchronization with stdio (scanf/printf), so cin/cout can work faster. More information here.

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

    Well, I guess because of this line

    ans=max(ans,(j-i+1)*num[j][i]);

    This line causes many memory hits, you need to access the array in row major order

    swap j, i in the loops or in the array dimensions (make it num[i][j])

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

    i think problem is with your input.

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

    Try this.

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

thanks pretest #11, for problem A (div-2).

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

Could someone explain the solution of Problem D? Thanks in advance

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

How to solve E div 2 / C div 1?

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

The "Custom test" feature here limits testcase input to 256KB, but the maximal testcase for "Maximum Submatrix 2" (Div 1 B, Div 2 D) has a 5000x5000 matrix (25M elements), so it seems impossible to properly test the maximal case for TLE against Codeforces servers (even if you hardcode the testcase in the source, you're circumventing the time taken reading input). Is there any good strategy for handling this, or any way around this restriction?

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

    Use a genarator code.

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

      That works for hacking, but not for testing your own solution in custom test.

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

        Oh yeah. My bad. I misread. Maybe the custom Test is not meant for stress testing.

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

F@uk...Pro D,,my time is n*m*logn.....TLE.= =

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

What does I.O.U (name of problem B of Div 2) stands for?

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

I don't understand why in B/D n<=5000. Many people submitted correct solution, but because of using (in my case cin) got TLE. I think n<=1000 would be enough for solutions with bad asymptotics to not pass.

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

    I got n*m solution but because using "cin" got TLE.if n <=1000 than it can be solved also n*m log m and it did not want to author,I think author is strict in this issue.

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

Am I missing an easy solution to Div1 D or so many people have managed to code solution that resembles mine? I've done it by an algorithm which resembles heavy-light decomposition. I've done DFS, computed some data for every subtree and in one vertex I copied the data from smaller subtrees to the biggest one, which results in O(n log n) solution. I was really satisfied to get this problem accepted :).

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

    Can you explain more detailed your solution? In Russian comments here we discussed accepted solutions in O(Nlog2N) with the same "copy data from smaller subtree to the greater one" idea, but the data was stored in log-time containers, such as Cartesian trees and Fenwick trees, so asymptotic was O(NlogN·logN) = O(Nlog2N).

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

      There is also a solution with complexity O(N * log^2(N) + (Q + N) * sqrt(N)) without advanced data structures, by splitting the set of colors into heavy and light sets such that light set contains colors that have < sqrt(N) elements and heavy set contains colors that have >= sqrt(N), then the light sets could be processed with simple dp on tree, and heavy sets could be computed using the "copy data from smaller subtree to the greater one" idea because there is at most sqrt(N) heavy colors.

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

      Here is my code that got accepted: http://mirror.codeforces.com/contest/375/submission/5508056

      For every vertex v I call DFS(v, log) where log is some number between 1 and log n. If vertex v has children v1, ..., vk and vertex v1 has the biggest subtree, I call DFS(v1, log) and DFS(v2, log + 1), ..., DFS(vk, log + 1). If I call DFS for vertex v with corresponding argument log, after calling DFSes for its children I want to have some data in col_num[log], at_least[log] and ver[log]. For fixed color c, col_num[log][c] means how many there are vertices in this subtree with color c, for a number k, col_num[log][k] means how many there are colors c such that col_num[log][c]>=k and ver[log] is simpy vector of all colors of vertices in this subtree. Those data allow us to simply answer all queries in each vertex and update corresponding data in our parent in time O(size of our subtree) (if we aren't the biggest subtree's of our parent's children's subtrees) which results in O(n log n) complexity of whole algorithm. If our subtree is the biggest subtree of our parent's children's subtrees, our parent just treats our complete data like its initial data and update it by other children subtrees.

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

Power of MS C++!!! I think if lots of TLE codes submit their codes with MS C++ compiler,
they will get accepted!
Accepted Solution: 5511246 and 5511362 and 5511553
TLE Solution : 5511075 and 5507435 and 5505552
I submitted these TLE solutions with compiler MS C++ and got AC!
What is the real reason?

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

    problem B sux

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

    you can't strongly say that MS C++ is better than GNU C++. The difference is that cin and cout have been defined differently in these two compilers. The time of cin in MS without ios_base::sync_with_stdio(false) and with it is really close, however there is a massive difference in GNU with ios_base::sync_with_stdio(false) and without it. But GNU is faster with syncing than MS with it. I can show u a lot of codes which got acceptance with GNU with syncing that same code in MS didn't.

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

Div.2 Problem D I add ios::sync_with_stdio(false); and pass.........

Can anyone help to explain?!

What a pity...

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

    cin works faster with ios::sync_with_stdio(false);

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

    Explanation here.

    Also some statistics here.

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

    I think it is almost always better to use scanf instead of cin.

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

      You're wrong. If you use cin with ios::sync_with_stdio(0); on GNU-C++ your solution may be even faster than with scanf as you can see here.

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

Feel quite disappointed about the problems setter (or the translator) of problem D div 2. You can rearrange the row but each col MUST BE ORIGINAL

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

Div.2 Problem D: priority_queue got TLE (AC in MS C++), push in vector and sort got AC :(

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

    I guess that why we usually prefer quicksort to heapsort :)

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

I don't know about you guys but I used a physics formula for Div 2 A. Is there any other solution?

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

Thanks for nice contest! It requires an ability to write fast without bugs not-completely-simple code in each task.

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

Can someone please tell me where my solution for div2-C is failing? I made use of the mathematical trick of finding %7 for large numbers.

http://mirror.codeforces.com/contest/376/submission/5506741

UPD: Found my mistake. Thanks to Zlobober ! :)

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

    Your idea is quite right but you should add your mp[remmod] to the end of the answer, because it will give the right remainder, but not 10^(len — 4) * right remainder.

    http://mirror.codeforces.com/contest/375/submission/5504410 -- my solution.

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

      Adding mp[remmod] to the end is wrong because that can cause leading zeroes.

      In any case, I found my mistake a while back and corrected it. :) Thanks!

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

        Well, you can add all zeroes to the end, as in the author's solution.

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

          Not quite. I'll give you an example.

          No zeroes in this case, so according to you I should add mp[remmod] to the end. But it is wrong.

          Test Case : 11689 Output : 18961 ( = 5 mod 7 )

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

It is realy unfair..... algorithm and and implement is correct only because of ios::sync_with_stdio(false); I get TLE....

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

    You should try to study more about the ur programming language sometimes :)

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

It was really best Christmas present, thank you very much and see you in DIV 1 :)

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

+100 :D

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

It is recommended to test the maximal case locally.
I think that it takes less than two minutes to write a code to generate maximal case.

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

+198 :)

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

First of all, thank you for preparing the problems for us. It was a nice Christmas Eve.

However, I would like to point out the problems is not very good (at least for me).

For Problem B, it is EXACTLY THE SAME with CEOI 2010 Day 2 Problem 1 Logs (the only difference may be the problem from CEOI asks rearranging the columns).

And for problem C/D, I cannot recall clearly the source of these problems but I have solved tons of problems based on the old idea.

I hope that Codeforces can have more problems with new idea instead of the old one. New idea may be easy, simple, interesting, ... but it is good.

Anyway, problem A/E is really nice (maybe adapted from Chengdu Onsite 2013?). I don't come up the solutions till now.

Thank you again!

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

    Well, if D has a nicer solution, than "move-info-from-smaller-subtree-to-larger" one with using some complicated data structures like maps, hashmaps, cartesian trees, fenwick trees etc (that are discussed above in Russian version of the site) then it would be great to know about them. Maybe when problemsetters publish editorial we will find more interesting solutions to it.

    And C seems very nice and interesting for me. Can you give a sample of the problem with the same idea? Moreover, if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem (but with such explanation in task the idea to store a mask of oddity for each object becomes much clearer and obvious).

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

      The Grove -- USACO 2006 January Silver

      As far as I knew, this may be the first time this idea appears. The problem can't become cooler by replacing the definition into something like "reach from the infinite point" since it must allow multiple pass of one cell. It is not that natural.

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

      If someone has read this and not my explanation few posts above — yes, instead of maps, trees and other stuff, you can use arrays :D -> http://mirror.codeforces.com/blog/entry/10034#comment-155315

      But one one drawback is that this results in also O(n log n) memory, there are other approaches with those more complicated structures which requires O(n) memory only. But if it fits into limits, there's nothing wrong with it :).

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

      "if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem" — imagine a closed curve with many selfintersections (those are allowed in this problem!). Could you clearly state what's its interior and what's its outerior? These 2 words are losing their meaning and the only thing that can tell them apart is this parity definition.

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

        Yes, that's exactly what I meant by phrase "authors have to explain what does that mean".

        hmspmy077 in his comment above showed much nicer task, that deals with that problem another way. For that task there is no need to define what interior exactly is, because it uses only the "walk around the connected figure" conception, which is much simpler to imagine and doesn't require additional clarifications.

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

    Problem A is not new at all — see there http://acm.timus.ru/problem.aspx?space=1&num=1095 There's about 2000 sucessful submissions on it on the most famous Russian online judge.

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

I did not write this round well,but I liked problems very much,thanks authors for contest.

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

How did people use sorting to solve Div2 D / Div1 B? O.o

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



More info

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

    Awesome work, like previous stats.
    How do you make such requests on this website to get data? wget parser?

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

      Thanks! :)
      If I get your question right, requests are made using XMLHttpRequest from javascript. After the received html data is processed, graphs are built using Google Charts.

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

Alternative problem for Div 1 A/ Div 2 C:

Is there a simple solution at this problem:
Find a permutation of a number n composed only by 1,6,8,9 digits (666,1689 etc...) divisible by 7
I tried to solve this problem during the thirty first minutes before finding my misunderstanding...

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

    As long as there's at least one occurence of each of numbers 1,6,8,9 in that number, it's the same as Div1 A :D

    For arbitrary numbers: if the input is small, you could do DP on (remainder,how many digits of each type you have left); if it's large, there are either few ways to solve it or a permutation should always exist, like numbers "16666666","61666666",...,"66666616" which give different remainders mod 7 — so it's enough to consider a random permutation of other numbers before it and choose the ending few digits that are good.

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

      Ok, so for larges numbers, we can't have perfect polynomial solutions (I mean, without using random) ? Anyway, thanks for this answer.

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

        I think we could get constant time solutions. Well, constant if we had just the occurences of 10 digits (if we don't limit ourselves to 4). Actually, digits with 7 possible remainders.

        As long as the number is diverse enough, there should be a small subset of digits such that there's a permutation of them with remainder x for all 0 ≤ x < 7; if there's such a subset, the length of the number is, in fact, irrelevant — no matter what permutation of the remaining digits we use at the start of the number, we can always pad it with the suitable permutation of our subset.

        The problem we got just specifies the subset for us: remainders "1,1,2,6". This is quite small, and I don't think any required subset (that doesn't contain any smaller required subset) will be much larger. Notice for example that the subset "many 6-s and 1" that I presented can be replaced by "many x-s and y", and it still holds for x, y giving different remainders mod 7 and even any prime modulus (not just 7) with 10 as the primitive root!

        That leaves us with the task of bruteforcing all suitable subsets, hardwiring them into the code and just choosing the right one for any number :D

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

Thanks for the round! The problems were very clever, even though I didn't solve them during the contest!

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

Timus 1095 is exactly the same with today's A div 1. The only difference is digits used but I suppose that there're many different sets of 4 digits that work in this case — it doesn't mean though that problems will be different as well.

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

:(((

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

Anyone get TLE at DIV1-B, try scanf("%s") instead of cin. what a sad story, my O(N^2) solution with very small constant coefficient TLE.

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

    I had the same issue. I think the time constraints for B are too harsh.

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

      Never mind, just remember to use scanf in future. I have been away from ACM for a couple of years and forget this rule :(

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

        I did scanf but I scan character by character.

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

          NEVER use cin without invoking sync_with_stdio first.

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

Can anyone explain test 4 of Pro.B div 1 (or Pro.D div 2) for me ? In the first row we have 10 ones so we can put ones adjacent so that we have a rectangle with size 1 x 10, or I misunderstood the problem ?

http://mirror.codeforces.com/contest/375/submission/5515862

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

What is the official solution for DIV1-D? When I read other's AC codes, to my surprise the moving-interval solution could pass-_-!!

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

    Its time is N\sqrt(N),so it can pass it.In CN, we call it 'MO DUI'

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

questions were interesting and little bit tricy...Hats off to problem setters!!!

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

Can you post the editorial please.

→ Reply