When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

yan.silva's blog

By yan.silva, history, 4 years 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
  • +165
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

We hope you will have fun!

»
4 years 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 ?

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

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

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

      Show when can I register for it ?

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

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

        • »
          »
          »
          »
          »
          4 years 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 ?)

          • »
            »
            »
            »
            »
            »
            4 years 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.

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

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

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

                Sorry but I can't answer this question :/

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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 ?

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

                  Yes, they all are random.

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

                  Okkk. Thanks for replying

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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 :((

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

Will it be rated?

»
4 years 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.

  • »
    »
    4 years 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.

»
4 years 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 :)

  • »
    »
    4 years 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 :(

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

The contest is now available to register!

»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

The participant's solutions will be made available?

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

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

    • »
      »
      »
      4 years 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 years 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 years 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

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

    Please release the solutions and test cases. Leonardo_Paes

»
4 years 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.

  • »
    »
    4 years 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.

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

      I don't get why this is valid?

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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!

      • »
        »
        »
        »
        4 years 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?

    • »
      »
      »
      4 years 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).

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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 :)))

      • »
        »
        »
        »
        4 years 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!

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice contest! Thanks :)

»
4 years 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 :(

  • »
    »
    4 years 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.

»
4 years 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.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the contest :)

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

Thanks for the contest! Will there be an editorial?

  • »
    »
    4 years 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!

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

      can you please allow us to see other users submissions?

»
4 years 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.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

Problem K doesn't work again.

Btw. nice contest! Enjoyed it.

»
4 years 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.

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

Can someone share their solution for problem H?

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

Any editorial? Leonardo_Paes yan.silva

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

I have solved the problem A using DFS , I have an intuition about what to do but i am getting wrong answer in the fourth test case,can someone help me out with that. By the way,i am not even taking the edges with composite weights as inputs,as they really don't matter.This is the link to my code....

UPD..I found my mistake,btw thanks...