kpw29's blog

Codeforces Round #683 by Meet IT (Div1, Div2)
By kpw29, 4 years ago, In English

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

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

Comments Comments (173)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

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.

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

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.

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

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

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

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

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +116 Vote: I do not like it

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.

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

    I am sure it will be a great round. kpw29 and rest of the team were very excited about making it :D

    → Reply
»
4 years ago, # |
  Vote: I like it +471 Vote: I do not like it

my dear wife Marta

weird flex but ok

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

    look at the bright side, at least, you have the freedom.

    → Reply
»
4 years ago, # |
  Vote: I like it +157 Vote: I do not like it

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?

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

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

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +562 Vote: I do not like it

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

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

    I'd participate in the round if I wasn't mentioned as a tester.

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

      I think it is more about whether you have seen any of the problems before?

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

        I think it is more about mentioning people who spent their time to test your round.

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

          To not be misunderstood, I don't really care that much, just messing around

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

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

    Looks like you almost got more upovotes than the round itself :D

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

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

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it +122 Vote: I do not like it

Is it rated?

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

    Yes, the round is rated for both divisions.

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

    Plot twist: the comment above gets many upvotes. What about making today a kind day for muchieej_orz? Community, I believe in you!

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

Hooray! 2 contests in three days!

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Brace yourselves for another antontrygubO_o show:)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +89 Vote: I do not like it

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)

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

    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?

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

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -36 Vote: I do not like it

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

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

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

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

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

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

please, don't get unrated again...

→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thumbs up20201114-102007

→ Reply
»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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

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

Now this my friend is what you call an announcement

→ Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -42 Vote: I do not like it

I hate problems

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

[Deleted]

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

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

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

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

      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.

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

      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.

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

excited to participate in this round...

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

https://www.youtube.com/watch?v=jRKSlI-Qvcc

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

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

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

    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.

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

What is pretest 6 for div-2 D?

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

    Pretest 6 was cancer man

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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

    → Reply
»
4 years ago, # |
  Vote: I like it +64 Vote: I do not like it

How to Solve Div-1 D??

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve div-2 E ?

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

    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.

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

How to solve Div2-D ??

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

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

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

    because then the answer would always be 0

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

    Yes, cause in other case answer is 0

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

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

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

    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)

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

how to solve div2 B?

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

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

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

    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.

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

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

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

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

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

      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

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

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

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

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

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

          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

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

            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

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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

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

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

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

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

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

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

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

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?

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

    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.

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

      Oh you are right. I made a very bad assumption. Thanks!

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

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
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 :( ].

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

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

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

      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

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

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

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

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

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

          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.

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

            Yes i got it Sir :) Thanks for such a amazing explanation.

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

        I am talking ABOUT XOR TREE PROBLEM

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

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

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

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

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

https://codeforces.net/blog/entry/82067 Copied from stream lol

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

Can anyone please tell how to solve Div2D ?

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

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

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

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

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

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

        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.

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

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

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

            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.

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

              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

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

                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.

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it -10 Vote: I do not like it

                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.

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

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

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

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

        → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Very nice questions

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

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?

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

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

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

      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!

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

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
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      I tried such a case:

      1
1 4
3

      Output:

      1
1

      So I don't think that's the issue

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

        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 }

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

          It outputs:

          1
2

          Which seems to be correct

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

            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]

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

              Got the issue now. Thanks!

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

            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.

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

Can anyone give a hint on div2 D?

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

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

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

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

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

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!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

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

    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.

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

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

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

      Finally I understood your algorithm. It's awesome!

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

Nice tests in D1/D2 https://codeforces.net/contest/1446/submission/98467159 https://codeforces.net/contest/1446/submission/98467235

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

    Lol what is this .. same code passes at one place and fails at other ?

    → Reply
»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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

Hi gamegame.

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

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

    → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +118 Vote: I do not like it

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

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

    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.

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

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

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

        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)

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

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Congratulations to jtnydv25 for IGM.

→ Reply
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it -60 Vote: I do not like it

If programmers were tools:

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

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

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

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

    Be considerate; this was a good round.

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

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

    → Reply
»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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!

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

    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.

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

    "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

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

    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!

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

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

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

    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.

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

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

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

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

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply