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

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

Hello, everyone! Codeforces Round #631 will be held at Apr/03/2020 17:35 (Moscow time).

The problems are almost from me(dreamoon_love_AA), except one problem of which the idea is from drazil and developed by me. Also we want to thank 300iq for helping me prepare the round, isaf27, tmt514, rowdark, yp155136, wangyenjen, n_dao107 and woruo27 for testing this round, and MikeMirzayanov for Codeforces and Polygon.

This is my third time organizing a problemset for a Codeforces round (my previous rounds: Codeforces Round #292, Codeforces Round #320).

Good luck and have fun!

UPD: Below is a message for you from MikeMirzayanov:

About two weeks ago, we completed the crowdfunding campaign dedicated to the 10th anniversary of Codeforces. Community help inspires and provides resources for the development and operation of the platform. Thanks! With this round, we want to say thank you to Denis aramis Shitov, for his significant contribution and support. It is valuable, important and very nice when people from the community lend a helping hand and congratulate. Thank you, Denis!

UPD2: Also thanks to Shik for testing the round!

UPD3: Score distribution:

  • Div2: 500 1000 1500 1750 2500
  • Div1: 500 750 1500 2000 2500

UPD4: link to tutorial

UPD5:

I won't say sorry that the pretests are not strong. Because I don't think the pretests must be strong in every contest.

But I still want to give congratulations to the winners:

div1:

  1. Um_nik
  2. tourist
  3. Petr
  4. ecnerwala
  5. ffao

div2:

  1. 3u_my_light
  2. hydd
  3. fafafafafafa
  4. timmyfeng
  5. FrijolitoAzul

Among these winners, I want to especially congratulate Um_nik. I am quite excited when I see him solve all problems.

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

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

It's going to be a great round. Really Excited :)

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

How many problems?

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

    Usually, it is a 6 Problem and 2 Hour round.

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

    I think there will be 5 problems for both division.

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

      Thus this round must be relatively hard...unsatisfactory results ending up usually

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

        But when I still studied in university, 5 problems round is more often than 6 problems. So I determine use 5 problems.

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

          Wow! It's actually very exciting to see you back! And the problems are definitely gonna be extremely high-quality and hard to solve as well. Don't think it's wise to take part in such a round, cause oftentimes I failed to get my rating higher(sad face Anyway, wish the round a complete success!

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

        .

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

wow Setting Problem After such a long time

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

You have one of the most interesting rating graphs on codeforces!! dreamoon_love_AA

Please explain the trend!!

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

I hope problem statements will also be short and sweet just like the announcement :)

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

Didnt invited sorry_dreamoon?

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

I wish the time could be earlier,I am not able to be there.o(╥﹏╥)o

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

Hope, everybody is going to enjoy the contest. :)

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

It will be interesting to see whether tourist can regain his throne in this contest!!!!

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

can anyone suggest how to practice so that I am able to complete more than 2 problems in a contest?

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

    there is no secret to it. just solve more tasks

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

    Solve problems which are a little harder than your comfort zone. Like you can easily solve 1000 rating problems, then try to solve 1100-1200 rating problems. And don't spend more than 30 minutes on a problem if you think you are stuck see the tutorial, understand, and solve it.And of course practice a lot.

    I am following this approach and it's helping me. happy coding.

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

      Actually you can spend more than 30 minutes on a problem. You can spend as much time as you wish until you have some progress on it. Trust my words ;)

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

Problem setting tab shows you have arranged 3 contests before. Round 272,292 and 320. Then it should be your 4th contest. Why are you not considering round 292?

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

Wow! This announcement is great! I think this round is going to be a great round.

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

dreamoon_love_AA here I come!!!

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

Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).

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

this is good ....

"Knowing Is Not Enough; We Must Apply. Wishing Is Not Enough; We Must Do.".......B)[user:hajer qandeel]

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

tourist vs jqdai0815. Who will win ?

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

Excited! Looking forward to your problems.

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

.

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

Who is Denis Aramis Shitov????

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

I am not begging for followers(friends) on codeforces.

Edit: I did not even edit my original comment uh.

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

Feeling excited. Codeforces making this lockdown time easy to pass by holding the contests for programmers.

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

Let us see if this round can get 25000 registrations

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

All the best to everyone who will participate in this round. I hope to become a specialist after this contest.

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

Thank You Denis Aramis Shitov

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

tourist vs. jqdai0815 It will be exiting!

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

Thank you mr. Denis Aramis Shitov

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

I hope I can do well in this round

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

is it rated?

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

Time is not good for me!

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

Thanks !!! We need competitions like this more and more .I wish everybody good luck.

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

Wow!It seems good!

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

Will it be a Mathforces Round?

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

Looking forward to seeing concise and crap free problem statements.

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

Thank you Mr.Denis Aramis Shitov.

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

umm..what we know so far is that there will be at least 2 problems

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

.

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

thank you Denis aramis Shitov and to all other contributors.

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

Thanks, Danis and other contributors. Because of you, we have problems to solve for free.

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

Friendly reminder: watch out for FST.

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

What's the score for each problem?

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

.

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

May God bless us from queue.... All the best guys!!!!!!!!!

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

Hope I will turn blue after this contest.

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

Hope this contest does not have long queues like the last rated contest

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

When the problem scroring will be posted?

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

I think , this contest will be very intersting

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

good luck for every one)

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

Why hasn't the score distribution been published yet?

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

hoping to do well in it and get some +ve rating . let's see how it goes .

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

I think will be 500-1000-1250-1500-2000

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

Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).

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

Is it rated ?

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

Enjoy the contest

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

site seems fast today

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

noExplanantionsForSamplesForces

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

Did anyone else too missed the contest because they binge watched Money Heist ? :/ Guess I'm gonna give a virtual one now !

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

Is this the second april fools round?

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

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

    The authors likely spent some time writing the statement. Why do you think they can come up with a better explanation now in a shorter time? Besides that, it is much harder to understand your question than to understand the statement. $$$x$$$ is a number that is given to you in the input, what more do you want?

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

      If they didn't say anything it would be better than this answer

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

        No, I think it's an excellent answer.

        It lets you know the answer is written in the statement, the statement is clear (in the author's opinion) and you do not need any more information. As opposed to "oops, we left this part out" and "yes indeed, it's unclear, we will edit". Not answering creates a lot of uncertainity. "No comment" is also a reasonable answer, but I think CF wants to be friendlier than that in easy problems.

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

          Not gonna lie you're right it's just a joke I don't why I can't understand it even though alot of people solved it

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

    Lolwut, do you really think this is a reasonable question? This is definitely the appropriate answer given that thousands of people didn't have a problem with it.

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

Is this round bit hard!!!

OR only i feel so?

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

Great contest, I hate it.

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

    I hate this contest! one of my worst performances so far could not even solve B!

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

      Yeah, I also only solved 2. But the questions were really nice. I am waiting to see where I went stupid in my C and editorial for D.

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

The worst contest i had seen!

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

How to solve Div.1 C?

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

:)

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

i devoted more than 1 and half hout to problem B and ended up getting wrong answer . It just screwed up . But still enjoyed it.

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

I can't blame authors for my mistake but I think it wasn't obvious from the statement of problem div2C that queries must be performed in given order

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

    What? I sorted the queries by length and wasted 1.5 hours and about 10 wrong submissions. I debugged on almost 50 test cases.

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

    I spent about an hour trying to solve and I still didn't know this was the case until I read your comment

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

    Glad to see I wasn't the only one. Took a long time to figure out, though I place all blame on me and none on the author. I have a bad habit of rushing the reading of the longer questions.

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

    I think many have done this, and I feel coloring according to our own order is slightly more difficult question, I think I correctly solved that version, but the real question is very much easier and straightforward!

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

Anyone has an idea for pretest 6 of div2C?

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

It's not as crowded as recent contests but main page still can't load properly :(

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

i don't get it, seems like most struggled in this round , why would there be such a huge difference in div 2 rounds ?

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

was it a normal DIV2 contest?

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

The moment when you get runtime error in Div. 1 C in the last 5 mins....

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

How to solve Div1B?

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

    The main observation is that the numbers in your array must have strictly increasing MSBs (you can prove this by induction). From there, you can iteratively calculate the number of arrays with MSB at most $$$2^i$$$ for each $$$i$$$, and it's a slight modification once you have to do the MSB of $$$d$$$.

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

    Sequence is ok iff msb($$$a_i$$$)<msb($$$a_{i+1}$$$). It can be calculated with simple dp.

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

    An array that satisfies the given constraints mandates that the MSB of an element is greater than it's previous. No two elements can have the same MSB.

    Let $$$A[i]$$$ be the number of elements that MSB at $$$i$$$th position that are less than $$$d$$$.

    The answer is : $$$ ( (1+A[0])*(1+A[1]). . .*(1+A[32])) - 1 $$$.

    We choose one number from each MSB bucket. We subtract the case where we choose 0 elements. We also take modulo $$$m$$$ at each multiplication step.

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

Problem B(Div1) D(Div2):

You can't find this in OEIS

Me: 1 Hour trying to find it in OEIS

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

VeryLongCodeWithoutBugForces

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

Anyone got an idea for Div2D ? Thanks :)

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

    Main idea: We can find an array b for a given array a iff, for all i, a[i] has a larger leading bit than a[i-1].

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

Super balanced contest. Apart from that, ABD seem pretty nice, C could be but getting to right implementation can be tough and the constraint $$$2^20$$$ seems too tight.

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

    After being unable to correctly implement my idea for a while, I realized it seems equivalent to a greedy which subsequently passed.

    Apply f on the topmost node such that after applying f there is no 0 in depth <= g. Very easy $$$O(nlogn)$$$ implementation for $$$n=2^h$$$.

    Hopefully correct.

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

      Probably correct. I simulated that in a much more complicated way (and forgot that $$$G$$$ isn't $$$H-1$$$ because the sample doesn't contain that), but your example supports my point that a lot of this problem's difficulty is getting bogged down in ugly implementation.

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

        Yeah, my code got extremely messy exactly due to $$$G$$$ not being $$$H-1$$$ as well. I didn't enjoy the problem either, but I guess it's still nice that a short correct code exists.

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

      Proof: Consider the first time we make an operation not on the root, but on the path that making an operation on the root would modify. But making an operation on the root would be strictly better, as then all vertices would contain a smaller number. Also, applying that operation immediately after the last operation on the root instead of where it was originally done doesn't change anything.

      Thus, we can first greedily apply operations to the root, then independently solve all branches of the path operating on the root would modify.

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

    Actually my solution was super simple to code. I guess there are many ways to think about this problem, because mine solution is significantly different than one described by Enchom

    Its code is here: https://ideone.com/1XiSlu

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

    Personally I don't think that it's ok when D1B level problem becomes D1D level because you have to restore the answer.

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

      Well, restoration of the answer in my solution is

      for (int i = n; i >= 1; i--) {
        if (!taken[i]) { cout<<i<<" "; }
      }
      

      where taken[i] means that I take number a[i] in the final answer :) (which I guess everybody needed to determine in order to get the first number right)

      Or were you talking about Div1D and somehow messed up which comment you reply to :P?

      EDIT: Ok, I think it is me who messed up xD. I kinda thought discussion under this post is about Div1C only, based on comments above. Don't mind me :<

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

Div1 D solution? Seems really hard. Seen a ton of similar problems but none of the usual techniques worked. Probably missing an observation of why some greedy part is correct.

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

    Number of operations we have to make is

    $$$ 1 + \max(\lceil\frac{\text{# of adjacent pairs of same character}}{2}\rceil, \max_{c \in \Sigma} (\text{# of adjacent pairs of character c})) $$$

    As each operation decreases both quantities by at most one.

    Greedy that works is always choosing the color with most adjacent pairs, then selecting some interval starting or ending with an adjacent pair of that color, and not both starting and ending with an adjacent pair of that color.

    Implementing this greedy in $$$O(n^2)$$$ is easy, but I couldn't implement it fast enough to not TLE :(

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

    find all occurrences 'aa' for all characters. Lets say if these type of occurrences is maximum for character a currently, then delete substrings of type aa....bb or bb....aa till it is possible to do so. This process ends when there are occurrences 'aa' for only one type of a character. Though the implementation was a bit too frustrating for me.

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

    You can reduce it to the following problem: You are given a string and in every step you can remove two consecutive letters if they are different or an arbitrary single letter and you want to make it empty in the smallest possible number of steps.

    Answer to that problem is max((length+1)/2, max frequency of a single letter)

    Reduction from original problem is that for every pair of consecutive equal letter, you put that letter into that string in reduced problem. It can be easily seen that operations of removing beautiful string in original problem is allowed operation in that reduced problem, so they are equivalent.

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

      Thanks. I made the reduction but for some reason the answer wasn't obvious to me. Quite disappointed that this is the solution to be honest.

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

      And how to solve the problem after reduction? I found $$$\mathcal{O}(n^2)$$$ solution, but it shouldn't fit in TL if $$$n \approx 10^5$$$.

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

        Oh well, that is a bit tedious task. In each step you determine the letter with biggest frequency (in O(26) cause I keep them explicitly) and we want to remove one of its occurences with some other one. Then you iterate over all other letters (another additive O(26), but beware, it's amortized!, because of reasons that will be clear later) and check whether there is any place where these two letter currently touch. In order to perform a single check you keep two-dimensional array (with size 26x26) of vectors of pairs that tell you where are currently neighbouring occurences of these pairs of letters. When you decide to remove some pair you need to remove 3 pairs and add 1. However removing is a bit inconvenient, so I do that lazily. That is, I do nothing in that moment of removing that pair and whenever I see some candidate for a neighbouring pair in one of these 26x26 vectors, I check whether this pair is still valid (that is, both letter are still alive) — if it is then I use it, if it isn't then I remove it. In order to know what new pairs of neighbouring letters are created I use my own bidirectional list. In order to restore indices in current string (based on global ones that I use everywhere) I use another bidirectional list for alive original positions and Fenwick tree.

        I hope my code can be of some help: https://codeforces.com/contest/1329/submission/75411250

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

How to solve Div 2 D ?

I tried to do kind of cheating using Berlekamp-Massey algorithm to extrapolate the sequence manually but didn't work out.

Also if anyone got AC using BM algorithm please post your solution link.

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

How to solve div2 B? My submission gives TL on pretest 2.

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

    maybe you used memset in each test case

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

      yeah, is it wrong?

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

        you have 10^4 test in each test case and you used memset on a array size 2e5 so it become n^2

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

          Using memset for size n won't give tle as sum of n over all testcase always less than 200000. And all a_i is also less than n.

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

          for clearing the arrays in independent testcases its better to use fill function . this will take the time of size n given in the input . It doesn't lead to tle since sum of n over all testcases is <=2e5.

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

        I also used memset in each test case... 4 times (whoops? :)) )... and I passed all the pretests, so that shouldn't be the problem.

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

          If you use memset for size n then will never give tle but if you use memset for size 20000 in each case then you will surely get tle.

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

            I used size 200000 each time. So... I guess a sweet TLE is awaiting me? :)): ...

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

              I hope as 10^9 iteration is very large to complete in 2 seconds.

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

    You can use a multiset and a set
    Create a multiset and a set that will be used as the prefix
    Create another multiset and a set that will be used as the suffix
    Iterate through the input array add the current value to the multiset prefix and the set prefix too
    And remove the value from the multiset suffix and from the set suffix if the multiset doesn't contain the current value again
    Now to check if a state is valid the multiset prefix size should be the same with the set prefix size and the largest element in the multiset prefix should be equal to the size of the multiset prefix check same for the suffix(multiset and set)
    If valid add i and n — i — 1 to the result

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

    Traverse the array until you get 1st repeated element. When you get that break the array into two array at the point where you get 1st repeated value. Then simply check if two array is permutation or not.

    Repeat the process starting from back.

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

In problem B, it was clearly written that two permutations are of non zero length, but this surely wasnt the case.

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

    No, both permutaion length was >0

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

    But they are of non zero length. a problem with the statement was the constraints saying both l1 and l2 <= n , not only their sums.

    still , they are of non zero length , maybe you adding that to your code only fixed another bug.

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

      Possibly, but adding an empty permutation somehow passed that testcase.

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

        then unfortunately you probably will fail the main tests. this test is clearly wrong for you:

        1

        2

        1 2

        it should output: 0

        while yours probably from what your saying will output:

        1

        2 0

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

          1 2 1 2 answer for this should be 1 2 2 why it is wrong?

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

            my bad , i am not sure why the comments here don't end lines like intended , fixed now.

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

    And Poor me, couldn't figure out if l1=l2 they are considered as same permutation in an hour

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

I read div1A statement and for some reason, I thought "well, it's optimal to sort the values in decreasing order", but i never read that I wasn't allowed to change the order in which I use the array values. I realized about this when there were 10 minutes remaining of the contest. So sad to lose rating for that silly mistake. Goodbye div1, it was nice to meet you :(

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

How to do problem B div2?

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

    First try checking valid sequence like all elements are 1 to n-1 , atleast there is one element with count 2. After that you can check till particular index if max=index and min=1 and sum=sum of permutation till index than insert in ans Same way for reverse array Take common elements

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

      Hey can you tell me why this fails ? link

      Thank you!

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

        Because you are checking validity of permutation using sum of first x numbers. According to your code, both the below testcase will be considered valid permutation because their sum is equal to the sum of the first 5 elements. Sum({1 2 3 4 5}) = 15 [Valid] Sum({1 3 3 4 4}) = 15 [Not Valid]

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

          I submit 3 wrong submissions while contest due to this, but finally Igot the point where I am stucking

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

Never noticed that the input is not a permutation in problem C, so sad......

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

What are the solutions for Div2C and Div2D?

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

How to solve Div2 C ?

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

    You are given m segments of different colors and you can slide these segments in a row of size n.
    The maximum length we can get by spreading these segments is equal to the lengths of all the segments(i.e without any overlapping), let denote it by sum.
    So if sum is less than n, it is not possible to cover the whole row.
    Now if sum >= n we have to compress it to fit in the row size of n. We have to overlap some units of the cells(possibly zero) such that all the colors are visible.
    The number of units cells to be overlapped is simply sum-n.
    So start placing the segments from start of the row and after leaving sufficient units of cell place next segment(trying to overlap as much as possible but less than required length), and keep doing this for all the segments maintaining the required number of cells to be overlapped.
    And if at any iteration the end of segment goes out of the window of size n, in that case answer is not possible.
    My solution with above approach

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

1A(2C):hacker's paradise

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

Tried hacking O(M^2) solution on A (http://codeforces.com/contest/1329/submission/75404901) with ~2.5B operations. Passed in 1.45s (facepalm).

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

    It looks like the optimizer changes while(ans[i] + a[i] - 1 < lst) ans[i]++; to ans[i] = lst - a[i] + 1 ?

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

      No, since if it did, the code would run much faster than 1.45 seconds. It's just that the operations are very simple and the processor manages to execute them in time.

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

In problem c (div2) i tried following approach : first sort in descending order and then choose 'p' value such that first position of the current coloured segment does not coincides with first position of last coloured segment.my submission : link .can someone tell the mistake in approach ?

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

How to solve Div1B/Div2D?

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

    Use the observation that the required sequence is essentially a sequence of numbers such that the most significant bit is in increasing order. So, the max length of this sequence is at most 30.

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

      Oh god, I got that observation before, but I just stopped thinking and doubting the problem statement which says it can't be found in OEIS, lol. I started spend too much time seeing similar pattern in OEIS and looking for how to code it. I should've just trusted the problem statement, what a nice lesson learned.

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

Wow, that's a pretty bad contest if I've ever seen one. Speedforces for a lot of blues, who will now undeservingly be candidate masters.

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

Can anyone tell what could be the pretest 2 for DIV2 B...

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

WOW div2D/div1B is quite tricky. You can find the sequence on OEIS this sequence but only those few numbers in front of the sequence is right for this problem. So tricky/QAQ

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

I spent an entire hour on C not realizing that all lengths must be FULLY painted (when at length 3, you cannot start painting at the next to last position for example). Even though it was very clearly mentioned in the statement. I'm mad at myself.

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

In Div2 problem C, I make the l array non-ascending. And, if sum(l1+...+lm)<n print -1, else for 1 to n, if
i+l[now]-1<=n, then ans[now]=i, sum-= l[now], now++ ,else print -1. But it get wrong answer pretest4! Can someone tell me why, please? Here is my code 75414479

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

    I find it. Because it not need be sorted!

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

    I think I tried the same approach with you and got stuck at pretest 4 as well. This is what I did:

    1. combine li and its index, then sort on li in descending order. (Need to keep the index information to retrieve a correct answer because we are forced to process the input array in the given order).

    2. if the sum of all li is less than n, it is impossible, print -1.

    3. otherwise compute the difference between this sum and n. We'll need this many overlapping picks. As long as diff > 0, we include the next unpainted cell in our current operation. When diff == 0, just pick non-overlapping unpainted cell ranges.

    My submission is 75413846

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

      As I said before, it not need sort it. For this case 5 3 1 1 5 if you sort it ,you will get wrong answer.

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

Video editorials for B, C, D out!!

B

C

D

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

One more time, there exists an other platform for such contests...

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

    Just curious, did you mean AtCoder or Codechef?

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

    Finally someone said... i was gettign the same feelong throughout the round. These problems resembeles or feels moee like atcoder grand contest problems. Soop tricky.

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

      I hardly solve 2 problems on atcoder grand contests. Sometimes even only one problem. So this contest is definitely much easier. It is like regular div 1 contest.

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

    you mean there's a platform for good contests?

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

      No, for the contests where all the tasks are more than less ad-hocs. They aren't balanced contest.

      Huh, how to say that. Let's imagine playing chess. OK, maybe knights are the most complicated pieces and it's possible to show who's the best in using them smartly, but there is some reason that there aren't the only pieces and even more, there's no more of them than any other pieces.

      See? balance

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

        You're just stupid, sorry man

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

          Don't you think that continuously considering some complicated processes and guessing some lemmas in each problem is rather exhausting and after a few problems it stops giving any pleasure? In normal contests, you switch between different areas of CP, so it stays fun and not boring.

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

            I think that description of ad-hoc as "considering some complicated processes and guessing some lemmas in each problem" is hilarious

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

              OK, maybe ad-hoc is a mental shortcut, but you know what I'm talking about.

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

            Maybe it is exhausting, but it is still better than "I read the statement, now let's write 300 lines of code"

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

              Problems that wouldn't appear on AtCoder aren't only "write 300 lines of code". For example, I guess that it's impossible for AtCoder to hold a problem that uses any string suffix structures in any manner, which usually gives very short codes (if an automaton is used for example). There are a lot of such examples, not considering only copyable things. And why? The only algorithm which still appears is an Eulerian Cycle ;_;

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

                I don't think that's impossible, just 95% of string problems are boring AF, so AtCoder staff don't see a reason.

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

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

      This contest could also consist of 5 geometry problems and it would be bad in exactly the same manner.

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

    Em, what? Do you consider D to be requring too much thinking so that it fits on AtCoder only xd? I think it was actually coding-heavy fitting CF standards very well.

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

    What do you want exactly? The problem where it is obvious from statement in what direction you should go (i.e. probably will need Heavy-Light Decomposition with Li-Chao trees, need to figure details)?

    I can't possibly understand what don't you like about AtCoder problems.

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

      Man, I love AtCoder problems, they are really surprising. How things are connected in them and how everything magically works. I don't like AtCoder problemsets.

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

    One more time, participants blame the contest for their bad performance

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

How to solve the problem Div2C?thanks!

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

Was it really necessary to have to restore an actual answer for every problem instead of just the value of whatever we're optimizing? It was a fairly hard contest and this just made everything more error-prone while not adding a lot of conceptual difficulty (e.g. Div1 A,C,D)

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

How to solve Div1C?

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

Div 2- D can be solved using Dynamic Programming

Here's my shot:

Let's say we have n numbers.

Then if we choose first element (having most significant bit i), then the rest (n-1) elements can be chosen amongst all numbers having most significant bit lesser than i. You can see intuitively that for condition 3 to satisfy (increasing order of array b) only the most significant bit of first element matters.

For bits 0 to 32, we calculate no. of numbers having most siginificant bit i in range 1 to d. This can be done by calculating s=log(d) and for i ranging from 0 to s-1, do c[i]= power(2,i) and for s: do c[s]= d-power(2,s)+1. Note here, that c[i] denotes the count of numbers having ith bit as most significant bit.

Once we have our array c ready, lets apply Dynamic programming to this problem. Note that bits upto s only matter as onwards s, array c is zero.

Upto ith bit, no. of ways to form array a= (no. of ways to form upto i-1 bit) + (no. of arrays a having size 1 but most significant bit is i) + (no. of ways to form upto i-1 bit)*(ways to select the most significant bit to be i).

i.e. Our DP Recurrence becomes: dp[i]= dp[i-1]+c[i]+dp[i-1]*c[i].

You can apply modulo m, at every step. Also, you need to iterate only upto bit s.

DP[S] will be the correct answer.

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

How to avoid TLE for Div 2 prob B. I tried the brute force way, considering all ways of splitting the sequence?

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

    You can use Prefix Sums and Suffix Sums. I wasn't able to solve the problem in the contest but I've solved it now (hopefully! but i'll only be able to submit and check if it's right once the problem appears in the ProblemSet).

    Here's my code that I think solves the problem:

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

    Let's consider the first permutaion is 1~n1,the secondary is 1~n2,and let n1<=n2 , than we have the times of 1~n is 2 ,and n1+1~n2 is 1. If the above conditions are not met,we output -1.then we just need to check the 1~n1 from the front and from the tail,Be careful of the situation of the n1==n2

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

3 brainless heavy implementation problems in a row. Should be on Codechef or Leetcode lul.

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

Can someone explain how the answer for 2 999999999 in question D is 3?? Only possible array is {1,2}

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

imbalanced contest -_-

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

Div1B/Div2D can still be solved with OEIS A028361

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

Did anyone solve Div2B using RSQ? I've tried but failed to approach the right adjustment :"(

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

What's test 66 in div1C/div2E? :O

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

    I think it's just a random case. Most people seem to have failed (me included) by forgetting to clear the input array properly between test cases.

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

    It can happen that you didn't clear some values in $$$a$$$ from previous testcase ( range $$$[n+1, 2n+1]$$$ can be used in previous testcase).

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

    You just needed to set the children of the lowest level to 0

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

you can be high but you can't be high enough like me. what a contest for me. ![ ](Capture50910b6fa16c4542.png)

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

FailedOnMainTestsForces

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

Weak pretests cost me becoming purple :(

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

weak pretests?

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

FailedSystemTestForces

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

bad pretests so pissed right now

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

Despite a series of unsuccessful submissions due to carelessness, and 1 resubmission (I didn't know that lost points too), I'm still optimistic that this will make me a Candidate Master :D

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

Weak pretests on Div2C?

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

multiset count is o(n) , learned something new -.-

Nice Challenging problems though

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

FSTForces

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

Way too many fails in the main tests..... Thats exasperating!

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

Was the round harder than normal or is it just me?

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

hey can anyone please tell me what is wrong with my solution of Div2 A https://codeforces.com/contest/1330/submission/75419943

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

    Firstly: please don't just paste your source code to comment. Use at least

    Block
    

    to make it more legible. But preferably just post link to your solution

    Secondly: I think your solution fails when optimal answer doesn't use any of $$$a_i$$$ at all, but just appends numbers from $$$[1, x]$$$ (that is if $$$a_i > x + 1$$$ for all $$$i$$$)

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

    Scroll to the bottom of your submission and you can find the test case you fail at.

    However, some cases are pretty big and are not displayed completely. It's very likely that you might have missed an edge case or something.

    Here's my submission that gets AC: https://codeforces.com/contest/1330/submission/75363519

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

Sorry but it was a coincidence .. I published my code on ideone.com that's why the problem has occured. Please give my ratings back

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

Why does Div1 B have multiple testcases? What is the solution that would pass otherwise?

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

    I hope people who rely on OEIS can search easily by just copy the output, I think it's a joke that the first nine numbers can still be found in OEIS.

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

      But it's interesting that the differentiation between each adjacent numbers can still be found in this, according to this comment.

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

        Maybe I'm too stupid, I don't know what's the relationship between the OIES sequence and Div. 1 B. ( •̥́ ˍ •̀ )

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

          d=1 -> 1 *1

          d=2 -> 1+ 2
          d=3 -> 1+ 2 *2=5

          d=4 -> 5+ 6 *1
          d=5 -> 5+ 6 *2
          d=6 -> 5+ 6 *3
          d=7 -> 5+ 6 *4=29

          d=8 -> 29+ 30 *1
          d=9 -> 29+ 30 *2
          ...
          d=15-> 29+ 30 *8=269

          d=16-> 269+ 270 *1
          d=17-> 269+ 270 *2
          ...
          d=31-> 269+ 270 *16=4589

          d=32-> 4589+ 4590 *1

          The highlighted numbers form a sequence which is same as OIES.

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

Disgusting pretests!

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

More participants make pretests weaker

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

Test $$$66$$$ in C is the first test where the values $$$h$$$ aren't non decreasing in the testcases btw.

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

Can someone explain to me why I'm getting this error? "wrong answer duplicated solution on test 324 (test case 324)" this is my submission : https://codeforces.com/contest/1330/submission/75421301 Thank you for the contest.

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

Добрый день. Пришло письмо, что мое решение задачи A (div 2) совпадает с решением другого человека (моя посылка была ранее, его позже). Так произошло из-за того, что я использовал онлайн компилятор ideone, что могло послужить воровству моего решения, ибо оно оказалось в общем доступе. Просьба не банить мой аккаунт.

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

Solution to Div.1 C: I believe solution was based on heuristics and greedy or at least mine was. The basic approach is choose the highest element in the array, check that after it is removed , and all it's children move up above, number of non empty nodes at indices more than (2^g — 1) are less than equal to the remaining moves or not. If they aren't, do not remove the element from the final array otherwise make appropriate changes. Edit : Time Complexity (NlogN)

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

I submitted a fake solution on problem C(div2) during contest. I figured it out and spent half an hour to fix it. But I find that the fake solution could pass system tests, WHY? Hacking it doesn't even need special cases but simply 10 2 9 2 will work. Also 6 3 4 1 1 and 10 2 8 5will work too. Maybe the system test isn't that trustworthly? submission: 75417494 You can check my code and check that there is nothing "made to be hacked".

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

Wowwwwww I became expert!!!!!! What a nice contest!!!! My second favorite coder Petr also returned after a long time and that too with a banggggggg!!!!

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

FSTForces

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

When the editorial will be published?

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

The worst cf contest in recent times. Very disappointed by the pretests. I mean I understand that the edge case I missed was a very obvious one but that argument goes both ways. I definitely feel it should've been one of the pretests, if not even the sample.

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

    I also think this is the worst cf contest in recent times. Because this is the only contest that I cannot take part in. (`Д´)

    (`Д´)

    (`Д´)

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

      Sorry, I guess I'm just disappointed with how things unfolded. I literally gave up 15mins before thinking I couldn't solve more and I had C in the bag.

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

      dreamoon_love_AA Actually, thank you for making the contest. Although I lost a few rating points, but it was good use of my time, and I had lots of fun. !! I know its a lot of hard work for you :)

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

I really liked this contest! Especially Div2C problem. Thanks!

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

Solution of Div1C (with proof), really like this one.

First, make two observations about the operation in the statement:

Observation 1: The operation is a removal of an element and preserves a heap structure.

Observation 2: Every non-removed number finishes on the path connecting the initial position and the root.

Denote $$$T(k)$$$ the set of initial values in the subtree below $$$k$$$. It is easy to show that $$$new(k) = min(T(k))$$$ for $$$k$$$ leaf and $$$new(k) = min({v \in T(k) : v > new(2k), v > new(2k + 1)})$$$ is the best we can potentially do.

To show that this is possible, we remove every number, which should not finish in the smaller heap, in decreasing order. The key invariant is that when removing number $$$k$$$ all numbers greater than $$$k$$$ are at their final positions. If the invariant broke at some point, then $$$k$$$ would be below its final position and a number above $$$k$$$ would violate the heap condition.

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

    The other way to look at this problem is induction. Let $$$x$$$ be the root of the heap we're solving the problem on. $$$l(x)$$$ and $$$r(x)$$$ are its left and right children. Without the loss of generality, let's say $$$key(l(x)) > key(r(x))$$$. Now, let's investigate if it's optimal to "pull" the node $$$x$$$. We can see that the path of the pull will go through $$$l(x)$$$, so it will not affect the "subheap" of $$$r(x)$$$ (might not be vice versa). Now notice that if we pull $$$l(x)$$$ instead of $$$x$$$, the same leaf would be lifted, so the effect of it would be exactly the same, just the value we pull would be smaller. That means, it's at least as optimal to pull a parent of a node than a node itself. The beauty is that we actually don't have to sort anything and can solve the problem in heap order: from the root pull the value while you can, then go to children in any order since they're disjunct.

    Unless the proof is wrong ofc.

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

why there was no deduction in points even after wrong subs in the contest

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

Became specialist for the first time, thanks to Denis Aramis Shitov.

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

Why are we not allowed to view all the tests after the contest is over??

its not always easy to figure out the issue with the code and it could very well be that the logic is not 100%% editorial alike but maybe serves as an alternative with few things taken care of.

I can never know where I went wrong.. and will have to just suck up the editorial approach which won't help me anyhow as its an A question which hardly anybody can have anything to gain to unless it had something to do correcting an alternate approach..

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

    It's unfortunate but here's what I do if I want to explore bad test cases faster.

    1. You can view small tests. But large tests will be trimmed, so you can't view large tests.

    2. Grab the editorial solution or any AC solution. Test on random small inputs and compare on your solution.

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

when the editorial will be out..??

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

Suprised that people have short solutions to Div2 C. I solved it only after contest with complicated logic T_T. https://codeforces.com/contest/1330/submission/75428216

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

Why is my submission for Div2 b giving TLE verdict? My submission 75410566

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

I have a question about the system test queue. Is it now following some random order instead of the submission time order? I find it quite strange to see some participants having A,B,C,D tested while all of mine are still in queue.

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

Why this submission 75370728 gets TLE, I used map instead of set here 75429219 and I got AC

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

my submission on problem B: Your text to link here...

I get right answer on rextexer compiler ~~~~~ Your code here... ~~~~~

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

Were pretests this contest made intentionally weak? I counted on Div1C, and 110/451 (around 25%) of participants who solved it in contest failed system tests. In addition, the pretests for C had all non-descending H in successive test cases, resulting in a lack of need to reset arrays between cases.

I thought the purpose of pretests was to prevent too much of a load on the queue, as well as (for example) catch people who forgot to cover certain edge cases, not to intentionally screw over contestants who solved the problem but forgot something as negligible as resetting arrays. These kinds of tests should be included in the pretests.

I think it would be better to avoid this kind of situation in the future regardless of whether it was intentional or not (although it seems to be intentional in this case).

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

Why this code gives wrong answer. My approach is to find lengths l1 and l2 first from the count of elements and if (l1+l2)==n then check first l1/l2 elements.

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

it was not hard and interesting

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

Where is the editorial?

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

Okay, sorry to burst your bubble, but div.2D (div.1B) was a poor choice, at least for the Codeforces format. Upon reading the problem, I noticed immediately 29, 59, 89 and it didn't take long to figure out the rule behind the sequence (brute force generator and a little bit of thought).

It's not that I could not (or did not want to) solve the problem itself, but given only 2 hours it is better to write any solution that works, and maybe upsolve "honestly" afterwards. But during the contest it's very difficult even to start thinking in the intended direction when you have a number pattern staring you in the face. I'm pretty sure those who solved it (I'm talking about div.1 here) for ~5 minutes did precisely this.

Again, the idea and problem are good, it's just that the presentation has some unintended consequences (read: complete the sequence 1, 3, 5, 11, 17, 23, 29, 59, 89, ...)

P.S. And yeah, given that, it might have been better to switch div.2 C and D places (div.1 A and B).

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

Fstforces?

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

Thank you for a good contest!

As a feedback, I'd like to say that writing sample notes (text explaining example tests) is a good practice, and making illustrations to samples is a brilliant practice.

Please consider those two in your future contests. Thank you!

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

I've found a wrong program of Div.2 A whose array index is out of bounds. I tried to hack it but got an "Unsuccessful hacking attempt". And the program even finally passed the System Test. So I really wonder how the compiler in CF works and why the program can't be hacked. Here's the test: http://codeforces.com/contest/1330/hacks/628623/test Here's the code: http://codeforces.com/contest/1330/submission/75390643 The index of the hack is #628623. Thx a lot if someone can help me!

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

    Memory access outside of array bounds is undefined behavior. That means any outcome is possible, including passing a test.

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

wtf I lost my rating because of two characters

75405872 75456985

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

What's wrong answer duplicated solution on test xx (test case xx)??

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

Can someone help? What did I do wrong in Div2B.

I took xor of 1,2,...max_element and xored that with the first 'max_element'(L1) number of elements. If it was zero then I take xor of 1,2,3...(n-max_element)(L2) and xor that with the remaining elements that are max_element+1 to n.

If that is also zero that is one permutation. Same way from the other side.

I fail on pretest-2. It says testcase 324. I cant reach that obviously. Help please?

75388010

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

I understood the tutorial solution of Div2 D/Div1 B. But I see a lot of people used dp to solve the problem. Can anyone explain their dp solution?

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

I don't understand why on Div2B, one of the testcases is:

4
1 3 3 1

This was not made using two permutations.

I get that the problem states that this could be the case but why would you say: "First l1 elements of a is the permutation p1 and next l2 elements of a is the permutation p2" when in your test cases that is not going to hold?

Its a bit misleading.

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

    I believe there exists some way to express the thing more clearly. But the statement contains the sentence "Note that it is also possible that there will be no ways.)" and also there exist some tests in the example show these tests will appear. So it's acceptable.

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

[problem:631A]div2 pls can someone help me to find a testcase where the output is 1 Because I think, the should be atleast 2