yan.silva's blog

By yan.silva, history, 8 days ago, In English,

Hey guys, what's up? How's the quarantine going?

Leonardo_Paes and I are preparing our first contest. It is ICPC-style, but we recommend that it should be done individually. You'll have 5 hours to solve between 10 and 12 problems. It will be held on this Sunday ( 03/29/2020 ), 14:00 UTC-3 in a private group. You can join this group using this link: https://codeforces.com/group/t62S9paTEF.

We really hope you enjoy the contest!

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

»
8 days ago, # |
  Vote: I like it +61 Vote: I do not like it

We hope you will have fun!

»
8 days ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Hope your contest will be success <3

I see no contest in the link ?

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

    We'll add the contest to the group only on Sunday

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

      Show when can I register for it ?

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

        You can register for the contest a few hours before it starts

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

          How hard is it, is it estimate about Div2 A-B-C ? (600 ~ 1500 *rate ?)

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

            There are easy, medium and hard problems. The easy ones are around Div-2 B difficulty and the hard ones are in Div-1 range.

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

              How many Div2-B and Div1 estimated-difficult-problems are there ?

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

                Sorry but I can't answer this question :/

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

                  Ok, how about the topic use for the contest, are they all randomly ?

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

                  Yes, they all are random.

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

                  Okkk. Thanks for replying

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                    Vote: I like it -27 Vote: I do not like it

                  Asking for too many things then forgot to take part in the contest. Sorry problem-setter :((

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will it be rated?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great, if this contest will be in other date, because at this time a lot of cf users(and ICPC teams) will be in opencup.ru contest.

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

    We think that changing the date of this contest it's a bad idea because we had announced it to many people already. But, if people like this contest, we'll make more contest and more people will be able to participate.

»
8 days ago, # |
  Vote: I like it +36 Vote: I do not like it

Why not using those problems in Codeforces Round?

I know it's kinda difficult to prepare official rounds but official rounds are also well organized :)

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

    I don't think we're on an enough level to help create an official round :(

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for your efforts! Hope it's gonna be fun!

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

The contest is now available to register!

»
5 days ago, # |
  Vote: I like it +46 Vote: I do not like it

The participant's solutions will be made available?

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

    Can anyone explain how to solve C. Trees and Decrees?

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

      Binary search on the answer, sort the queries by $$$r$$$ and for each query go from $$$l$$$ to $$$r$$$ taking the maximum you can until that query become 0 or it's impossible.

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

        thank you for responding Devil, but can you elaborate it a bit more after sorting the queries by r.

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

          Suppose that you want to know for a fixed $$$k$$$ if the answer is $$$\le$$$ $$$k$$$

          Let's see it as an array $$$A$$$ of $$$n$$$ elements with value $$$k$$$

          Then for each query $$$l, r, x$$$ you need to subtract a total of $$$x$$$ between $$$[l, r]$$$, if you can do that and $$$A_i \ge 0$$$ for all $$$i$$$ in the end then the answer is $$$\le k$$$

          The best way of do that is greedy sorting the queries by $$$r$$$ and for each one do:

          for i in [l, r]:
              z = min(x, A[i])
              A[i] -= z
              x -= z
          

          if all the queries have $$$x = 0$$$ in the end the answer is $$$\le k$$$

          For speed up the solution just use the compression path idea of disjoint set for find the next $$$A_i > 0$$$ instead of iterate from $$$l$$$ to $$$r$$$, here are the solution

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

    Please release the solutions and test cases. Leonardo_Paes

»
5 days ago, # |
  Vote: I like it +31 Vote: I do not like it

What was the expected solution for D? Felt something like connected components, but no luck.

  • »
    »
    5 days ago, # ^ |
    Rev. 3   Vote: I like it +40 Vote: I do not like it

    You need to just find the smallest rectangle such that all points lie in it or on its borders, then just remove the points on the borders of this rectangle and start again until no points are left. Here is my code.

    • »
      »
      »
      5 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I don't get why this is valid?

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

      Your solution seems to be wrong for this case, unless you're doing something I'm not understanding.

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

        Yep it seems like my solution is wrong for this case, it looks like tests are weak for this problem!

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

        what is the expected solution to this problem? Also could you allow us to see other people submissions?

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

      I didn't submit the solution during the contest, and I think that I've misread the statement in some way. Tried re-reading it, but didn't help.

      So, on the following test:

      test
      visualization

      your code outputs 3, but the answer, in my understanding, is 2 (you can deal with the top left square and the bottom right square separately).

      Could someone please point out what piece of the statement I understood incorrectly? :) (since I'm pretty sure that it's my problem — there are x16 accepted solutions).

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

        It's not just you, I talked to some of the people who got AC in this problem and they seem to be confused by this test too :P

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

          It's quite funny that we posted exactly same countertests to the abovementioned solution :)))

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

        I think they forgot about this test, I totally agree with both of you!

»
5 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice contest! Thanks :)

»
5 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem K: The arrays x and y will be destroyed after this query; the new array receives the index of the smallest positive integer that has not been used yet. The meaning of destroyed in this case is very confusing, I couldn't send it in time because I understood that destroying restores the id :(

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

    Oh, sorry :/ The array is destroyed but the index was already used :/ We are working hard to rejudge the solutions.

»
5 days ago, # |
  Vote: I like it +25 Vote: I do not like it

How to solve H? I came up with the obvious O(n^2*k) dp solution but couldn't figure out a way to optimize it.

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

    Divide and Conquer DP Optimization, check this problem and its editorial for a detailed explanation

  • »
    »
    5 days ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    It can be done with D&C, as RedNextCentury sad, but it also can be done with segment trees, stacks + multiset, or normal DP!

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

      Can you please explain those solutions? Also, will you be publishing an editorial?

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

        We are thinking about it, but we are almost sure we will!

»
5 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the contest :)

»
5 days ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Thanks for the contest! Will there be an editorial?

  • »
    »
    5 days ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    We are thinking about it, but we are almost sure we will post it!

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

      can you please allow us to see other users submissions?

»
5 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Really my fault for not asking clarification, but the phrasing led me to believe the first query in K meant adding $$$v$$$ to the $$$y$$$-th element of the $$$x$$$-th array, rather than setting the $$$y$$$-th element of the $$$x$$$-th array to equal $$$v$$$ :(

Anyways, thanks for the contest! The problems were pretty nice.

»
5 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice contest! Can you please make all the testcases visible to us?

»
5 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem K doesn't work again.

Btw. nice contest! Enjoyed it.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me in problem B,i tried to solve it using weighted bipartite matching but i got TLE in test case 85.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their solution for problem H?

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

Any editorial? Leonardo_Paes yan.silva