Блог пользователя Lewin

Автор Lewin, история, 7 лет назад, По-английски

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://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
  • Проголосовать: нравится
  • +477
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 8   Проголосовать: нравится -50 Проголосовать: не нравится

Deleted...

»
7 лет назад, # |
  Проголосовать: нравится -62 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +434 Проголосовать: не нравится

** ** *****?

»
7 лет назад, # |
  Проголосовать: нравится -124 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

nice tags

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Wondering how to hack the interactive problem?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -39 Проголосовать: не нравится

-

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -49 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Hope the interactive problem will be interesting.:)

»
7 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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...

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope to provide a grader for the interactive problem :/

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Bad timing for manchester united fan.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Good luck everyone! Lewin always writes interesting problems.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I hope there will be lots of math questions!

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Explain B problem in Div2

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

DIV2 B problem statement :(

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

what is the explanation DIV 2 B means?

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

be formed ??

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just love Ruski English.

GGWP ;)

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

.XX

XX.

XX.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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!

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      But then how

      5 5

      .....

      ..X..

      .....

      .....

      .....

      This outputs YES?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    say why yes -> know why no

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

the problem statement on B is extremely weird !

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hacking, hacking everywhere!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    2 3
    XX.
    .XX
    Answer is NO.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    2 3
    .XX
    XX.
    
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Why is the answer NO? Cannot we make it as

      .XX

      .XX

      and the other one as

      XX.

      XX.

      and combine two pieces

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          How do they intersect?

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              "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?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        .XX XX.

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Petr may reclaim his second rank today.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Div2D and Div2E?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the problem about the table game?

»
7 лет назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

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...

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Statement for DIV2 B could have been better.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please explain your solution.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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]

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Agree, I hacked 8 submits with easy hacks like

    3 3
    ...
    XXX
    X..
    
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

My first ever hack!

»
7 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was sad too.

      But then I had a bhangra session to enjoy life.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DIV2 E test3?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://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 :|

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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! :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I found 2 submissions with the same implemention http://codeforces.com/contest/745/submission/23067444 http://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!!)

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I should practice more hard

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

:)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      .XX

      XX.

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -29 Проголосовать: не нравится

    Why not? ;)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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!

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится +6 Проголосовать: не нравится

                Do I really need to clarify?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится +4 Проголосовать: не нравится

                  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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 лет назад, # ^ |
                    Проголосовать: нравится +22 Проголосовать: не нравится

                  "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 =)

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

Problem statements were really confusing -_-

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Problems were fine, statements were trash

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

»
7 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    I never saw weak pretests being reason for unrated contest.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

I really liked Div1 B!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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).

»
7 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Is it rated ? :p

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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..

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      3 3

      X.X XX. .XX

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

»
7 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

 welp, this was unexpected

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Waiting for rating

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

whatever....what about ratings???

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

system pending wasnt faster before ? :-"

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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. ;)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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'!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +156 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Goodbye Expert...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where is the new rating?

»
7 лет назад, # |
Rev. 24   Проголосовать: нравится +8 Проголосовать: не нравится

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)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Tutorial on C — The simple made tough

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Start the upsolving, please

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

When can we submit for problems??

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try this case; if you count this edge ?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't see test cases :(

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.com/contest/745/submission/23076645 . Thanks in advance !

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
7 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

Back to CF after 1.5 years...

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    They don't let you solve :P

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Очень интересно тут считается рейтинг. После первого участия в олимпиаде я стала специалистом, хотя решила всео одну задачу. Потом было пару раундов, на которых я не успела решить ни одной задачи, рейтинг не снизился. Было пару раундов, когда я отправляла неправильное решение, так и не решив до конца — рейтинг упал. Вчера мне все таки удалось решить одну задачу, но рейтинг еще понизили. То есть, лучше бы вообще ни одной не решила, что б хоть не понизили? Обидно. Зачем так новеньких обламывать?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Рейтинг меняется в зависимости от твоего места. Потом было пару раундов, на которых я не успела решить ни одной задачи, рейтинг не снизился. Если ты ничего не отправляешь, система считает, что ты не участвовала в контесте (что логично), и твой рейтинг не меняется, потому что в принципе не на что опереться при его пересчете — места-то нет. Было пару раундов, когда я отправляла неправильное решение, так и не решив до конца — рейтинг упал. Как только ты делаешь отправку, твое решение проверяется, выдается какой-то вердикт, и тебе присуждается место в контесте в зависимости от твоих баллов. Раз ты не решила, то место у тебя было судя по всему низкое, и у тебя забрали рейтинг.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it just me or rating is not updated yet?