yan.silva's blog

By yan.silva, history, 6 months 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

»
6 months ago, # |
  Vote: I like it +61 Vote: I do not like it

We hope you will have fun!

»
6 months 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 ?

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

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

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

      Show when can I register for it ?

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

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

        • »
          »
          »
          »
          »
          6 months 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 ?)

          • »
            »
            »
            »
            »
            »
            6 months 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.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

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

                Sorry but I can't answer this question :/

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months 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 ?

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

                  Yes, they all are random.

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

                  Okkk. Thanks for replying

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months 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 :((

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will it be rated?

»
6 months 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.

  • »
    »
    6 months 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.

»
6 months 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 :)

  • »
    »
    6 months 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 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

The contest is now available to register!

»
6 months ago, # |
  Vote: I like it +46 Vote: I do not like it

The participant's solutions will be made available?

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

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

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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.

        • »
          »
          »
          »
          »
          6 months 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

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

    Please release the solutions and test cases. Leonardo_Paes

»
6 months 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.

  • »
    »
    6 months 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.

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

      I don't get why this is valid?

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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!

      • »
        »
        »
        »
        6 months 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?

    • »
      »
      »
      6 months 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).

      • »
        »
        »
        »
        6 months 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

        • »
          »
          »
          »
          »
          6 months 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 :)))

      • »
        »
        »
        »
        6 months 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!

»
6 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice contest! Thanks :)

»
6 months 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 :(

  • »
    »
    6 months 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.

»
6 months 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.

  • »
    »
    6 months 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

  • »
    »
    6 months 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!

    • »
      »
      »
      6 months 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?

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

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

»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the contest :)

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

Thanks for the contest! Will there be an editorial?

  • »
    »
    6 months 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!

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

      can you please allow us to see other users submissions?

»
6 months 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.

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

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

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem K doesn't work again.

Btw. nice contest! Enjoyed it.

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their solution for problem H?

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

Any editorial? Leonardo_Paes yan.silva

»
6 months 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...