Lewin's blog

Codeforces Round #385
By Lewin, history, 8 years ago, In English

Hello everyone!

Codeforces round #385 will take place at the unusual usual time of Saturday, 17 December 19:35 MSK.

Thanks to the following people for making this round possible.

As usual, contestants will have 2 hours to solve 5 problems. Hope you will enjoy the problems!

Scoring will be announced closer before the round.

EDIT: It may be helpful to read the Interactive Problem Guide before the round for both divisions.

EDIT 2: The scoring distribution will be unusual:

Div2: 500-1000-1500-2250-2750

Div1: 500-1250-1750-2250-2500

EDIT 3: While you wait for system testing, here is a quick editorial: http://mirror.codeforces.com/blog/entry/49126

EDIT 4: Congratulations to the winners!

Div1:

  1. tourist
  2. Petr
  3. PavelKunyavskiy
  4. YuukaKazami
  5. W4yneb0t

Div2:

  1. Akulen
  2. RVS
  3. tpablo
  4. theodor.moroianu
  5. YouAndI
  • Vote: I like it
  • +477
  • Vote: I do not like it

Comments Comments (249)
| Write comment?
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Interesting problem setters. Now, i'm more eager to participate :)

→ Reply
»
8 years ago, # |
← Rev. 8   Vote: I like it -50 Vote: I do not like it

Deleted...

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

I am sure that this round by Lewin will contain interesting problems(not as previous two rounds).

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

Clashes with COCI #4. It would be awesome to move it to 20:xx MSK (a hour later).

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

** ** *****?

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

hope not to see comments like "is it rated?" or "usual time"

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

Found it funny:"unusual usual time"..:)

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

nice tags

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

Till now I found out that Lewin is fantastic setter. I hope another , balanced problemset !

When I see interactive task I know my rating will go down :D It would be nice to say before contest which task is interactive, for you it is not big deal for me and probably fot many users it is very important.

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

    it's ( div2-C/div1-A ) or ( div2-D/div1-B )

    we will need less than 2 minutes to find out :D

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

Again interactive! every time I see and I think- well! I can solve it :D but then- I say — Sorry me! :(

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

After seeing the tags and round description, I'm wondering, if we will have to interact with cows...

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

Wondering how to hack the interactive problem?

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

    The statement always explains how to.

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

      sometimes source code can't be seen by double click or ctrl+clik after lock my submission, it shows only submission history. why?

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

-

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

thanks Lewin for suggesting to read the interactive problem guide. i would have wasted some time in the contest to learn how to solve interactive problems. i never solved an interactive problem.

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

It seems that codeforces is cleaning up its inventory of problems before Christmas...

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

Today Petr is participating :) ,any guesses in which language(Java/C++/both) he will code in todays contest ?

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

Hope the interactive problem will be interesting.:)

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

tourist vs jqdai0815 vs Petr

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

Four contests in a row) Four contests in 3 days) Real happiness...

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

Good luck! I hope more Experts will be Candidate Master!

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

Is Codeforces trying to implement "Boxing Day" algorithm from the England Premier League? Xp 4 Codeforces round in 3 days. That's something worth living for...

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

I have registered for the div-2 contest but I am not able to see the problems. What should I do.

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

    Contest has not started yet! its about 1 hour 44 minutes to go.All the best!!

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

Hope to provide a grader for the interactive problem :/

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

ICPC REGIONALS ON 22ND, UNIVERSITY PRACTICALS ON 22nd Onwards.Ladies and Gentlemen . Codeforces will always be there, when you need to get high.!Thank you codeforces for the contest series this week.

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

Bad timing for manchester united fan.

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

‌

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

Considering the amount of people who are trying to find out how interactive problems works and sending submissions and how hard it works right now on problem "Guess The Number" do you think it will be ok during the contest?

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

Deep♂Dark♂Fantasy (jqdai0815, jcvb, YuukaKazami) in this round they will decide who will be the captain

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

I hate registering using the lower bottom, hope in this round I can reach Div1 and use the upper one

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

    I guess I'll cheer you on since I like the problems you write :D

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

Hi I new to this platform. Today I will be solved by second contest.

I was wondering why the newer comments go to the bottom rather than addition of comments to the top.

Thank You . Jai Babe di.

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

Good luck everyone! Lewin always writes interesting problems.

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

I hope there will be lots of math questions!

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

Explain B problem in Div2

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

DIV2 B problem statement :(

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

what is the explanation DIV 2 B means?

How can by one movement to right ..... XX... ..... ..... .....

be formed ??

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

    they said two identical copies. I think that's your ans. although I couldn't solve the problem!

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

Div2 Problem B ..So unclear problem statement. It does not even make sense to me :(

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

    Damn right!

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

      I am done with this contest. I am either really stupid or other people who are solving this fast are really geniuses.

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

I just love Ruski English.

GGWP ;)

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

In Problem C Div2 "There is at most one edge connecting any two nodes " and the graph is undirected :/ How is that possible if graph is undirected?

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

    I think it means that there is at most one undirected edge connecting two nodes i.e no parallel edges.

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

In DIV 2 B , is it 'x' or 'X' ?

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

in problem B DIV 2 why this test outputs no? 3 3

.XX

XX.

XX.

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

    I will get my eye sight tested I cannot understand what was meant by their problem statement.
    But interesting problems though. ;)
    Especially D.

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

    I guess we cannot move the individual "X"s. I first submitted the solution based on checking whether "X"s form a rectangle or not. Then thought we can move individual "X"s so checked if there exists a,b such that # of "X"s = a*b. If a<=n and b<=m, said YES else said NO. Then decided to hack solutions and then realised after unsuccessful hacking attempt that we are wrong. We have lost this round brother!

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

      But then how

      5 5

      .....

      ..X..

      .....

      .....

      .....

      This outputs YES?

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

        Because here the single X is the complete puzzle. I failed in English and not code skills. Sad life. Wish I hadnt submitted it again.

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

    say why yes -> know why no

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

Can I delete my last accepted solution? I only need another one to be verified...

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

    Only last successful submit will go to system testing.

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

the problem statement on B is extremely weird !

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

Hacking, hacking everywhere!

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

Does anyone have a hack case for Div. 2 B?

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

    2 3
    XX.
    .XX
    Answer is NO.

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

      There goes my B solution...
      Could you please explain why its NO?
      I'm not sure if I understood properly but why cant you arrange it like this:- .XXYY. .XXYY.
      (Rearranging the tiles in the puzzles and putting them next to each other. Y are the tiles from identical board)

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

      Why is it no? Can't you slide all pieces to the right on the first piece and then slide all to the left on the second piece so that it looks like:

      .XXXX. .XXXX.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    2 3
.XX
XX.
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Why is the answer NO? Cannot we make it as

      .XX

      .XX

      and the other one as

      XX.

      XX.

      and combine two pieces

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

        It mustn't intersect and you can't change the figure.

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

          How do they intersect?

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

            We cannot change individual X positions within one piece. I misunderstood the question :(

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

              "The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."

              Doesn't this mean you can change individual x positions?

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

                You can move only puzzle pieces not the part of the puzzle pieces. I think it sounds confusing, but russian version is ok.

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

                  Yeah my bad. I should've asked for a clarification but the other way of understanding it didn't even cross my mind in contest lol.

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

        .XX XX.

        XX and XX form a single piece(4 connected).

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

    The puzzle piece has to be one of the following types:
    1. Rectangle
    2. Horizontal segment
    3. Vertical segment

    If the figure formed by 'X' symbols does not belong to one of these 3 types — the answer is NO. Otherwise, the answer is YES.

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

Petr may reclaim his second rank today.

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

How to solve Div2D and Div2E?

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

    Div2D: example: n=8 ask1 : 1 3 5 7 ask2 : 2 4 6 8 ask3 : 1 2 5 6 ask4 : 3 4 7 8 ask5 : 1 2 3 4 ask6 : 5 6 7 8 then answer for the 1st row is min(answer2, answer4, answer6) answer for the 2nd row is min(answer1, answer4, answer6) answer for the 3rd row is min(answer2, answer3, answer6) etc The idea is to consider the binary form of the number. Ask 1 and 2 is for the least significant bit, 3 and 4 is for the second and so on.

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

How to solve the problem about the table game?

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

If I pass system testing this will be my best contest ever...fingers crossed wish me good luck.

btw what was the hack for DIV 2B ???

:)

UPD: It passed.

:) UPD2:finally blue...here I come Div 1...

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

    I don't know if it was the hack case but my first submission passed pretests and failed for this case:

    3 3 .X. XXX XX.

    Answer is yes. My first submission was awfully written though (so was my second lol) so maybe it was just me that was wrong on this.

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

    4 4 .... XXX. ..X. .... I did like 4 hacks :)

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

    I hacked a solution using this test case
    4 4
    ....
    .X.X
    .X.X
    .XXX
    The answer should be NO

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

Statement for DIV2 B could have been better.

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

How to solve Div 1 B / Div 2 D?

I kept dividing intervals in n/2 and asking for 2 questions each. For n = 1000, it asked 21 questions somehow :\

Edit: it seems the approach was correct as in editorial. However the last question was redundant and trying to find values on the main diagnol only

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

    Please explain your solution.

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

      Suppose you want answer on a table NxN. Then lets query n/2 numbers twice, the first query questions indices 0, 1...n / 2 - 1, and the second query questions indices n / 2...n - 1. Graphically, this means you know all information for the bottomleft and topright of the current table(verify this with a picture). Now recurse on the topleft and botright, notice that they still have the diagonal with 0's.

      I think this is what he meant.

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

        I don't see why this is right. I thought the same thing. Obviously, binary division was involved, given the constraints, but I couldn't prove it's correctness.

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

          Yes exactly, this was what i was doing. For the topleft and bottomright, part you can divide them into 2 new sub matrix and solve for them too. However direct implementation of this will lead to no of steps as f(x) = 2 + 2*f(x/2). However each of the queries on the leftside and rightside are disjoint and one could merge it into a single query too. That would make f(x) = 2 + f(x/2)

          As for why its right, it is effectively searching all the matrix values

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

            Your implementation sounds exactly like what I tried as well, unfortunately it seems I had a flaw in implementation.

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

            I finally understand :) So, its 2*log(n) .

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

      for each bit i, do 2 query, one for all the index whose ith bit is 0, one for all the index whose ith bit is 1.

      now for row k, we only check the reply which desn't contain M[k][k], that is, those query that checks ith bit different from k's ith bit.

      UPDATE: M[i][i]->M[k][k]

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

    My approach was, first I split all N numbers in two queries by taking groups of 1:

    1 3 5 7 9... and 2 4 6 8 10...

    then I take groups of 2:

    1 2 5 6 9 10... and 3 4 7 8 11 12...

    then take groups of 4:

    1 2 3 4 9 10 11 12... and 5 6 7 8 13 14 15 16...

    and so on.

    With this queries you can test every element in the matrix, and get the minimums.

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

Problem B pretest cases were extremely weak, I couldn't believe some of the passed solutions that I hacked. rankings in Div.2 are more influenced by number of guys with bad solution in your room than time penalty. I think pretests should be stronger, so hacking would be more challenging.

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

    I agree, one of the people I hacked just checked whether there exists a rectangle that has the area equal to the number of X's. No idea how that passed pretests.

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

      I did the same, but I also checked that the number of X inside the rectangle is same as the area of rectangle.

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

    Agree, I hacked 8 submits with easy hacks like

    3 3
...
XXX
X..
    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My first ever hack!

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

Pretests passed in Div1-A by reading edges first then capitals — such strong pretests :( — http://mirror.codeforces.com/contest/744/submission/23053839

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

Div 2B question should have had a clear statement.

"The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions." is very confusing. I thought that the pieces could be moved independently of each other and only understood why my answer was wrong in the last 10 minutes.

When the initial statement read "It is guaranteed that the puzzle pieces are one 4-connected piece", I thought that only referred to the input and not that the pieces had to remain connected throughout.

Nice questions in Div 2 otherwise.

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

    Yeah I thought the same. It could've been a really nice problem if it wasn't for the unclear statement.

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

I hacked 3 C solutions where their logic was as follows:
ans=n-k+1;
ans=(ans*(ans-1))/2;
ans=ans-m;
If any of you did this, it is wrong.
Counter test case:
6 2 2
1 3
1 2
3 4
Correct answer is 5.

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

    LOL, this solution is really retarded. The pretests are really weak if it worked.

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

Div2 B is the worst problem I have ever seen in CF

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

    I'm sorry you feel that way :( I tried to balance a short statement versus a clear statement. It seemed it was too short on details.

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

      Thanks for your effort though! It was a good problem I think just very unclear (at least for me).

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

      It's alright, you tried your best. Other problems were very good. Just that this problems statement should've been a bit more clear :)

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

      Other problems were great...thank you very much for your effort..

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

      I was sad too.

      But then I had a bhangra session to enjoy life.

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

DIV2 E test3?

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

That moment when you discover your bug 30 seconds after the contest ends T_T.

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

can someone figure out why my code is giving Idleness limit exceeded on pretest 2 even though I am flushing many many times?

(bug is probably in n<3 part since pretest 2 has n=2)

http://mirror.codeforces.com/contest/744/submission/23071215

I have tried finding the error for the past hour and have used 8 incorrect submissions on this problem :|

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

    disclaimer: i am CPPer

    shouldn't it be like this? (corrected n < 3 part)

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

I first submitted a correct submission on div2B and then got confused, changed the code so that it outputs wrong on some cases, and submitted it! :(

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

    Similar thing happened to me, but I noticed in time and changed it back. Still lost 10 minutes :C

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

I found 2 submissions with the same implemention http://mirror.codeforces.com/contest/745/submission/23067444 http://mirror.codeforces.com/contest/745/submission/23067030

I just read the first one and i didt understand why he used big integer with this problem, but i think the cheating detector will find it soon :)) (hope so!!)

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

    getting 3rd place with a stolen code, seems legit

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

I have taken almost 20 minutes to understand the problem B in div2 :(

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

    Same here, the funny is I submit a solution without understanding the problem and got pretest passed !!

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

I should practice more hard

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

So what's the right solution for B? Check whether it's a rectangle? Or what? Even C is easier than this.

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

    Yeah, I can't say with confidence that I know, even though I passed pretests... I just made sure the input was a rectangle, since you can always combine two rects to make another rect.

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

      Then why there seems to be such a confusion about this problem? This was the most obvious thing to implement.

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

        Yeah, I guess a lot of people have confusion about what a 'piece' is. Many believe you can shift individual 'X' characters in any fashion you like, where the problem statement says that 'X' characters come together to form one connected piece which must be shifted as a whole. Many people don't quite understand the intent of the question, so hopefully we are not one of those people.

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

      But didnt they say that you could move pieces in any direction?
      So technically even if the input is not a rectangle, it may form one on rearrangement.Did I miss understand?

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

        By puzzle pieces, they mean the big given grid, and not individual X's

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

          Oh my god....
          So basically you have to paste one grid on top of another and the resulting 'X's should be a rectangle(with no overlaps)?

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

            I hope so, because that's what I did. :)

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

            You comment should be part of the problem statement ;)

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

    Yes, it has to be a rectangle. There's no other way.

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

is it even necessary to have govt nodes Number in Div 2 C ? if i iterate over all nodes to do the dfs anyway ?

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

    Of course they are needed, you can't put edges between vertices that are connected to some capitals. The example contains such a test.

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

Both problem statement & pretest cases of problem B were really very weak.

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

That weird moment when you get pretest passed without understanding the problem at all and pray to get hacked before it's to late :P

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

    And when it get hacked...you start to read and understand the question again :(

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

    That weirder moment if you get accepted instead without understanding the problem

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

This contest was nice but the pretest for Div 2 B sucked...like they weren't just bad they were the worst...my friend solved an entirly different problem and got pretest passed...

but other than that it was great.

:)

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

in the problem B DIV2 it says in the statement " The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."

and now you say i can't move peaces how is that ?

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

    Well...you actually can. But you'll get a rectangle only when the pieces are initially rectangles. I don't understand the confusion about this problem.

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

      .XX

      XX.

      this is not a rectangle but if i moved each peace in the first row one step it will be rectangle

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

        I don't understand you, how can you get a rectangle from to pieces that look like this?

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

        XX.

        XX.

        this one peace if i have two peaces it will be like this XXXX.. XXXX..

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

      The confusion is whether they meant the board as a whole is a 'piece' or do they mean the 'X's as the pieces?
      If we consider the latter, then the input does not have to be a rectangle originally.

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

Div2/B is just horrible, nice Div2/C BTW I got pretest passed in the last minute.

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

Why Codeforces nowdays testing user's ability to understand problem statement???

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

    Why not? ;)

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

      Because it's not an English language testing platform -_-

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

        Why did this guy _index solved the problem A in 2 minutes and problem B in 6 minutes?

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

          He said he read the statements in Russian where they were clearer (according to him).

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

            Ok, TheMaverick is definitely not russian (and has a badass toxedo) :)
            He solved B in 9 minutes.

            theodor.moroianu is from Romania and he solved B in 4 minutes!

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

              What are you trying to prove here saying "He" solved B in "T" minutes?

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

                Do I really need to clarify?

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

                  Did you see how many people failed in the system test in problem B?I don't think there is any corner case in this problem.

                  So do you want us to believe that they all got the statement right and coded wrong?Seriously?

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

                  "you want us to believe that they all got the statement right and coded wrong?"

                  No, I wanted to say that 1240 people understood the problem and coded it correctly. And I wanted to say that for the people with enough experience B wasn't a problem at all. Understanding the problem correctly (however unclear it is) is, I believe, a part of the problem solving skills.

                  If tourist or Petr participated in Div2, they would have solved A and B in no time =)

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

Problem statements were really confusing -_-

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

Problems were fine, statements were trash

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

Lets see how many solutions of B pass system test.
As I understand now, the code I wrote is COMPLETELY wrong.
Yet,it still passed pretests and a hack too...

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

In Div2, Only a few could solve D or E. The gamechanger question was B whose problem statement was horrible. People have submitted considering individual "X"s can be moved. This round should be made unrated for Div2 as B has clearly caused complete turbulence.

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

    I never saw weak pretests being reason for unrated contest.

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

      Weak pretests + confusing statements + D,E were very hard.

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

        The only times I've seen contests be unrated are when the queue is bad. I think there was one contest where the judge solution for Div 2. D was actually wrong and they just removed the problem instead of making it unrated. So today will probably be rated.

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

    Then how come some people understood the statement correctly? Have you ever played jigsaw puzzle? The question clearly stated two puzzle pieces. It should've occurred to you that 'X' != puzzle piece when you saw the first sample case.

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

    When people go undercover to make the contest unrated.
    The contest can not be unrated just because of a problem statement.
    Also many were not able to give time to D because they were stuck in B.

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

I really liked Div1 B!

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

Problem B not passed — nooooooo! So it's actually wrong to output yes when the piece is a rectangle.

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

    Not true, mine passed. Probably a bug in implementation.

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

      Wow, that's even worse. The pretests are so weak.

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

I have a question. I wonder how people can solve Div2 B, though they are confused about it... Is it a gap between me and high ranks?

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

    I'm definitely not a "high rank" but because of weak pretests, it's possible to "solve" the problem without actually understanding it. For parts that were unclear for me, I assumed parts of the problem that were actually incorrect but worked with the sample cases. And with passed pretests, it made me think it was actually correct (when it wasn't at all).

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

Is it rated ? :p

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

    Before the contest : ** ** *****?
    After the contest : ** ** *****? xD

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

The pretests for Problem B DIV2 is very weal i got pretest passed and i don't know even what is the problem is .. and Now i got Wrong answer and i still don't know the problem .? could someone explain what the problem ?

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

    find out if the surface covered with 'X' forms a rectangle

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

      It would've been Problem A with an understandable statement but they made the statement so confusing so that it would have the difficulty of a B problem..

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

      3 3

      X.X XX. .XX

      i understand that we can make rectangle with this by shifting?

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

        You're not allowed to shift 'X' You can only move left, right, up or down the whole matrix (the whole piece)

        You have to get a rectangle by appending two identical pieces. You can get that only if you have a rectangle in the given piece.

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

          oh man thank you very much =D . i see it's easy now

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

welp, this was unexpected

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

Waiting for rating

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

The statement for problem B (division 2) was very poor!

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

whatever....what about ratings???

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

system pending wasnt faster before ? :-"

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

Let's hope rating will be updated in 25 minutes, otherwise there will be few lucky div1 participants who can participate officially in tomorrow's round. ;)

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

When can i up-solve problems? cant submit any solution now! there is no option ! if i click on 'submit code' tab, its shows 'contest is over'!

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

    You have to wait until system testing is over and ratings get updated, then the problems will be available for practice.

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

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

Div.1A, test 15. Are you sure that given graph is stable?

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

    You are reading capitals after the edges, but they are given before them.

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

    Surprising part is that it passed 14 tests..

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

    You should read capitals first, then edges, not vice versa.

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

Goodbye Expert...

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

Where is the new rating?

→ Reply
»
8 years ago, # |
← Rev. 24   Vote: I like it +8 Vote: I do not like it

C approach:

let k be the number of governments

Make k sub-graphs such that each of them contains one government node (k strongly connected components), so vi nodes with government.

Note that there will be, let say p nodes in anarchy (no government) with pe edges between them.

We will attach those nodes to some of the k sub-graphs and generate the maximum number of possible edges. (No node can be attached to two different sub-graphs)

Let g1 be the edges generated by

  • Two nodes with government

Let g2 be the edges generated by

  • Two nodes without government

Let g3 be the edges generated by

  • Nodes with government
  • Nodes without government

We agree g1 has a fixed amount, thus no decision with the anarchy nodes will influence its value.

Then we need to see that g2 ≤ p * (p - 1) / 2 - pe. We can't have more edges between p nodes than the possible pairs of them. Any solution with g2 = p * (p - 1) / 2 - pe has an optimal value of g2. Any solution that set the p vertex in the same group has an optimal value of g2 (1)

Note that adding one anarchy node to a group with government generate vi edges of type g3. (denote vi the original amount of nodes per group).

If j is the sub-graph with more nodes then vi ≤ vj with any sub-graph i

where ci is the amount of anarchy nodes that go to the sub-graph i

As ci * vi ≤ ci * vj

this means adding all anarchy nodes to the group j implies an optimal g3 value, cause equality is obtained. But if we do so then all anarchy nodes will be in the same group, because of (1) g2 is optimal As g2 is optimal, g3 is optimal, and g1 is fixed, adding all vertex to greater group is the optimal solution.

After doing so we count the amount of nodes and edges per group and solution will be

where ei is the amount of edges that already exist per group

Total complexity: O(n)

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

    Tutorial on C — The simple made tough

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

      it's a simple problem and you can figure out the solution intuitively. This is not the solution, but the proof of it.

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

Start the upsolving, please

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

When can we submit for problems??

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

Well, just 1 far from expert :( Look at my graph

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

I think something is wrong here one code with 2 different verdict (hack, accept) 23067626 , 23072618

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

I think there is a problem on codeforces , i can't do anything on the site
look here

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

    I've been having such a problem for a couple of hours, though :/

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

    Me too. I can't see my own submissions, which is quite annoying.

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

When I go to any of the problems a message says "No such problem"

and all my solutions in this contest disappeared

and my graph is updated and the rating still the same ,

does anyone have the same problem ?

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

    it seems like everyone is having this problem, idk why, the rating is still the same but the color doesn't change though.

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

      I just fixed it , you have to change your ip address (by restarting your router or whatever)

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

Anyone know what testcase 15 on Div1A/Div2C contains? I'm failing on it.

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

    Try this case; if you count this edge ?

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

      It seems that your program can solve this case.Then i have no ideal what's wrong with your program.

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

    You need to make all components cliques.

    Say capitals are 1 and 4. 

    n m k
9 8 2
1 4
1 2
1 3
2 3
4 5
4 6
5 6
7 8
7 9

    (1) - 2 (4) - 5 7 - 8
   \ /    \  /   \
    3       6     9

    you have to make an edge 8 - 9 and connect that component to any other, adding 3 * 3 = 9 edges, so total is 10 edges.

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

      Damn, my code already passes your test case :( Still not sure why it's failing 15 because I can't see the whole input.

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

I can't see test cases :(

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

Can someone please help me with Div2 C problem? I made disjoint sets of all the capital cities and the nodes connected to them directly or indirectly. Then I calculated the number of nodes who aren't connected to any of the capitals,I did this by calculating the sum of sizes of various disjoint sets and subtracting it from n. Then for every capital city I added (size*(size-1))/2 to my final answer.Finally I gave the output as this sum-m , the no of edges. My submission is http://mirror.codeforces.com/contest/745/submission/23076645 . Thanks in advance !

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

    Here's my approach. First of all, if you have make disjoint sets in such way, make each of those disjoint sets a complete subgraph (let's say the set contains x nodes, so the number of edges we can add to make it a complete subgraph with x nodes is x*(x-1)/2 — e where e is number of default edges on that sets).

    Then after we make each disjoint sets a complete graph, we search every disjoint sets who doesn't have a capital city (special node) as their member and do the following process : - since we want to add as many edges as possible, find the best disjoint set that have capital city as its member (e.g. the disjoint set who has the maximum number of nodes as its member) - add our variable answer with sum[x]*sum[y] (**_sum[x]_** is how many vertex in disjoint set x)

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

Back to CF after 1.5 years...

Looks like I have not completely forget all about algorithims :)

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

    Now you can probably stop saying you were carried by team members. xD

    They don't let you solve :P

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

Is it just me or rating is not updated yet?

→ Reply