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

Автор kpw29, 4 года назад, По-английски

Hello, Codeforces!

On behalf of Meet IT, I'm glad to invite you to (Codeforces Round #683 by Meet IT (Div1, Div2) which will take place this Sunday (15th November).

The round lasts 2.5 hours and is rated for both divisions.

What is Meet IT?

We are a family of enthusiastic and motivated young people passionate about programming and mathematics. We build a community where people learn together, motivate and help each other.

Please expand the spoiler to find out more about us.

Meet IT family members worked hard over the last few months to provide you with our favourite challenges we came up with. We hope that you will enjoy them as much as we did :)

We are enthusiasts of short and clear problem statements, strong pretests, and happy participants!

Every effort is valuable for us, and therefore I'd like to thank everyone who has contributed to the creation of this round:

  • Co-founders of Meet IT: Mateusz and Paweł for guiding Meet IT projects and making things happen.
  • Maciej, Piotr and Michał. Without their commitment in early years of Meet IT the Family would not exist.
  • Round coordinator antontrygubO_o for endless discussions about the problemset.
  • pawelek1 for coming up with problem ideas.
  • tnowak for massive support in the work on harder tasks.
  • staniewzki and jjaworska for developing the most challenging problem of the round.
  • pasawicki for interest in tennis which was an inspiration to one of the problems, and for preparing another problem.
  • lcaonmst for preparing a problem quickly and diligently.
  • Mohamed.Sobhy for coming up with a nice easy problem and preparing it.
  • Amtek for enduring my repetitive reminders to prepare a problem.
  • flaviu2001 for his excitement about the round after testing and help to improve the shortcomings.
  • _h_ for help in providing a high-quality editorial to one of the problems.
  • dorijanlendvaj for firmly complaining about one edgy problem that pushed us towards substituting it with a better one.
  • kobor for providing beautiful pictures for the removed problem. :(
  • Devil for coming up with the substitution problem :), without you we would be still finalizing the problemset.
  • arsijo for paying special attention to statements clarity during testing.
  • zdolna_kaczka for winning the virtual contest among testers.
  • Anadi for inventing an alternative solution to one of the hard problems as well as his kind comments and suggestions.
  • Farhan132 for his ideas on how to improve the problemset in the second division.
  • Linkus and a.piasta for showing the need to reduce the round difficulty a bit.
  • The Army of Testers: ffao, RetiredPlayer, Retired_cherry, Whistleroosh, ijontichy, coderz189, AwesomeHunter, H4ckOm, TeaTime, hg333.
  • MikeMirzayanov for the amazing platforms Codeforces and Polygon.
  • all the people who strive for Meet IT Family to grow.
  • Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round.

UPD

I'm also thankful for Swistakk for testing the round thoroughly. Sorry for forgetting! I wrote the announcement sometime before that. I totally don't get why he got downvoted, please give him as much contribution as he deserves!

UPD 2

There will be $$$6$$$ problems in each division, with $$$4$$$ problems shared. One of those will have a subtask!

We strongly recommend to read all the problems. You have been warned :)

Scoring:

Div 2: 500 — 1000 — 1250 — 2000 — 2250 — (2500 + 750)

Div 1: 500 — 1000 — 1250 — (1750+750) — 3000 — 3000

UPD 3

We would like to host a stream shortly after the contest. We haven't yet figured out the details, you can expect some backstage stories about the round, Meet IT, and casual discussion. Stay tuned!

UPD 4

We've added the link to the stream which shows on the Streams pannel on the right. You're more than welcome to join our stream

UPD 5

Editorial is ready!

UPD 6

We hope you've all enjoyed the round despite some minor issues. Congratulations to the winners!

Division 1:

  1. Um_nik (the only person to solve all problems!)

  2. ecnerwala

  3. Benq

  4. ainta

  5. ksun48

Division 2:

  1. shb

  2. jz_597

  3. 1700012703

  4. XueYJ

  5. zybkl

  • Проголосовать: нравится
  • +781
  • Проголосовать: не нравится

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

I was aiming to reach red before this round so that this announcement looks more serious, but my attempts ended up with almost falling to purple and I'm very happy it's only almost.

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

It might be helpful if you write the date and time rather than "this Shnday", since it appears to people that this blog was posted 3 weeks ago. I almost thought this was for an old round, but I realised otherwise once I saw the lack of comments.

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

    This is confusing. The post was created 3 weeks ago indeed. But it was published 20 minutes ago (Wednesday evening).

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

      I understand, but at the top of the page, it still shows 3 weeks ago as the date, so it'll probably be helpful if the wording is changed from "this Sunday" to "Sunday the 15th of November" or something similar to avoid any confusion :)

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

Behind the scenes: they were talking about this round for almost a year, so if it won't be good then I don't know how much time you'd have to spend to make a good round.

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

my dear wife Marta

weird flex but ok

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

Don’t you think that saying who won virtual contest, who developed which problem or who came up with which problem is a small hint for everybody who know these people?

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

    In some way maybe, but not much bigger than just revealing writers of upcoming round which is done on daily basis.

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

    I don't think that any of the descriptions gives any advantage at all. In fact, many of the problems were invented by a person other than the one who developed the problem package.

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

As an unmentioned tester let the community repay me this lack of gratefulness with contribution from them. Upvotes — come forth!

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

As a first time tester I'd like to say unlike kpw29 I have solved the tasks twice now. Also a great round is waiting for you all :D

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

Nice to see the contributions of each tester and setter being elaborated :)

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

Is it rated?

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

Hooray! 2 contests in three days!

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

Brace yourselves for another antontrygubO_o show:)

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

Do we really need these LONG LONG comments to all contributers and testers??

As some comments provide little hints, in some sense we're forced to read it and it's an annoying work for me. (like "inventing an alternative solution to one of the hard problems" is some kind of hint)

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

    I'm sorry if you don't like those :(

    "(like "inventing an alternative solution to one of the hard problems" is some kind of hint)" I don't think so. Most of the problems have alternative solutions, don't they?

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

      "most of the problem have alternative solutions" — agree. though, the information which this comment provides is not only "the existence of the alternative solution" but "the existence of alternative solution which is easy to come up with and worth to mention in editorial".

      Do you still think this is no hint?

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

        Yeah. Your conclusion might be wrong. Let's come back to this after the round!

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

    You can just choose not to read that.

    I'm sure you won't be at a great disadvantage, and you also won't waste your time:)

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

      maybe you're right, but I'm not so brave or strong enough to forgo may-be hints in front of me :(

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

please, don't get unrated again...

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

Congratulations on your marriage! So happy for both of you <3

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

Thumbs up20201114-102007

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

This is the most wholesome round announcement I have ever seen. Well done, see you on the scoreboard!

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

Now this my friend is what you call an announcement

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

This guys H4ckOm was plagiarised a few rounds before in Codeforces Raif Div1+Div2 and still he testing rounds? Seems risky.

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

I hate problems

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

[Deleted]

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

be aware they will have odd, even number type questions, as the rounds are going as 13,15,17.19,21(Div2), Hoping that this series will continue after 21.

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

"Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round." .this line touched my heart.

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

"We strongly recommend to read all the problems. You have been warned :)"
I wonder how to interpret these words :/.

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

    It seems unrealistic but 2500 + 750 looks interesting in F1-F2(Div. 2) problems. Maybe F2 should be the easier variety of F1?)

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

      No, you can picture this as: F1 is already quite hard, and you get bonus points for something on top of that. In other words, F1 is a substantial part of the whole problem.

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

      Usually (something+something) are easy version and hard versions. Hard versions may be stricter in constraints or have additional variables.

      In this case maybe F1 is already hard enough and F2 is just a small optimization of something.

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

excited to participate in this round...

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

One of the best contest i ever gave, enjoyed a lot! Thanks for the interesting tasks!

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

That feeling of the rise in difficulty from D2C/D1A to D2D/D1B is a killer. The round had sexy af problems. I wasn't able to solve D and above but I really liked thinking about them and how I was thinking about them. Thank you for the amazing round setters and testers <3

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

    Agree that round was amazing :)

    But on the other hand, because D2C/D1A was more ad-hoc and D2D/D1B is a slight modification of classic LCS dynamic programming, I found D2D easier.

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

What is pretest 6 for div-2 D?

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

    Pretest 6 was cancer man

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

    One of my submissions failed on pretest 6, because it allowed negative dp values (in the LCS-like dp such that $$$dp[i][j]$$$ is the maximum possible similarity score of substrings C, D such that C ends at i and D ends at j).

    Given that you can always choose empty substrings, the dp entries obviously have to be non-negative.

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

Is there any particular reason for putting 256 MB memory only in div1D?

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

    No, it's the default one. We haven't had any solutions which was close to that :/

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

How to Solve Div-1 D??

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

How to solve div-2 E ?

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

    When you insert any good sequence into a trie, for all vertices one of the sons will have <= 1 vertices in subtree. You can calculate cost to convert trie into a good one with dp.

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

How to solve Div2-D ??

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

Nice problems. Was there some reason for choosing 4*LCS — |C| — |D| instead of just LCS — |C| — |D| in D?

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

    because then the answer would always be 0

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

    Yes, cause in other case answer is 0

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

      Oh yes just realised that. So any factor would have worked as long as answer is non trivial. Thanks.

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

    It can be shown that the optimal solution for LCS — |C| — |D| is just two empty substrings :)

    I'm guessing 4 was chosen to facilitate generation of strong testcases (too large a constant would probably allow scams based on just finding the LCS of the strings, too small a constant and you may not be able to easily generate non-trivial large testcases)

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

how to solve div 1 c ? i understand that graph is a forest but what is the answer

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

how to solve div2 B?

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

    notice that an even number of negative number can change to all positive

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

    If there is a zero in the grid, you can always make all elements positive.

    If the number of negative elements is even, you can always make everything positive.

    If the number of negative elements is odd, one of the elements will always be negative in the end after all operations. Try making this negative value as the one with smallest absolute value among all numbers.

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

what's wrong in this implementation for B? https://codeforces.net/contest/1447/submission/98492176

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

    notice you can also change a negative number to a positive one

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

      I know it, so what's the problem in code? If there's no zero and odd count of negative numbers I'm looking for smallest in absolute negative number to subtract from sum

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

        You have to subtract it twice. Because sum is already sum — min number.

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

        in that case you have subtract twice of that number cause you already added it in your sum once

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

          I'm subtracting it twice in line 41 sum += 2 * list.get(0);

          list at this time is sorted in descending order so list.get(0) is smallest by absolute negative number

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

            you are not getting it right you have to take minimum in not just negative but positive also so that its absolute has minimum value

            like in 1 -2 -4 2 5 the minimum is 1 but in your case its -2

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

First time got TLE on using long long in place of int ( in DIV2D or DIV1B ).

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

d1 F was same as this problem with solution described in this blog.

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

    Fortunately it was on HackerEarth so probably nobody except you knew xD

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

      And I still couldn't do it anyway because I didn't open it during the contest thinking that one was probably different. ;_;

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

    I hate this "you need to log in" shit. I didn't open any HackerEarth problem in a long time because of that.

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

Any help on Div2E/Div1C, I think we need to group those numbers with same most significant bit, since they will choose to connect other members in that group, like [0 1 5 2 6] -> [0 0 2 1 2]. Then we sort the number of members for groups, like [0 0 2 1 2] -> [1 2 2]. Then we remove the smaller groups (except last one) to only one member, so [1 2 2] -> [1 1 2]. So answer is 1. But I get wrong answer, anyone can help?

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

    After you group the number with the same most significant bit, they still don't make a connected component. For example, add to all the numbers in your example 2**31. It will not change the graph, and they will still not form a connected component.

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

Can anyone tell me why my memoized code failed for Div 2-D?

It should be only twice as slow, as the recursive version needed another dimension

Link to Submission

It took me about half an hour or more to convert that code into it's iterative version.

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

    There's a recursive version of the solution without the extra parameter. It passes pretests in about 500ms, so I can see the extra x2 factor giving TLE.

    Basically, the observation is that "started" is useless because you can determine where to start by whether you can get a value greater than 0 by continuing to take letters.

    Code: 98454285

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

    In my case , i changed long long to int and TLE was removed. long long uses more time .Also recursive calls have more overhead. But in my case it worked with int and recursion.

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

Great contest! Problems were great and well written!
I especially liked Div2E which was a beautiful problem with a beautiful solution, and solving it saved my rating from dropping to LLONG_MIN :P [couldn't solve that damned div2D :( ].

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

    can you tell me why resulting graph do not contain cycle??

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

      Write down what happens with a triangle and eventually you get:
      a+b>a+c>b+c>a+b. And you get a+b>a+b, contraditction.
      The inequalities are correct because (by order of them):
      1. a chose b over c
      2. c chose b over a
      3. b chose c over a

      You can apply it to any cycle

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

        i didn't got what is a+b or what does these inequalities say?? can you explain little more??

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

          by plus I meant xor (I should have used ^)

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

          Say you have a cycle in the graph of size 3 (a triangle), and it's made of three nodes (numbers) — a,b,c. suppose the direction of the triangle is
          a->b->c->a.
          That means a chose b over all other numbers, b chose c over all other numbers, and c chose a over all other numbers.

          So far so good? I think I'm being pretty clear so far.
          Now, what does this mean for their xor values?
          because a chose b instead of c, you know a^b < a^c
          because b chose c instead of a, you know b^c < b^a
          because c chose a instead of b, you know c^a < c^b.
          from these inequalities you can build the following inequality (which actually means my inequaility was wrong in the last comment):

          a^b > b^c > a^c > a^b

          Thus you get a^b > a^b which is not possible.

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

        I am talking ABOUT XOR TREE PROBLEM

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

Solution to problem C (Div. 2) was mentioned here.

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

    Not sure which solution you're referring to, but the solution for problem C was O(n) and I didn't see one in your link, because the problem is more specific here.

    BTW you failed the pretest because you need to do what you did in decreasing order (you sorted in increasing order and that doesn't work).

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

Can anyone please tell how to solve Div2D ?

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

Got a color change on atcoder today and now expecting the change at codeforces too. Happy Day :)

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

Isn't the only difference between div1D1 and div1D2 that we want to consider subarrays where everything occurs very few times? After all, for a given $$$f$$$, only values that occur $$$\ge f$$$ times in the whole array are important and there are at most $$$N/f$$$ of them. For $$$f \ge 2,000$$$, it reduces to D1.

I haven't solved D1, but if I did, then D2 would be easy. If $$$f \le F \approx \sqrt{N}$$$, and we fix $$$A_{l-1} = v$$$ with $$$l \gt 1$$$ (optimally $$$v$$$ should occur $$$f$$$ times), we know the optimal $$$r$$$ for a subarray $$$[l, r)$$$ that contains at most $$$f$$$ occurrences of each value and only need to check that it contains at least two values $$$f$$$ times.

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

    Yes, I solved D2 this way and don't get how you can solve D1 but not D2.

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

      Most testers reasoned this way, too! But there were some technical difficulties in coding this which apparently stopped most people. Maybe there were just trying themselves with E,F.

      Initially we wanted the problem without the easy subtask. That would not be a good decision...

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

        You could have flipped the subtasks. Then it would've had an easy subtask. This way it has a hard subtask and a slightly harder full solution, not an easy subtask.

        How do you flip the subtasks? Let the easy subtask be $$$f \le 100$$$ instead of $$$a_i \le 100$$$. Flip the scores too. It's a bit of an in-your-face hint that the hard part is for large $$$f$$$, but that's fine.

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

          I thought it's better this way. The interesting part of the problem needs to be solved by everyone, the more technical bit can get you some additional points if you spend more time on it. I'm against obvious subtasks in hard problems which require just coding. In the end the ratio of solves C/D1 is not too bad! :)

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

            I'm against obvious subtasks in hard problems which require just coding.

            Then you pretty much get one either way and just choose if you want it to "unlock" after solving a harder problem / hard subtask (D1).

            Do you like (D2 minus D1) as a separate problem in this problemset? Why/why not? These reasons don't change whether it's a subtask (in any order) or a separate problem.

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

              The initial problem was D2, we've added D1 because we (correctly) predicted it's going to be too hard. Would you rather have only D1 instead of the full problem?

              There are a couple of things which make implementing D2 more difficult than solving just D1 and I think it's fair to give some additional points for those who can do that. D1 is interesting on its own, but D2 is more natural.

              Not sure if that answers your question though

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

                Yeah, I'd rather have D1 if the main reason for splitting is implementation difficulty. This middle way feels like combining the worst of both ways: neither discarding a problem because it's implementation-heavy nor using it despite that.

                As for what's more natural... well, D1 must be natural enough to use because it was used. It's normal for problems to have constraints like $$$1 \le K \le N \le 10^5$$$, $$$K \le 100$$$. You might as well have left D2 as a simple bonus/challenge in the editorial. Instead of this "haha you might know how to solve it but can't".

                I figured out how to solve the whole problem shortly after; I'll try implementing after I wake up and tell you how hard I found that for each half.

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

                Alright, so D2 has short implementation: process values from left to right, for each value, maintain the list of last $$$\le \sqrt{N}$$$ positions and for each $$$f \le \sqrt{N}$$$, maintain the smallest 2 of the values at $$$f$$$-th index in those lists (pad with $$$N$$$); usually, we'd need a set to update the smallest 2 values, but since all elements in those lists can't increase, we actually need just the smallest 2 as some kind of mini-heap.

                I think people were just discouraged by D2 being the second subtask. It's very straightforward and I wouldn't use it at all.

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

      I solved D1 in 100 * n, and I don't see clear way to generalize it for harder version.

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

        I described one in my comment. Basically, you don't generalise, just solve it separately — that's applicable to every problem with subtasks.

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

Very nice questions

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

In problem Div2-C, looking for programs that have been scored as correct, I see that all of them considered half of W as [W/2+1], but in the text of the problem it was clear that the condition was [W/2] <= C <= W. So, if W=101, a sum of 50 was within of the constraints of the problem.

Don't you agree?

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

    read about ceil and floor of a number. In the problem was ceil(w/2) not just (w/2)

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

      You are right, I didn't know the difference between that notations, and even though I realized that the floor supposition didn't make much sense, I took it for granted. Frustrating, but I've learned something new...

      Thanks!

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

Could somebody explain the problem with my Div2C code?

https://codeforces.net/contest/1447/submission/98479826

What the code does:

Sort weights
For each weight from least to greatest:
    if adding this weight causes the sum to be  > W, continue
    else if adding this weight puts the sum in [W/2, W], we're done
    else if adding this weight makes it impossible to get a sum in [W/2, W], continue
    else, add this weight
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If there is a single value in range W/2,W we can use this single element.

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

      I tried such a case:

      1
      1 4
      3

      Output:

      1
      1

      So I don't think that's the issue

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

        I did not inspect the code, but if it does what you wrote above, then it will fail on cases like

        w/2,w=5,10

        items: { 4, 7 }

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

          It outputs:

          1
          2

          Which seems to be correct

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

            Your code seems to also check the next element when trying to add the current element in. Try this case:

            n = 3, w = 10 items = [2, 2, 9]

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

            Ok, what about this one: { 4, 7, 11}

            It seems you have that speacial case for the last element of the items, but that is not good. It might work if you throw away all items >W in the first place.

            The main error in that code is that it is horrible complecated.

            In the end you need to check if a prefix sum is in the range or a single element. There is no need for anything complecated.

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

Can anyone give a hint on div2 D?

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

Lot of people failing on test 10 in D2B. What is that test ?

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

can anyone tell me what was the pretest 6 of problem D div 2 ... thanks

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

A great problem set — brief and to-the-point problem statements (no verbose descriptions or bad attempts at humor) — nice twists to traditional problems that tested concepts down to the fundamentals (knapsack that doesn't use DP, LCS with a twist, etc.) No glitch during the contest either.

Nicely done, problem authors and testers!

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

For others who tried to solve div2E by grouping the numbers by their binary length like me: it's wrong, since $$$(1000)_2$$$, $$$(1001)_2$$$, $$$(1010)_2$$$ and $$$(1011)_2$$$ do not make a tree.

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

    If they don't form a tree, then make them by solving the group. Eliminate the msb of each number and call the solve function on this group.

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

      That may be a good idea. I (and some of my friends) mistakenly think that what are in the same group always make a tree:(

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

      Finally I understood your algorithm. It's awesome!

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

Is it normal that the same solution passes a complex D2, but does not pass a simple D1? 98467235 98467159

Hi gamegame.

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

    I feel really sorry for gamegame. The tests of D1 were mostly created by taking only D2 testcases which matched D1's input constraints and a few other testcases to make up for that. It looks like one of those killed your submission :/

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

@kpw29 , In Div1 B, I've got TLE on Pretest 12 in my 2nd submission: 98466019
Then I optimized that & it passed the pretests with 920 ms runtime: 98466474. Now in system test, it got TLE on test 12. But test 12 was under the pretests. What's wrong here?

Edit: Same code got accepted when I submit it after the system test. Submission: 98495086 . Was CodeForces' judging server slow while performing the system test? If that's the case, please rejudge my submission.

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

kpw29 I think it is reasonable to rejudge my submission for problem F. During the contest, my program passed pretest with maximum 7238ms. But during system testing, my program got TLE on test 38, which is a part of the pretest, 98482510. In contrast, I know some contestant who passed pretest with maximum 7488ms but passed system test. I think this is due to instability of judging machine and is not fair. Please rejudge my submission, thanks! By the way, I submitted the same code for 5 times after system test and they all passed. 98494884 98495166 98495208 98495243 98495274

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

    I remember this happening to Marcin_smu. Shit happens. I don't think this pretest-tle-during-systest thing should be rejudged whenever a participant asks for that. In the future though, it would be nice not to get pretest run again at all.

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

      As a writer, I believe this is quite unfair and I hope Mike will agree to rejudge these TLE solutions. We have set pretests=tests in that problem so that nobody fails F on systests...

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

        But you could as well have a few more max tests and it's perfectly possible that one of them hits running time bigger by 0.1% than his maximum from pretests. However stupid this sounds, we can now assume that every pretest is doubled and one instance is in final systests only, so it isn't that bad.

        Basically, a participant should optimize their solution if they get 99.9% of TL in pretests or in custom invocation. Unless they accept the risk.

        (but yeah, in the long run this should be fixed)

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

      If rejudging isn't the solution, what about making the contest unrated for them if they want? Thus, they won't suffer from this unexpected event.

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

Problems were great, no changes in problem statement, well balanced problems, short queue, strong pretests and fast editorial . I think we got a perfect round after a long time, thanks for the contest.

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

My contest submission for Div2 D gave TLE on system test 12. I submitted the same code post contest 5 times, and it passed all 5 times. 98495870, 98498360, 98498305, 98498285, 98498574. If its possible to rejudge my submission, please do so.

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

Congratulations to jtnydv25 for IGM.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

If programmers were tools:

How do you like it, kpw29? Your round is a real shit.

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

    Thanks for an honest opinion. What didn't you like about the problems?

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

    Be considerate; this was a good round.

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

    I don't remember last time where something made me laugh so hard as your meme xDDD.

    But problems were nice anyway ;). And D was actually quite tricky, I needed to think for a bit about it as well, no reason to be salty for not solving that ;)

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

I hope the authors will appreciate some feedback.

D1A: Standard. It is the first google result for the search "subset sum problem greedy".

D1B: Standard. It is a minor variation over the longest common subsequence problem.

D1C: Nice, maybe a bit easy but it is not an issue.

D1D: Wonderful problem, I enjoyed thinking about this one a lot. In my opinion, this is one of the rare cases where putting two subtasks was a really good idea (maybe because I solved only the easy subtask...). I spent fundamentally all the contest on this problem and thus I enjoyed the contest! For me, it was super-satisfying to notice that the most common number is the most common also in (one of) the longest "good" substring. Moreover, I like that this single observation is not sufficient, it is also required to understand how to use the observation. Last but not least, the statement is so simple that it gives you the feeling "how is it possible that I never thought about this question?". A wonderful problem.

D1E: Not read.

D1F: Okayish problem, very easy as F. Binary searching the answer and stating the problem as "count the number of segments intersecting a circle" is immediate. The remaining part is harder but not so hard (looking at the tangents is very natural). I am a bit curious on how it ended up as the last problem. Was it very hard for testers?

Let me add that I consider perfectly fine to give somewhat standard easy problems (so the fact that D1A, D1B are standard is ok).

Overall, I enjoyed participating in the contest. Thanks to the authors!

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

    Thank you for such a nice feedback. We really appreciate to hear that!

    I am the author of problem F. For both myself and kpw29 geometry is not the strongest suit so we were confident that the lemma needed to solve the problem was very hard.

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

    "Was it very hard for testers?" — no, it was not ;p. I was pushing swapping E and F and didn't succeed, but at least I managed to achieve that their scores were made equal :P

    By the way, I really love problem B, I think it is very cute

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

    Hi! Thank you for the comments. From the standings it looks like D1E was significantly harder than 1F. We just thought it's not the case :)

    "D1E: Not read." — sad! It's almost as good as D in our opinion (D is my favourite too), we encourage you to take a look and find out by yourself whether it is really that hard.

    Btw, your recent contests were great, too!

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

TIL: After failing 6 times on pretest 3 for DIV2-C, int and long int have the same range. Just had to change long to long long. Got accepted after time.

But can some one tell why do long int and int have the same range when the size of a long(8 bytes) int is double of an int(4 bytes). And long long int and long int have same size but different range ?

geeksforgeeks-c-data-type-ranges

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

    cppreference on fundamental types

    It is not guaranteed that long int is 8 bytes in every implementation. In fact, the standard only guarantees that it has width of at least 4 bytes. If you want something guaranteed to have a width of 8 bytes, use long long.

    I'm not very sure that the article you linked is correct when it states the range and size of long int. From my knowledge of how signed integer implementations work, the range they gave seem more in line with a 4-byte long implementation. An 8-byte long implementation would have the exact same range as long long in most modern computer systems.

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

Can someone please tell me why is my code getting TLE on 3rd case? https://codeforces.net/problemset/submission/1447/98493657

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

    auto it = lower_bound(s.begin(), s.end(), p);

    change into:

    auto it = s.lower_bound(p);

    You should use builtin set lowerbound function (log N). This way you're using a default STL one, random access on a set is not supported so it ends up just scanning linearly through the set and whoops, O(n).

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

.