FieryPhoenix's blog

By FieryPhoenix, 5 years ago, In English

1348A - Phoenix and Balance

Tutorial
Solution

1348B - Phoenix and Beauty

Tutorial
Solution

1348C — Phoenix and Distribution

Tutorial
Solution

1348D - Phoenix and Science

Tutorial
Solution

1348E - Phoenix and Berries

Tutorial
Solution

1348F - Phoenix and Memory

Tutorial
Solution 1
Solution 2
  • Vote: I like it
  • +533
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +185 Vote: I do not like it

Wow! I didn't expect the editorial published so fast.

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Thanks for the fast editorial!

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

Editorial so early -.-

»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Wow, it was very good contest. Fast editorial, cool tasks with short conditions. Thanks!

»
5 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Damn
I feel so stupid after seeing the solution for B
Nice problems man!

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

    Can anyone recommend practice problems for constructive

    I really suck at it

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -346 Vote: I do not like it

      I suck at them too. Hate constructive. Downvote the author for making so bad B

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

        Nahh B isn't bad
        We just suck XD

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

        Perhaps that mindset is one of the reasons you are hardstuck Specialist. Never blame the problem, only blame yourself for not practicing enough. With this mindset, improving quickly suddenly becomes much easier for anything you do :)

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

          Can u pls explain why we go upto n*k.. I did it that way but not getting how its working

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

            We need to print at least n numbers. Printing k of the numbers (if all unique) or c unique numbers and k - c "1"s (or any other digit) (where c is the number of unique elements) will guarantee that you print all numbers in the input, which is required in the output whatsoever be the insertions you make. The primary goal of constructive problems is to come up with something simple that does the job. You could go all in and actually calculate the sum of first k numbers and then go about trying to solve the problem, but that just makes life a lot lot harder.

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

              Sire, I've a doubt in part B. When we store element in set, elements are reordered. So when we output the elements, order may be different than what is in the original array. Since we want to preserve the order, how will it work? Thanks.

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

                you don't need to preserve order. you have set n times: [][][]<- denote set 3 times. let say you need 413 as subsequence. because in each set you have each unique element, you can remove everything from first [] except 4, from second [] remove everything except 1, from last [] remove everything except 3. And, by definition resulting is subsequence, subsequence it's anything you can get by removing elements.

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

            You can think it like this :

            Suppose k=3 and the sequence is 4 3 4 2 So, you need to make a new sequence with period 3 basically.

            You can make a set with distinct elements from the original sequence and of length 3, like (2,3,4). Now, you just replace every element with this small sequence. You'll get -

            2 3 4* 2 3* 4 2 3 4* 2* 3 4
            

            (* represents the elements in the original sequence)

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

        No, It was a great problem Just needed to think in another way :/

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

        Why downvote author try to do it.

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

        Instead of blaming the author, you should focus on practising more.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -128 Vote: I do not like it

          Stop giving advice when you become just become specialist first time. No one asked for it.

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

            Now you are criticising me instead of practising more. That's the reason for your fall. And yes, I become an expert first time with my own potential. And I didn't blame anyone when I was falling. I was seeing my mistakes and was improving them. You should try this too.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -112 Vote: I do not like it

              WTF retard. You are not expert you are barely specialist. And no one cares for advice unless you are candidate master or above. SO pls gtfo

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

                You too are not eligible to decide the quality of the question, so better you Fuck Off and start practicing.

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

                Please, respect others at least.

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

            are you shit!!!...... suraj_gupta is right..... and i am watching your every comment.... why giving so much hate ....... you were not able to solve problem during contest then it is your problem not of Author.... Around 10000 peoples had solved it... nd you are accussing author for your fault....

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

            The worst people are those who have not very high rating,looking down upon those who have lower rating,but diligent guys

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

        seriously you want to blame him for doing so bad in the contest yourself. That's ridiculous.

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

      In the last contest by dreammoon, the problem div2 C was excellent read its tutorial. It is more like a general way to solve any constructive algo. problem that will help surely. https://codeforces.net/contest/1330/problem/C

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

    Constructing is so hard for me. I haven't been used to it.And I have to admit that I am too scared to solve it LOL.

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

A very good editorial indeed and how come you guys publish it so fast..?

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

    Secret: I prepare it beforehand :)

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

      Very Good explanation and comments were great at C problem :D Thanks a lot <3

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -161 Vote: I do not like it

      Thanks for ruining ratings with bad problems

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

        You seem to be really asking for trouble, don't ya? Go and watch me on Demon Slayer, you'll learn a thing or two about persistence girl.

        - Inosuke Hashihabara, Demon Slayer Corps.

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

          I saw demon slayer but left after 3 episodes it's boring

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

            You left before my entry, of course, it must have been boring.

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

Bruhhhh, this is magic! Great contest and the fastest editorial ever....

»
5 years ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

In addition:

In problem C we can reduce the time complexity to O(N) by using array int charCount[26]; (due to the small alphabet size) instead of explicit std::sort.

p.s. thanks for the fast editorial.

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

Video Editorials for today's C and D

C

D

Enjoy watching!

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Very nice contest! Problem statements were succinct and the editorial was published so quickly! :)

»
5 years ago, # |
  Vote: I like it -81 Vote: I do not like it

is it rated ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    Yes,

    See the second line of the announcement.

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

    I am just finding your reply's for downvote them xd)):

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I think there is an error in solution C.

It should be return instead of continue;

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

Can anyone think of a counterexample for this solution to E?

Sum up all the red berries and make as many baskets as possible. There are $$$r$$$ (at most $$$k-1$$$) unused.

Sum up all the blue berries and make as many baskets as possible. There are $$$b$$$ (at most $$$k-1$$$) unused.

This is already almost optimal: there are at most $$$2k-2$$$ unused berries. We can get at most $$$1$$$ basket out of these. Said basket only exists under the following conditions:

  • There are at least $$$k$$$ leftover berries.
  • For some shrub, we can take $$$x$$$ red berries and $$$y$$$ blue berries so that $$$x <= r$$$, $$$y <= b$$$, and $$$x + y = k$$$. If the inequalities are not satisfied, we won't be able to make all the complete color-based baskets. Checking this takes an $$$O(nk)$$$ double loop.

This way, we leave as few berries unused as possible.

My code fails on test case 10, and I think it's a problem with the algorithm and not my code. Here's Haskell: 78739086. Here's C++: 78744165

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

    Test:

    2 6
    17 1
    9 3
    

    Your answer : 4

    Correct answer : 5

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

    You are almost correct, but you miss some cases.

    You might have to find more than one shrub, where the red berries add up to x, and the blue ones add up to y. You are only checking the case where it's a single shrub.

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

      But we can take both kind of berries from one shrub only, isn't it or did i not get you correctly ?

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

        You can only put berries from one shrub into a single bucket (if they're of different colors) but you can use multiple buckets.

        For example, in the example above, you can take 5 red, 1 blue from the first shrub, and 3 red 3 blue from the second shrub. The remaining 18 red berries can go into 3 buckets, for a total of 5.

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

          I still dont get it. you aren't using the r and b remaining berries after grouping all the red and blue berries separately.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think it would be nice to comment my approach to E and the way i thought about it.

Lets say we have some vectors in a plane, lets define a modular plane as a plane such that if we are in $$$[x, y]$$$ then $$$0 \le x,y < k$$$, also if the condition doesn't holds then we go to $$$[x\space mod\space k, y\space mod\space k]$$$(a positive modular), we want to see if we are able to choose some of vectors to reach $$$[x, y]$$$ such that $$$x + y < k$$$, starting at $$$[r, c]$$$. Also each vector is labeled with a number $$$i$$$, we cant choose two vectors with the same label, there are $$$n$$$ labels at most.

We know that a vector $$$x$$$ coordinate plus its $$$y$$$ coordinate is equal to $$$k$$$(each vector means how many reds we chose and how many blues we chose from a $$$i$$$th shrub). The problem is not easier, but it can help you understand the logic behind the problem and the solution, at least it helped me. Also if you start from $$$[r, c]$$$, you cant reach $$$[x, y]$$$ such that $$$(x+y) \ne (r+c) _{mod \space k}$$$.

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

    What is r and c and what does x and y represent?

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

      $$$r$$$ is number of reds modul $$$k$$$ and $$$c$$$ is number of blues modul $$$k$$$, $$$[x,y]$$$ is coordinate of a dot or a vector(coordinates of a vector is the coordinates of the endpoint of the vector when its moved to region)

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Woah editorial published very fast! Thanks FieryPhoenix for the contest <3

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I didn't expect C to be that simple. Nice problems!

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain mass increase from x to 2*x part from D ?

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

    There are $$$x$$$ bacteria. If you split none, mass total will increase by $$$x$$$ that night. If you split all, mass total will increase by $$$2x$$$ that night. So, the mass increase will be between $$$x$$$ and $$$2x$$$ inclusive depending on how you split.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Can we prove that it is possible to acquire all the values in the range $$$[x,2x]$$$?

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

    Let's say there's x bacteria of mass m. Total mass: x * m At night, it's mass (single bacteria) becomes m + 1. Now, consider if it split before the mass increase. Now, there are 2 * x bacteria of mass m / 2. At night, the total mass becomes (for one bacteria): m / 2 + 1. The total increase: Final mass - Initial mass: 2 * x * (m / 2 + 1) - x*m = 2 * x. This is only if all x bacteria split. If none split, total increase will be x (as every bacteria mass increases by 1). So, increase will be in the range $$$[x,2x]$$$

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

You make good problems.

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

I like the format giving solution along side with tutorial is really helpful.otherwise sometimes get stuck with tutorials only.

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

It is really great that you prepared editorial 6 days ago && published score distribution day before round. Huge thanks for this! (and problems were good as well too)!

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

I couldn't solve a single question today.
I was totally blank.
But I, cherished the time I used to read each beautiful problem.
And, now this well written editorial and code with comments!
Best contest experience I have had till now !
Kudos to the author for his time and efforts !!

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Could someone please help me understand why the following claim is true for problem E? The author states "Note that if we know that there are j extra red berries, we can also easily calculate how many extra blue berries there are." How would we calculate the number of extra blueberries from the the number of extra redberries?

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

    If there are $$$t$$$ total berries and $$$r$$$ extra red berries, there will be $$$(t-r)$$$ $$$mod$$$ $$$k$$$ extra blue berries. This is because all the other red berries are already filled in some baskets, and if there are many extra blue berries they can fill their own baskets too.

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

I had to give contest on m2.codeforces.com......codeforces was running very slow.

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

In Div2-B, why is no solution possible if there are more than k distinct integers?

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

    if there are more than K distinct integers, then there will be at least two subarrays whose sum will be different and they can't be made equal by inserting any numbers from 1 to n

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

      Suppose, n = 2, k = 1 & array = {1,2} why the answer is -1? According to the statement answer can be m = 2, array = {1,2}.

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

        your answer {1,2} has two subarrays of length 1 , {1},{2} , and their sums are 1 and 2 and since they don't satisfy the condition given in the problem , it is incorrect.

        and since {1,2} can't be made periodic with period 1 , answer will be -1

        below PoIar_ has explained why the answer must be periodic with period k

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

    You want to make an array such that every subarray of length $$$ k $$$ has the same sum.

    Let $$$ s $$$ be the sum of the first $$$ k $$$ elements of array $$$ a $$$. You can tell that $$$ a[k+1] = a[1] $$$ so that the subarray from $$$ 1 $$$ to $$$ k $$$ and the subarray from $$$ 2 $$$ to $$$ k+1 $$$ have the same sum $$$s$$$.

    With the same idea, you can see that the array must have a period of $$$ k $$$. Thus, once you choose the first $$$ k $$$ elements, you can only repeat them. That's why you can have at most $$$ k $$$ distinct numbers.

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

    The period has to be k so you can't put more than k distinct integers in one period.

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

can anyone explain what does max(a1,a2,..,ak) means in problem C ?

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

    The largest lexicographically among the strings $$$a_1, a_2, \ldots, a_k$$$.

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

    The maximum among all these strings a1, a2, ..., ak

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

Author does everything to satisfy participants. Thanks for such a pleasant contest.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it
To minimize the length of sequence $$$a$$$, we will start building our sequence with $$$1,2,…,2^x$$$ such that the total sum $$$s$$$ is less than or equal to $$$n$$$. If the total sum is $$$n$$$, we are done. Otherwise, we insert $$$n−s$$$ into our sequence and sort. This gives a valid sequence of minimal length.

I don't understand this. Is the sequence just $$$1,2,2^2,…,2^x$$$ such that $$$1+2+2^2+...+2^x <= n$$$?

Also, if you can simply insert $$$n-s$$$, then does the case of $$$-1$$$ never arise?

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

    Yes. Because they are the increase in mass. So the sum must be s <= n

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

    You can see that we can just wait without splitting to gain every possible integer.

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

      OK, thanks. Still no idea how someone is supposed to come up with this during the contest.

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

        You don't need to use exactly this approach. You could get intermediate value in various ways.

        First approach
        My approach
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, I will try to understand your approach. By binary descent, I suppose you mean binary search? Or is it different? (Couldn't find anything about binary descent).

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

            Look here https://codeforces.net/blog/entry/76555?#comment-613830

            • And, here is code for "First approach", legit binary: 79004119
            • Similar approach but using fact that lowest the first, highest the most, so you will find lowest on next step very soon: 79006127
            • Completely same but with loops: 79005752 this one should be most understandable.
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Ah... about binary descent... It's called so when you have some tree of decisions and you descent to some leaf. You can represent all outcomes here as tree like that. Why I said binary? Because either you have binary tree or you can do binary search. Sorry, looks like it's my own name of it :(

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

    And impossible case doesn't exist.

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

    I had a bit different approach. If it was possible to split all bacteria, we will split them.Now how to check this, Consider there were K bacteria and W total mass at some stage, if W + 2*K >=n than we can directly reach n in n-W splits. Else if W + 4*K >=n than we can do it using 2 splits minimum and for every other case we split all of them. Link to my submission

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

    Yes, but make $$$x$$$ as big as possible.

    Yes. It is always possible to find a sequence. Easy proof: if you never split your first cell, then after $$$n-1$$$ nights the cell has weight $$$n$$$. (Obviously that is not the shortest sequence)

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

Editorial is good.

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

hey guys .. how did you solve problem A ... look over my solution 78745046 dp Solution lol

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

    My solution:

    Solution

    And code: 78663445

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

      i think this is the optimal solution good job

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it
    cin >> n;
    cout << 2*((1<<(n/2))-1) << '\n';
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      this is very funny solution great job .... i think no one solve it using dp there is much easier solution

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

Judging by the fact that D is rated higher than C despite having a very simple solution with Div2B-ish implementation, (some of) your testers seem to have had similarly over-complicated approaches as me — that makes me feel a little less stupid! Thanks, testers!

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

    Also thanks to Fiery of course, very nice problems!

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

The editorial has been published very fast, just after the contest. Wow!! The problems were cool..........

»
5 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it
 otherwise, we insert n-s into our sequence and sort

what does this mean? how do we know that resultant sequence is even possible?

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

    We have a sequence $$$1, 2, \cdots, 2^x$$$. Note that $$$n-s$$$ does not exceed $$$2^{x+1}$$$. So, inserting $$$n-s$$$ and sorting cannot break the condition: $$$a_i \le a_{i+1} \le 2a_i$$$.

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

B and D were beautiful! :)

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

In the solution of Problem C

if remaining letters aren't the same, we append remaining letters to answer

I don't understand why does it works :(

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

    Consider aaabbbc split into 3. We're gonna put all 3 as into each split, so our remaining string is bbbc.

    Dividing evenly gives ab ab abc which won't work. It's easy to tell that ab ab abc isn't as good as a ab abbc because the only thing we care about is that abbc < abc.

    So we take it to the extreme and throw everything into one, with abbbc as our answer, so that we push that c behind as many lexicographically-lesser characters as possible.

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

someone please explain why one of the test case of DIV.2 b is failing in the codeforces judge while it is running correctly in my local ide the link is:-https://codeforces.net/contest/1348/submission/78736417

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

    Try debugging it using random print statements on codeforces custom test.

    There maybe an initialisation error.

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

First time reading the kind of solution in Div2E. Can someone explain in a possibly detailed manner? I don't get how you can derive the number of extra blue berries from the extra red berries.

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

Nice, E seems to have no testes against n^4 solution//

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

    There are only $$$O(nk)$$$ total reachable states so optimized $$$n^4$$$ solutions are not actually $$$n^4$$$.

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

I knew I was stupid after I saw the solution to B. But the solution to C was a facepalm. And to think, I thought the contest was hard. The questions are excellent and well made; they just require us to get a click....

Just 'a click'

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

Kudos to FieryPhoenix for very interesting problems!

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

FieryPhoenix Problem: 13348B , My_submission:78741637 For the input : 4 2 (n, k), 2 1 1 2 (n distinct number) My output was : 5 (array length), 1 2 1 2 1 (output array). But it shows wrong. Why?

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

    look the given array is 2 1 1 2 but in your output there is no sub-sequence of that array.. there should be sub-sequence as 2 1 1 2 in the output array.. you can't delete anything from the given array..you can just add numbers in between them.. like the given array is 2 1 1 2 the answer could be : 1 2 1 2 1 2 look at the answer array — you can choose a sub-sequence which is the given array (2 1 1 2) . so,your answer must contain the given array as a sub-sequence. I hope you got it.

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

How to think for problem like C . I mean seeing min of max() made me think it is binary search over something. Then I thought it being dp .How do we proceed ahead rejecting this ideas and think of case based solution ?

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

    Put aside ideas that doesn't give any approaches for some time span. You have to have some heuristic how long you may think about idea. Revisit ideas.

    Personaly, it was obvious that each string has to have letters in sorted order. Because, otherwise we could sort them and string would be smaller. Then I stucked for some time. First good observation for me was: let say string s is answer, then if there some string s' in the list for which some prefix is less than prefix of same length of s, then we can reduce length of s moving letters to s'. Carefully thinking about 'when can we do that', brought me to hypothesis that it's possible only when answer is single letter. Carefullly thinking 'why always single letter' (it's not true) and comparing to samples got me to right list of cases.

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

My O(N) greedy passed for E: https://codeforces.net/contest/1348/submission/78740802

My logic was this: The final baskets can be divided into two categories: those that are homogenous (i.e have only red or only blue berries) and those that are heterogenous (i.e can have both red and blue berries). The heterogenous baskets are obviously from the same shrub.

Now, we will run two different greedy solutions. In the first solution, we will prioritise making heterogenous baskets. That is, for each i, add (a[i] + b[i])/k to the answer and then leave the remainder for homogenous baskets. With the remainder, I have just prioritised making homogenous A baskets and then made whatever homogenous B baskets are possible at the end.

In the second solution, we will prioritise making homogenous baskets. That is, add (sum of a[i])/k + (sum of b[i])/k to the final answer. Then, find an i such that min(a[i], remainder of a) + min(b[i], remainder of b) >= k. If you find such an i, add 1 to the answer. Otherwise leave as is.

Finally, take the max from both solutions and output it.

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

    Hacked

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

      I think this should fail too: 78774283

      the testcases don't seem good...

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

        Hacked. Admittedly, making tests for problem E was very hard because random tests were ineffective, so many of the tests were added through stress testing. As you can imagine, it is very hard to stress against every possible greedy...

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

          yes i see, i just hope no one passed system tests with stuff like this: 78775314

          I don't know how complicated it is to find a hack for this one...

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

            Hacked by generating about $$$100,000$$$ random cases with $$$n,k,a,b$$$ in $$$\{1,...,11\}$$$.

            It's really hard to find a counter-example for such multi-greedy solutions. In $$$100,000$$$ random cases, usually only $$$1$$$ or $$$2$$$ that program failed. :(

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

          Yep I understand. Great problems though, thanks for the contest.

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

I used a simpler approach with D,

Observations —

  1. Number of partitions + 1 will always increase each night

  2. so I have to create minimum array possible that sum up to n, which is in increasing order and each element is less than it's max possible at that point which is simple as 2^i as ith night (0 indexed)

  3. now keep maximum possible element fulfilling those condition.

  4. and for actual solution number of partitions each night just take adjacent difference between elements.

My sol — 78714792

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

    Hey! Can you please explain this part (if condition) in your code?

    lf = df-x
    if lf<x:
       ans.append(df//2)
       df -= df//2
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is the case when we will select maximum possible value for that position i(value = 1<<i) but the next value will be less than that so we equally divide remaining difference between last and second last term

      example n = 9 -> ans = [1, 2, 3, 3] , sol = [1, 1, 0]

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

I am unable to understand div2 C .Can anybody explain it. Thanks in Advance

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

Hello!. Can someone tell me why this solution is wrong for E. It fails on test 73

I commented the code so is easy to understand.

What I am trying to do is a dp(i, r) = {maximun number of full_boxes from i to n-1, maximum number of unused blue berries}.

So in each state I try all possible values from [0, k-1] of red berries that I want not to merge with the same shrub (then this one will be merged with r).

At the end the answer should be dp[0][0].first + dp[0][0].second / k

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

Can anyone please explain why the greedy strategy mentioned in problem D works(i.e to take summation till 2powerx and repeat same for n-s) by working I mean proof that it is optimal

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

There is a typo in problem D. The complexity should be O(nlogn).

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

    $$$n \log n$$$? $$$n$$$ goes up to $$$10^9$$$.

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

      Oh, I didn't read carefully, and thought n is the length of inc. Since the length of inc is O(logn), the complexity is O(lognlog(logn))?

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

        If you sort using insertion (since we are only adding at most one number), the complexity is still $$$O(logn)$$$ I believe.

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

          I see. Insertion here means insertion sort. Thanks for clarification.

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

            insertion sort isn't nlogn for array of n size? logn(log(logn)) isn't right why?

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

              Insertion sort has complexity O(N^2) in general. But here we construct a sorted array in O(N) and insert (at most) one more value at the end. A single insertion operation is O(N) with respect to the size of the array. And since the size of the array is O(log(N)) with respect to the original n from problem statement, so is the time complexity.

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

                In the solution given we are using sort(inc.begin(),inc.end()) and this sort uses quick sort right? quick sort takes nlogn for size n, so our array length is log(N);

                so time complex -> log(N)*log(log(N))

                isn't this right??

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

                  Sorry, I did not read the code, only the tutorial text.

                  Yes, you are right: if we use the STL function, then that is the right complexity. And if we use insertion, as suggested in the tutorial (but not implemented in the code), then the complexity is linear. These are 2 independent statements, not conflicting with each other.

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

For problem E, What is the memoisation approach, if any?

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

    This is my solution 78781631, pretty much the same as the editorial solution except it's memoisation. Be aware this approach TLE'd for me, so I had to optimize a bit.

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

    My solution is a bit different than the one explained in the official editorial.

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

      can you explain why there is no need of memoising the variable 'g' in your code in the dp array?

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

        Explanation

        For a given value of x and r, the value of g will always come out to be same.

        In other words:

        If we know the number of red berries that are being passed on to the X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.

        Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub — Number of red berries R passed onto (X + 1)th shrub) % K

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

          I think your codes complexity is O(NK), am I correct? btw thanx for the response, it helped a lot!

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

My submission for problem B is always wa,I'm really disappointed,can anyone help me?https://paste.ubuntu.com/p/9Xftz94CM7/

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

Why does D have a binary search tag, is there a way to solve this using binary search? Anyone?

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

    Here is a link to my submission: 78773066 I have solved it using binary search.

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

      Awesome technique!

      I think sum = [N+S, N+2*S], should rather be sum = [N+S, 2*N+S] .

      Thanks a lot though!

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

        Assume a state, of sum 3 and no of bacteria 2, then we can can reach the states which have sum in the range [5-7], i.e, [3+2, 3+2*2]

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

          That's right, tho you have written 2*sum rather than 2*no. of bacteria. Was just mentioning to correct it :)

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

            Whoops! apologies for overlooking it twice!! Thanks

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

      This uses the same principle but I am finding the value greedily. Although I have to mention that during contest it would require more thought.

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

It was a nice set of problems! However, I think that the time limit for problem E was too strict. I understand that a O(nk^2) recursive solution may not be fast enough, but I saw some iterative O(nk^2) solutions getting TLE (including mine).

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

    Yes, I also got TLE on test 33. When I try to use as least as 'long long' as possible, I got AC

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

No offence to problem authors problems were quite elegant but in general I have observed too many constructive algorithm based problem these days. Why the problem setters are focusing on it so much is there any specific reason to include lots of constructive problems in the contest. Or constructive problems are intutive to be prepared. or some other reason exists for this please share your thoughts

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

    No offense taken :) . I am not sure about other problem setters but personally, I did not specifically intend to have many constructive problems. But, the problems in my round covered a diverse range of topics: strings, math, dp and more. The constructive part just happened to come with the problems.

    I think constructive algorithms are very closely associated with logical thinking, so learning to solve them increases your problem solving skills. Personally, I quite like constructive problems because they allow you to be more creative (for the most part).

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

      yeah I agree with you problems were really amazing. Even B was very elegant though I solved it too late. But I liked solving B.now I am upsolving other problems.

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

How we can solve to minimize the length of beautiful array (problem B) if we want to. (In the question ,it was told that we don't need to minimize the length).

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The solution for 1348C — Pheonix and Distribution will fail for the case where k = n. This is because there is no check for n == k in the part below.

if (s[k]!=s[n-1]){
    for (int i=k;i<n;i++)
      cout<<s[i];
}

This will result in out of bounds error/segmentation fault.

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

Problem E: Has tag greedy. First line in tutorial: No Obvious Greedy Solution. Is it that complex to implement greedy in it?

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

    There shouldn't be any greedy solutions since the special case where the first shrub has only $$$x$$$ red berries, the second shrub has only $$$K-x$$$ blue berries, and the remaining shrubs have exactly $$$K$$$ berries (of either color) is a knapsack variant.

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

    The greedy tag might be because some ppl might have used a greedy observation to optimize their DP solution.

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

A different approach for D (binary search):

Claim: If answer is 'd' then you can always find the answer by splitting all bateria till d — 3 days, then on d-2, d-1 you split only m, k bacteria. One can find m, k using binary search. Here is the proof:

(for image 1: note 1st row represent no. of day, 2nd row represents what is the mass after that night night in case all bacterias have been splitted before, 3rd row represent no. of bacteria available to be splitted for next day.) page 1 page 2 page 3

Here is my submission (Had to upsolve, because in the contest I got confused with the proof for the whole time). Time complexity is O(log(n)) per test case. FieryPhoenix what do you think about this approach.

Obviously the editorial solution is much more creative and definitely elegant :). (but I was nowhere near thinking like that).

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

    You can find $$$m$$$ and $$$k$$$ in constant time too.

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

Can some one please help me figure out what is wrong with my solution of 1348B? would be great help thanks https://codeforces.net/contest/1348/submission/78743946

Test: #4, time: 234 ms., memory: 160 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER

Checker Log

wrong answer Integer element b[199] equals to -1, violates the range [1, 18] (test case 8)

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

Like the idea of problem B. (maybe the hardest B problem I have ever met in a div2 conteset)

Thanks for such a high quality contest and the fast turorial! :)

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

Great solution of problem F!!!

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Problem B was the cutest.

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

Share a Solution in $$$O(nk)$$$ of problem E.

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

    Could you explain how does it work?

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

      First if we pick r red berries and b blue berries from a shrub and use them to fill exactly i baskets ($$$(r+b)MODk=0$$$).

      Then if $$$r \geq k$$$ or $$$b \geq k$$$,we can pick k red berries or k blue berries just because they are the same color.So we just need to pick r red and b blue from the same bushes and use them to fill one basket $$$((r+b)=k)$$$.And others can be picked just because they are the same color.

      dp[i][j] means considering the first i shrubs if we can pick x red berries (x%k=j) ,y blue berries to fill exactly some baskets((y+x)%k=0).

      we can use dp[i][j] to update dp[i+1][c] as follow:

      • If we pick no berries from the $$$(i+1)_{th}$$$ shrub,then dp[i+1][j]=dp[i][j]

      • else we must pick exactly k berries from the $$$(i+1)_{th}$$$ shrub.Let's suppose we pick "a" red and "k-a" blue.The following condition must be satisfied :

      1. 0<a<k
      2. a<=a[i+1]
      3. k-a<=b[i+1]

      You can easily find that ,the possible "a"s form an array:[max(1,k-b[i+1]),min(k-1,a[i+1])],in the other words dp[i+1][(j+c)%k](c is in the array) |=dp[i][j].

      You can used some ways to achieve it in O(1).Like this :

      for an array a[1]...a[n] you want to make a[l]...a[r] both increased by 1.You can do as follow:

      a[l]++;

      a[r+1]--;

      After all the process.Set a[i]=a[i]+a[i-1] for all i (from 2 to n).

      Final answer can be worked out according to the dp[n][i].

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

For A we can see a pattern:2->2, 4-> 2+4, 6->2+4+8... So answer is pow(2,n/2+1)-2

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

Problems were good. still i was not able to solve even 2 problems.

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

Nice Contest and Editorial. Thanks Phoenix!

But could someone please help me out with E. I can't really understand what is "_leaving extra berries_" in the editorial? :p

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In problem F there is another way to find which friends to swap. When we construct answer greedily for friend i we always take interval with minimal b. So what are intervals with which we can swap i? There is only one possible interval. Interval with second minimal b (if exists). submission

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Nice and simple explanation. Thanks!!

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

In problem F, why do greedy algorithm for an arbitrary valid ordering work?

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

    First we should place friend 1 to somewhere, valid intervals have form [1; x]. Imagine we don't chose one with minimal x, then we should use that interval in future, but then we can swap those two intervals, so solution with using minimal x always exists. For placing friend 2 we can think of intervals with form [1; x] as [2; x] and don't lose anything, and so on. Sorry English.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain the O(nk) solution for E ?

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

Can anyone explain me the binary search solution for Problem-D ???

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

can anyone explain me why my solution got TLE for 2nd question though i printed n*k which is less than 10^4 letters output.My submission:78696875

»
5 years ago, # |
  Vote: I like it +57 Vote: I do not like it

More solutions for F:

(When I refer to the "length" of an interval below, I mean the number of unmatched points on it)

First, any interval of length one can be matched greedily. This reduces the problem size by one. Repeating this until no more intervals of length one are left is actually pretty tricky to implement efficiently. Here are two ways:

  1. On every interval, keep two "sentries" at uniformly random distinct positions. This is impossible once the interval has length one, in which case we add it to a queue of length-one intervals. When we find an interval of length one, we match it and shrink all intervals containing that position. This may require relocating "sentries" at this position, which can be done in $$$O(log{n})$$$ per sentry using a Fenwick tree. Since each sentry is expected to have $$$O(\log{n})$$$ relocations, this solution has an expected runtime of $$$O(n\log^2{n})$$$.

  2. For each interval, we store it in a bucket based on the leftmost point it contains that hasn't been matched. We sweep from left to right and match length-one intervals we find. We only need to check the interval in the bucket whose right endpoint is closest. If we do find a length-one interval, all other intervals in the bucket get merged into the next bucket. We also need to take a step backward because a new length-one interval may have been created. We can store the unmatched points in a doubly-linked list to do this efficiently. This solution is $$$O(n\log^2{n})$$$ if buckets are merged small-to-large, or $$$O(n\log{n})$$$ if join-based trees or meldable heaps are used.

Now all intervals have length at least two. Suppose there are at least two valid orderings.

  1. Observe if the greedy algorithm for finding a solution ever has two active intervals with the same right endpoint, taking either will be optimal, so we will get two different solutions. It turns out this must happen if all intervals have length at least two.

  2. There must always be two adjacent (by ID) points such that swapping their intervals creates another solution.

Code:

  1. 78842146

  2. 78842436

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the following approach to D problem ? pigbrain's solution

this one gives a different answer for the test cases. Thank you.

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

For F problem another greedy initial matching is following: Sort by $$$b_i$$$ in increasing order. Within groups of same $$$b_i$$$ sort by $$$a_i$$$ in increasing order. Now, iterate over this order and for interval $$$i$$$ pick smallest not used value in the interval. I don't know how to prove it shortly. So, perhaps it's wrong.

During this iteration, let say smallest not matched value is $$$v$$$. If you also check for any used values (matched) within interval $$$(a_i, v)$$$ that can be also matched with $$$v$$$ -> this is solution. this pair is exactly what values you may swap. You do this check with segment tree.

Or, at least, it passed tests: 78850901 (code is ugly, just for hacks)

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

can someone for problem E explain how this TC's correct answer is 4? 4 8 11 5 1 4 1 4 1 6

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

For E, doesn't O(nk^2) time out? Or can CodeForces computers handle ~1.25*10^9 operations in 2 seconds? I thought that modern computers can only handle at most 10^7 ish operations a second. This was my first contest so I'm not really familiar with the website. :P

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

    O(nk^2) is not around 1e9, it's something like 1e8 and well to be honest it's a bit around the edge for 2 seconds, but generally when you see 500, just remember you can usually run it in n^3 if you code tidily.

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

      Oh lol, just realized it's 1e8 can't count. Thanks for the advice though.

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

    Have you ever heard about CPU clock speed? It's measured in Hz. Hertz — is basically something in second. It can be anything. But regarding to clock speed, it is cycles per second.

    CPU perform single operation in several cycles, and at the same time, several operations during same cycle. Because of parallelism. It's not that kind of parallelism everyone talking about most of the time, like multiple cores / threads. It's other parallelism: processor split operations into micro operations... In short, all I want to say, that you can't tell time spent on operation. Modern CPUs are very complex.

    Instead, lets say in optimistic maner CPU perform single operation in single cycle. This means if CPU is 3GHz, then it does $$$3*10^9$$$ operations per second. I said it's optimistic, but it can be wrong, just because number 1 cycle per operation is arbitrary chosen. You could say 0.5 cycles for operation, it's twice faster. But anyway, it's good approximation of order of magnitude. It's not $$$10^7$$$ or $$$10^8$$$. It's around $$$10^9$$$ because of GHz. Note that some operations are slow, like: sqrt, sin, cos... So, it doesn't work for them the same.

    In short, thinking about second as approximately $$$10^9$$$ operations is enough. You can verify by running code. Just keep in mind that compiller can throw off any code that it may predict result, or if result is not used. So, at least print result of computation, and don't make super simple computations.

    • It's applied to native binaries like produced by C++, C, Pascal, Go, Rust...
    • C#, Java — a bit slower, because they use Virtual Machine
    • pypy is even slower (as far as I remember $$$10^7$$$)
    • python is around (as far as I remember $$$10^6$$$)
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! I didn't know about that before. CodeForces doesn't give extra time to Java, right? Do you know the Hz of the CPU for CodeForces?

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

        I don't know. It doesn't add for python and pypy for sure.

»
5 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Given that the feedback on this tutorial is high, I don't really care if I get negatives for my message. Honestly, the tutorial for E is just terrible. There are many claims without a single proof.

I didn't understand the tutorial after reading it for two hours though I got some clue. I tried to implement the same thing as described in the solution to see what's going on. If you change the condition from $$$(a_i - l)~mod~k + b_i$$$ to $$$(a_i - l)~mod~k + b_i~mod~k$$$, you'll get a wrong answer.

Where that condition comes from? Why do we need to take the $$$mod$$$ of $$$a_i - l$$$ but not of $$$b_i$$$?

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

    Insulting my explanation wasn't called for, please consider asking nicely in the future.

    Nevertheless, your question is valid so I will try my best to explain.

    Why we don't mod $$$b_i$$$:

    Consider the case:

    2 3
    0 2
    2 3
    

    The optimal solution will have one basket contain $$$2$$$ blue berries from the first shrub and $$$1$$$ blue berry from the second shrub, and the second basket will contain $$$3$$$ of the remaining berries from the second shrub.

    After processing the first shrub, only $$$dp[1][0]$$$ will be true. When transitioning to the second shrub, one optimal solution leaves $$$0$$$ extra red berries and groups the $$$2$$$ red berries in the second shrub with a blue berry. So, we want to check if $$$l=0$$$ is possible for $$$i=2$$$. A correct solution would return true.

    Look at the condition. $$$(2-0)$$$ $$$mod$$$ $$$3$$$ $$$+3$$$ is greater than or equal to $$$3$$$, but $$$(2-0)$$$ $$$mod$$$ $$$3$$$ $$$+(3$$$ $$$mod$$$ $$$3$$$ $$$)$$$ is not. Why? Because for $$$l=0$$$ we can actually group the $$$2$$$ remaining red berries with a blue berry when $$$(b_i \ge 1)$$$, but after modding it doesn't work.

    Why we mod $$$a_i - l$$$:

    Consider the case:

    2 3
    0 2
    4 0
    

    If we don't mod $$$a_i-l$$$, solution will print $$$2$$$. Why? Because for the second shrub it will say it is allowed for $$$l=0$$$ when it obviously doesn't work. The $$$4$$$ red berries cannot be grouped with blue berries to make some number of full baskets. After leaving $$$l$$$ berries for valid $$$l$$$, all the remaining red berries must be put away.

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

      hi, excuse me, could you please answer my question too? thank you in advance :)

      for problem E explain how this TC's correct answer is 4? i can only see 3.....

      4 8

      11 5

      1 4

      1 4

      1 6

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

        x c y means take x berries of color c from basket y 1. (6 b 4, 2 b 3) 2. (2 b 3, 4 b 2, 2 b 1) 3. (1 r 4, 1 r 3, 1 r 2, 5 r 1) 4. (6 r 1, 2 b 1)

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

    Here's another way of thinking about E:

    Suppose we know the number of red berries in heterogeneous baskets modulo $$$k$$$. This determines the number of blue berries in heterogeneous baskets modulo $$$k$$$. Since the number of red berries in homogeneous baskets is a multiple of $$$k$$$, it also determines the number of red berries not in any baskets (we can safely assume this to be less than $$$k$$$ since otherwise we can form another basket). Similarly, we can determine the number of blue berries not in any basket, and thus deduce the number of baskets.

    To compute the possible numbers of red berries in heterogeneous baskets modulo $$$k$$$, it suffices to look at each shrub separately and determine the possible numbers of red berries modulo $$$k$$$ in heterogeneous baskets for that shrub. If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous. Now we have two cases. If there are no heterogeneous baskets, the number of red berries in those baskets is obviously zero. If there is one heterogeneous basket, let $$$x$$$ be the number of red berries in it and $$$k-x$$$ be the number of blue berries in it. Clearly, $$$0\leq x\leq a_i$$$ and $$$0\leq k-x\leq b_i$$$. Rearranging, we get $$$\max(0,k-b_i)\leq x\leq \min(a_i,k)$$$. These correspond to the transitions for our DP.

    Code: 78841831

    Bonus: This implementation is actually $$$O(nk+k^2)$$$. (Hint: consider the maximum consecutive sequence of trues in each row).

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

      "If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous."

      Thank you.

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

Since some time now, i am seeing a strange pattern in some of cf questions. strangely tough ad hoc which seems just too forced. logics which appear to have been put just to make a question tough more than interesting and learning based . of course some problems are really beautiful and you get to learn, but many like this contest's D are straight out from the first category i mentioned. ofc i may be wrong, just wanted to voice my view.

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

in problem D, if n=13 output is 1,2,2 but if we follow this approach ,then it goes as, 1->3->7->11 could someone explain it to me? Thx in advance.

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

    your sequence is right upto 7 that is 1 -> 3 -> 7

    • but after that only two of them broken down to 4 and you only increased those 4 by 1
    • You should also increase those bacterium which do not have broken down, so the left 2 bacterium will also get increased by 2 hence total increase will be 6, thus after 7 , 7 + 6 = 13 will come

    if you still have doubt feel free to ask

»
5 years ago, # |
Rev. 8   Vote: I like it +10 Vote: I do not like it

My solution for Problem "E. Phoenix and Berries" 78860291

Let, DP[X][R]= Number of baskets that can be completely filled using the shrubs indexed from X to N — 1 (0 based indexing), given that we have R number of red berries to start with.

Note that for every shrub, if:-

  • the total number of berries a[X] + b[X] (both red and blue) in a shrub is greater than or equal to K,

  • and there are both red and blue berries in the shrub.

Then, we'll fill one basket completely, with these K berries and pass on the remaining berries to the next shrub. There can be at most K - 1 different ways in which we fill a basket containing both red and blue berries from the same shrub.

For example if the Xth shrub contains 2 red berries and 10 blue berries and K = 4, then the possible combinations are:-

RED    BLUE
1      3
2      2

(All the combinations with either zero red berries or zero blue berries will be taken care of in the last part)

Whenever, the count of any of these passed on red and blue berries becomes greater than or equal to K, we immediately fill a basket with it and pass on the remaining (R % K, B % K) berries to the next shrub.

Important observation:

It can be observed that if we know the number of red berries that are being passed on to the X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.

Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrubNumber of red berries R passed onto (X + 1)th shrub) % K

If we receive R red berries and B blue berries from the Xth shrub (passed onto the X + 1th shrub), and the total number of berries in the X + 1th shrub is greater than or equal to K, i.e., a[X] + b[X] >= K, then we fill exactly 1 basket with these K berries. After selecting a total of K berries (all possible different combinations of red and blue), from X + 1th shrub, we'll add the remaining red and blue berries to R and B and find mod K.

The number of red berries R and blue berries B is always stored as R % K and B % K, because if we have at least K red berries or/and K blue berries, we can completely fill (R / K) + (B / K) baskets.

Another Case

If the number of berries in a shrub is less than K, then we cannot fill a basket completely, using berries, entirely from this particular shrub, therefore we'll have to add the number of red and blue berries in this shrub to R and B respectively, fill R / K and B / K baskets completely, and pass on R % K and B % K red and blue berries respectively, to the next shrub.

We solve the above case even when a[X] + b[X] >= K, to consider the combination :-

RED   BLUE
0     K
K     0

and pass on the remaining red and blue berries to the next shrub. :)

We have to find DP[0][0]

long long dp(int x, int r, int g)  // r red berries and g blue berries
{
	if(x == n)    //terminating condition
		return 0;
	if(DP[x][r] != -1)    //value already found before
		return DP[x][r];
	DP[x][r] = 0;
	int rem_r, rem_g;
	if(a[x] + b[x] >= k)
	{
                // considering all possible combinations of red and blue berries to completely fill a basket
		for(int i = 1; i < min(a[x] + 1, k); i++)
		{
			if(i <= a[x] && (k - i) <= b[x])
			{
				rem_r = r + a[x] - i;
				rem_g = g + b[x] - (k - i);
				DP[x][r] = max(DP[x][r], 1 + (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k)); 
			}
		}
	}
        // passing onto the next shrub, the total red and blue berries from this shrub along with the previous red and blue berries passed onto this shrub
	rem_r = r + a[x];
	rem_g = g + b[x];
	DP[x][r] = max(DP[x][r], (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k));
	return DP[x][r];
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    your explanation is good but one point i am missing is you said that if in a shrub a[x]+b[x]>=k then we will fill one basket from it and pass the remaining to next shrub , why? why can't i fill more than one basket from the same shrub(of type in which basket is filled with red and blue berries) if i have the chance , why i am filling only 1 basket and passing to next shrub?

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

I really apreciate your editorial and your effort! If you don't mind, i'm still having some troubles with problem E, it's a little bit hard to digest these operations. I've read carefully the editorial and all the comments and i'm still having troubles with these parts of the code :

"if ((a[i]-k)%K+b[i]>=K) dp[i][j]|=dp[i-1][(j-k+K)%K]; (especially the dp[i — 1][(j — k + k) % k] part)"

dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];

If somebody can give me an explanation with some examples i would be really grateful.

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

    I rewrote some of the variables in the code. Sorry for making it confusing with $$$k$$$ and $$$K$$$.

    Essentially, once we determine we can leave $$$l$$$ extra red berries from the $$$i$$$-th shrub, we also have to check whether the state from the previous layer that we want to transition from is true. For some $$$l$$$, if we want to see if we can achieve $$$dp[i][j]$$$, we have to check if $$$dp[i-1][j-l]$$$ is true. But, $$$j-l$$$ might be negative, and since we only care about the value modulo $$$k$$$, we force it to be positive by adding $$$k$$$ then modding.

    The second line of the code corresponds to leaving $$$a[i]$$$ modulo $$$k$$$ berries. We can always achieve this by creating full baskets containing only red berries until there aren't enough. The logic of transitioning from the previous dp layer is the same as I described above.

    Hope this makes sense!

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

      why is it not possible to leave l red berries if (a[i]-l)%k + b[i] < k. Wouldn't it be possible to combine the (a[i]-l) % k red berries with the j-l red berries already there ?

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

How is time limit handled on codeforces? Mu solution for problem C had T*N complexity, while solution in editorial had T*N*logN which would not make it in 2 seconds for big enough test set (for example if input would 900 test with string of length 10000 + 100 tests for edge cases). I saw such solution in room, but wasn't quick enough to hack it (with program that would generate 1000 * 10000 test set) and it passed (even though I'm pretty sure that it would take more than 2 seconds). So my question is: is time limit in problem for 1 test, or complete test set? And to add: are there some limitations for hacking (for example time limit for program that is generating input, or number of characters for directly passing input)? Thanks.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Detail explanation for div2 C if anyone need here

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

My solution for the problem E is greedy and it gave me accepted. To know how it works you can go to this blog: https://codeforces.net/blog/entry/76862

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The matching is unique iff contracting the edges (merging nodes connected by edges from our perfect matching into one node) in the perfect matching creates a DAG.

Can you please explain why this is true (or give an appropriate theorem/lemma name)?

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

    Thanks for asking, I added the following explanation to the editorial:

    Consider a simpler graph, with only nodes representing positions. We draw a directed edge from node $$$i$$$ to node $$$j$$$ if the friend currently assigned at position $$$i$$$ (from our greedy) can also be assigned to position $$$j$$$. So, if there exists any cycle, we can shift the friends around the cycle to create another valid ordering. If the perfect matching is unique, our graph has to be a DAG.

    Now, returning back to the bipartite graph, we see that it is essentially the same. By contracting edges, all position nodes are equivalent to the friend node that is assigned to them (from the greedy). So, following an edge from the left side (position) to the right side (friend) puts us back on the left side (position), and this graph corresponds to the simpler version I explained above.

    Please let me know if anything is still unclear.

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

can someone please explain o(nk) soln for Phoenix and Berries??

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

    Consider solution $$$2$$$ from the editorial. It is clear that valid $$$l$$$ form a contiguous interval, so we can apply prefix sums on each layer to quickly query whether there exists a "true" in some interval.

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

    Some of comments describe it enough, but I'll try to do my best.

    Horrible wall of text
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I had idea to use only k/x of those with range starting with x. It would be $$$O(n+k^2log(k))$$$ if it work. 79024430 It passed tests but obviously it's wrong so I hacked it.

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

      Looks like I'm finally made legit solution for 1348E - Феникс и ягода in $$$O(n + k^2)$$$ time and $$$O(k)$$$ memory. Just for fun I was trying to find solution where n can be bigger, and looks I did it. Code: 79055234

      Idea of optimization is pretty simple, we want fast check is shrub useful or not. What do I mean by useful? Well, if processing of it does something, then it is useful. Now, just from definition of does something it means that after processing shrub we have more possible remainders. So, task is: determine fast will it increase. We don't care at all how much. So we can ask opposite: when is it useless? Yet again, say "problem is tough, we need something simpler". When it doesn't change if range is exactly one value? (in other words, if we can fill shrub-basket only in single way). If nothing changed, it means that infinite concatenation of our array of booleans after shift by number of red berries picked did overlap completely, and maybe better for understading: their bitwise OR looks same as initial infinite array. This means that it's shift by whole number of periods of our infinite boolean array. And you may find it in linear time. Back to "tough version". We have range of shifts then. So, we need to find is there any value among those shifts that is not whole number of periods of our infinite array. It's done in constant time. So, in the end, we process only those shrubs which will increase number of possible remainders, and in worst case we increase from 0 to k one by one which is k times. Each processing still takes $$$O(k)$$$ so in total with reading of shrubs becomes $$$O(n+k^2)$$$. (:

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

"we do not care about how many extra blue berries we leave because that is uniquely determined by the number of extra red berries." I am not able to get this line from question E, can anyone explain it?

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

Is there any Testcase for problem D. Pheonix and Science when the answer will be -1 ? If yes, please share.

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

    Answer can never be -1.Because every possible n is reachable, just don't split the bacteria on any day and it will keep on increasing 1,2,3,4.....

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

Thanks FieryPhoenix for the editorial,

but one thing I don't understand in problem E(Phoenix and Berries) is that according to the editorial we are trying to leave extra l red berries from a[i], and extra means it is not placed in a full basket.

my question is: should not l be <= j ?

because as I see in the solution code that if l > j we are merging some of the l berries with red berries from the i-1 shrubs to maintain j extra berries, and this means that not all l red berries are extra

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

    $$$l$$$ does not have to $$$\le j$$$. When we leave $$$l$$$ extra red berries from shrub $$$i$$$, we merge them with extra red berries from shrub $$$i-1$$$. At this point, if the total number of extra red berries is $$$\ge k$$$, some of the extra red berries may no longer be extra and will form their own basket. So, you can think about those berries being extra temporarily.

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

I am new to C++, can someone please tell me what does int b:s do? P.S. I read about sets, just can't understand that line

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

    Search up "foreach loop C++" on Google. Basically, it is an easy way to iterate over a container (such as set or vector for example).

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

The editorial for D is exquisite, but it is also very confusing, and the editorial must be easy to understand it doesn't matter if it is elegant or not.

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

Thanks for the tutorial!
There seem to be a little mistake in the first solution for F: "a friend $$$i$$$ such that there also exists some friend $$$j$$$ such that $$$a_{p_j} ≤ p_i < p_j ≤ b_{p_i}$$$".
I guess the correct expression should be as follows: $$$a_{p_j} ≤ i < j ≤ b_{p_i}$$$.

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

FieryPhoenix Can you please explain how (t-j)/k gives the total number of completely filled baskets as we are not subtracting extra blueberries?

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

Another/Easier Approach for Problem C

During the contest , I found it was tougher to come up with the correct approach. So instead this is a brute force solution... (0-based index)

  1. We check if the smallest letter has <k occurences, then simply print the [k-1]th character.

  2. If thats not the case,

    We have only 2 Possible Options:

    -> Either to fill all A[i] strings with the smallest letter, then append all the remaining characters (s[k......n-1]) to any a[i]. (preferably a[0]).

    ->Or to simply distribute all the characters evenly in k strings.

Now we make 2 arrays , and store the result of both options. Sort both. Then simply print the Minimum, of the Maximums of both Arrays!

CODE!

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

can anyone help me in my code.Here is my submission 158595810 1348B - Phoenix and Beauty Instead of inserting the element in array a i have printed them directly

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

I was trying to solve Problem C using customized set but using erase function on customized set giving TLE, I am unable to find the reason, if anyone knows solution please help, thanks in advance.

my code : https://codeforces.net/contest/1348/submission/257644894