Sooke's blog

By Sooke, 6 months ago, In English

1337A - Ichihime and Triangle

Idea: Sooke

Tutorial
Solution by Sooke

1337B - Kana and Dragon Quest game

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander

1336A - Linova and Kingdom

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander

1336B - Xenia and Colorful Gems

Idea: ustze & isaf27

Tutorial
Solution by Sooke

1336C - Kaavi and Magic Spell

Idea: EternalAlexander

Tutorial
Solution by ouuan

1336D - Yui and Mahjong Set

Idea: Sooke

Tutorial
Solution by Sooke
Solution by PinkRabbit

1336E1 - Chiori and Doll Picking (easy version) and 1336E2 - Chiori and Doll Picking (hard version)

Idea: Sooke

Tutorial
Solution by Sooke
Bonus

1336F - Journey

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander
 
 
 
 
  • Vote: I like it
  • +257
  • Vote: I do not like it

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

Fun fact: 1336A - Linova and Kingdom and 1336C - Kaavi and Magic Spell were prepared for Codeforces Round #564 (Div. 1) but unused for some reason.

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

    For problem 1336A — Linova and Kingdom

    My approach is to do dfs and then sort the nodes is decreasing order wrt size of sub tree. If two nodes has same sub tree size, then we will pick the node with smallest depth first.

    Can you please tell me, why this approach is wrong.

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

    For problem 1337E — Kaavi and Magic Spell

    My approach is to use dp with 3 dimensions, for every character I put in A, I am calculating no. of substrings it is forming.

    Initial state: dp[0][i][i] = 2 (if S[0] == T[i])

    My state transition: dp[i][st][end] = Summation of (dp[i-1][st+1][end]) if S[i] == T[st] Where st runs from 0 till T.length and end starts from st.

    And my submission is here https://codeforces.com/contest/1337/submission/77231262

    My solution is failing at 7th test case, could you please let me know if the approach is correct and where I am going wrong?

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

This round has given me confidence.Thanks to the author and the examiners!

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

Is there Chinese solution?

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

Thanks problem-setters for the editorial. I will try to solve C next time

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

will there be any dp solution for 635 div2 'C'?If yes, Please explain.

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

    I think you can do it by something like $$$dp_{i,j}$$$ -> the answer when $$$j$$$ nodes chosen in the subtree of $$$i$$$. But the complexity will be $$$O(nk)$$$. And you can use the alien trick to optimize it to $$$O(n\log k)$$$ or sth, but it seems very stupid.

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

    Isn't counting how many nodes are there that are under a node u and connected with you is DP. Like this? 76935092

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

      This was greedy approach,i think so.

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

        I think greedy was the last step where I used priority_queue. Maybe I am wrong. I face problems with dp and greedy.

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

          In this problem, if you have used the fact that you have to color all nodes of subtree of ith node (except the ith node) before coloring the ith node, then you have used a greedy approach.

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

    manan_shah, probably you can contribute to this.

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

      actually my solution is the same as the editorial. 76863601
      The cnt is maintaining the no. of nodes in the subtree of a node including that node. Our approach would be to select the leaves, but if the value of k is greater than that, then we need to select other nodes that are at levels above the leaves and contribute to happiness.
      A crucial observation is that when a node is selected, it would decrease the happiness of all the other which are in the subtree. And as we have selected the nodes in the subtree already, the happiness would increase by the depth(level)-nodes in subree.
      So we sort the array of level-no. in subtree and select the largest k.

      I noticed that I could have computed level by dfs also as presented in the editorial. I had the bfs approach in mind first and then I noticed that it isn't the only thing so I had to use dfs.

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

        I dont understand what you said tha "and as we have selected the nodes in the subtree already, the happiness would increase by the depthe nodes in subtree" please can you explain again..

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

          our main idea is to select the leaves but now if we have more to select, we will pick one level above the leaves. So, which ones should we pick? We pick the ones having maximum happiness. Now if we pick one,we know that it will add happiness by the level of that node, but as we have picked all in its subtree before its picking,we need to subtract the number of nodes in its subtree as while travelling up, the current node won't count.
          so, finally we just sort all the values(level-no. in subtree)(net happiness which every node would provide)
          Hope this helped.

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

        What's the use of level[0]=-1000000; in your code?

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

    Video editorial of 635-Div2-C

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

I have prepared video editorials, check them out for more insight about the problems.

Div2C/Div1A

Div2D/Div1B

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

is the note of div 2 E right?

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

    ok i got it i didnt read the input the first string taken is S not t

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

Div2 C and Div2 D were great problems. Thanks to the authors of the round!

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

    It could be greater if the authors didn't gave the case 1 1 1 1 1 1000000000 in the sample. Then, a lot of people like us would have assume ans = 1e18 first instead of 9e18. And would have got WA and do debugging. Anyway, C and D was nice. Learned a lot solving these.

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

    Problem C was harder than Problem D for me. :(

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

      it's easier, in D u've used approach from editorial?

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

Thank you for funny legends!!!

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

Can someone please explain to me why Div.2 C got wrong answer on test 6? https://ideone.com/EhLzvj. My idea is that I create a vector from 1 to all the leaves. I then create another copy of it and increase the sum by the difference between each of the vectors. Can anybody help me and tell me how to get it to be accepted?

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

    Well, it is simply wrong logic.

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

      Thank you for your help. I have just understood why it doesn't work.

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

    Why am I getting all these downvotes? I just asked a question about a problem that I thought about incorrectly! What is wrong? Do you just see a downvote and say I will go with the flow or what?

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

      Maybe Div.2 C seems too easy.And your idea is totally wrong that seems like you are fake.

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

        Wait what? What do you mean I am fake? A robot or something? I honestly don’t get it. I am just a kid in college who is currently a trainee at ACM and who is definitely passionate for competitive programming. What is wrong with you!

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

          There is an another reason.If you usually chat in codeforces,you will find that the people whose rating is high hardly gets downvotes.But I exactly don't care about thing.

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

            What do u mean ?!?!? He just asked a q.U don't wanna answer just scroll down.

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

          dude just dont listen to him , he is just another blockhead who had been struggling in his life, don't give shit to these people.

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

            Aren't you?

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

              No one understands why you said the guy asking his question is fake. Maybe you just like to keep receiving downvotes, I suppose...

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

                Because Chinese people in 某谷 always pretend themselves.I 'm sorry for what I say.

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

            Yeah, will do. Thanks man

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

          Tips: Next time before you decide to retort upon somebody, check his contribution first.

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

          "fake" means "strong, but pretending to be weak" among OIers in China.

          I don't agree with him that you are "fake", I believe you asked the question because you really didn't know why it was wrong.

          However, I think it's better to find a counter-example by yourself instead of asking here. If you really want to ask here, I suggest you explain why you thought it was correct. Your explanation was not detailed, so I had to read your code, and I just couldn't understand why you thought it was correct.

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

            Ohh ok I get it now. I really hope I was actually good. Thankfully though this is the first div 2 contest that I have solved 2 questions in and I was so excited about solving C as well. Due to me solving 2 questions, my rating jumped by 129 points which is awesome! As to my question, your are absolutely right, and I am sorry I didnt provide a detailed enough explanation, it turns out it really was only bad logic. What made me believe that I had something going for me during the contest was that it failed at test 6 so I thought there was just a small thing or case that I forgot and then it would be accepted. Thank you.

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

        This dude needs english classes for babies.

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

      The whole commenting area would be blown up if everyone having problems like yours sent a comment. If your algorithm is tested wrong and you don't know why, there are many ways to figure out besides sending a comment asking for help. Also, when a link is posted, it is more often an exhibition of another solution with a different thinking to a certain problem that people wanna share, rather than an ask for help. So try to work independently :)

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

        Yeah, you are right. It's just that this is my first comment on a round and I so a few questions from people asking about their code so I assumed it would be fine. Sorry for the inconvenience.

      • »
        »
        »
        »
        31 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        kaogu

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

Why in div2 D they are using upper_bound and then decrement z instead of using lower_bound while iterating on z. When I use lower_bound it give wrong answer.

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

    And that is why you should read carefully the definition of these functions.

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

      Upper_bound gives value which is stricly greater than given value.

      why we are not checking for both values of z(upper_bound) and z-1?

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

        What do you mean by "checking both values of z and z — 1"?

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

          let the value of x(from one of the gems) is 50 and we want find upper_bound in following array 2 5 35 52 78 100

          z=upper_bound() will give the value 52 which sould be taken but we are decrement z which will give the value 35

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

            Ah. You misunderstood what z was for. z was actually meant to find the largest element smaller than given value.

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

              z is upper_bound() which is smallest element greater than given value

              infact stricly greater

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

                Yep, that's why we have to decrement z.

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

              It's easy to prove: no matter what z is, the bigger rx is, the smaller (rx−gy)2 and (rx−bz)2 are; for bz it's similar.

              This statement is in editorial for the problem xenia and colorful gems (problem D Div-2). I still cant understand how to prove this. Can anyone help me with this?

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

    Here's an example.

    #include <iostream>
    #include <set>
    using namespace std;
    
    int main() {
        set<int> a = {2, 4, 6, 8};
        cout <<
            // greater or equal, but no equal element
            *a.lower_bound(5) << "\n" <<
            // greater or equal, finds equal element
            *a.lower_bound(6) << "\n" <<
            // strictly greater
            *a.upper_bound(5) << "\n" <<
            // strictly greater, so ignores equal element
            *a.upper_bound(6) << "\n";
    }
    

    Output:

    6
    6
    6
    8
    

    Hope this clears things up.

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

      Thanks, now i got my mistake.

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

        Could you please explain why z is being decremented?

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

          Since we want the greatest value less than or equal to (let's call it) v, we find the number just before the least value strictly greater than v. There's some number just before and just after v in the set. (Or there are no numbers before, and that has to be handled separately.) upper_bound and lower_bound both give the number just after, and only are differ in whether they include v itself. The before and after are right next to each other, though, so finding the value just after and decrementing will get the value just before.

          In the example, suppose we have the set {2, 4, 6, 8} and we want to find the value just before 5. upper_bound gives us a pointer to 6, which is just after. Decrement the pointer, and you end up just before at 4.

          Now suppose we want to find the value just before 6, where equal to 6 is still ok. upper_bound gives a pointer to 8 because it never gives back the value itself. Decrement the pointer, and you end up at 6.

          I wish there was a standard function for finding the value before, but there isn't.

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

            As per your statement "the greatest value less than or equal to v ", if we get value equal to v we are fine with that but if it becomes less then it violates ours assumption of z being greatest of all.?????

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

      If r = {5} g = {5} b = {1,7} we fix g = 5 and look for upper bound from b which is 7 and according to the editorial solution z-- will indicate 1 so red(5) <= green(5) <= blue(1) which is violating the context . Isn't it ?

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

        You have it backwards. That would give the condition red(5) >= green(5) >= blue(1).

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

    I also had the same doubt. Actually {x,y,z} are different in editorial and implementation. I will be explain using implementation code. You can figure out the difference.
    Some Definitions-
    lower_bound() — greater or equal to the element.
    upper_bound() — strictly greater than the element.

    These are steps we are doing -
    1. We are fixing x from vector a.
    2. We need to find z from vector c such that z>=x hence we use lower_bound.
    3. We need to find y from vector b such that x>=y hence we first use upper_bound to find element strictly greater than x then decrements it which guarantees that y<=x is followed.

    So y<=x<=z relation has been followed as mentioned in editorial(note the difference in conventions).

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

can anyone please explain the editorial of problem 1336B — Xenia and Colorful Gems?

I am not able to understand it?

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

Otherwise, if we choose its parent to develop tourism instead of itself, the sum of happiness will be greater.

Here is a mistake. Should be "the sum of happiness will be smaller."

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

    I think so too. Been stuck at that line for a while. Authors please clarify.

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

    I think you mixed up "tourism" with "industry"? In the statement, you are asked to choose $$$k$$$ cities to develop industry, but here in the lemma, we are choosing cities to develop tourism.

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

Can anyone please explain Div2-D problem. I understood the core idea that we iterate over any one array and find closest int rest two but why is there 6 possible cases?

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

    i need to know too

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

      Imagine the solution : if it is ordered like $$$r_x \le g_y \le b_z$$$, then you need to run through the green set, and for every $$$g_y$$$ take a red $$$r_x$$$ just below $$$g_y$$$ and a blue $$$b_z$$$ just above.

      But what if the solution is rather $$$g_y \le r_x \le b_z$$$ ? You then need to run through the red set first (the middle one).

      Etc... You have to try all permutations.

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

    because there can be 6 possible permutations of x,y,z

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

A bit different solution for 1336D:

Spoiler
»
6 months ago, # |
  Vote: I like it -20 Vote: I do not like it

I tried using calculus in Div 2 Problem D(XENIA AND COLORFUL GEMS) but was not able to achieve a good equation has anyone done it with using Maxima and Minima approach , if yes Please explain it :)

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

This code is of div 2 problem A. Code

why it didn't got TLE as the range of the numbers is 10^9 and if the variable d=10^9 and and b+c=2 then the loop this code should give TLE

I think if loop goes beyond 10^7 or 10^8 it should give TLE

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

Is there a better explanation for Div1 C ?

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

    Let me try. I will explain the same dp but with another indexation and less cases to handle.

    Informal: Let dp[i][j] ($$$i\leq j$$$) be the number of ways to perform $$$j - i$$$ operations in such a way that the string we've built so far will be in the position [l..r) of the final string, provided that we did not perform invalid actions. For example, if $$$T$$$ is abac then dp[2][5] is the number of ways to build ac* where * is any symbol, counting that if we'll ever finish this as a spell then we add exactly 2 more letters to the beginning. This dp is easy to calculate using dp[i][j - 1], dp[i + 1][j], s[j - i] and probably t[i] and t[j - 1].

    More formal: Let's change the rules for our game. The new rules follow.

    We have an infinite sequence of free cells, numbered by $$$0$$$, $$$1$$$, $$$2$$$ etc. Before we start, we put a separator before any of the cells (either before the 0-th cell or between any two consecutive cells). In each turn we delete the first character of $$$S$$$ and put it either into the left nearest free cell to the separator (if any), or into the right nearest free cell. We cannot put a character $$$c$$$ into the sell $$$i$$$ if $$$i < m$$$ and $$$c\neq T_i$$$. After each turn we can claim our victory if the first $$$m$$$ cells are filled (by the letters of $$$T$$$, as follows from the rules).

    I state that the new game is equivalent to the old one. Indeed, putting the separator before the $$$i$$$-th cell in the new game corresponds to promising that we will add the character to the front of $$$A$$$ exactly $$$i$$$ times in the old game. I leave understanding of the relation between victories in these two games as an exercise to the reader.

    Now it's easy to calculate dp[i][j] which is the number of ways to eventually fill exactly the cells [i, j). The answer to the problem is the sum of dp[0][j] for j from $$$m$$$ to $$$n$$$.

    My dp calcuation:

    It's not necessary to calculate it in this order; one could also do for i := n..0; for j := i + 1..n.

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

      what exactly is l and r ?

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

      I've seen that many top contestants used this indexing, but I couldn't understand it before. Thanks for the explanation.

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

    I myself failed to understand the tutorial too. I've read some comments under the announcement blog and have looked through some implementations.

    Assume that both strings $$$S$$$ and $$$T$$$ are of equal length, that is $$$m = n$$$. If it is not the case, append some special characters to $$$T$$$ that say that any character may be there. You have to count number of ways to build string $$$T$$$ using the two operations. Let $$$dp(l, len)$$$ be the number of ways to build string $$$T[l, l + len - 1]$$$ having used first $$$len$$$ characters of $$$S$$$. When you have a string $$$T[l, r]$$$ and you consider the next character, that is $$$S[r - l + 2]$$$, you can proceed to states $$$T[l, r + 1]$$$ and $$$T[l - 1, r]$$$, but only when $$$T[l - 1] = S[r - l + 2]$$$ or $$$T[r + 1] = S[r - l + 2]$$$ respectively. If $$$T[i] = ?$$$, a special character, then it is always true that $$$T[i] = S[j]$$$, for any $$$j$$$. To get the answer remember that you don't have to use all $$$\lvert S \rvert$$$ characters, you may stop after some steps, so you need to sum $$$dp(1, len)$$$, for $$$len \ge \lvert T \rvert$$$. I assumed that $$$\lvert S \rvert = \lvert T \rvert$$$, but you still need to store the initial length of $$$T$$$ before appending special characters to calculate the answer.

    Have a look at my submission 76955112. The hack I use when filling initial $$$dp$$$ state is proceeding up to $$$n + 1$$$ as without it I don't get correct $$$dp(n, 1)$$$ because $$$dp(n + 1, 0)$$$ is used.

    I would like to see the tutorial to be presented in a clearer way so I can understand how exactly our solutions are different.

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

Here is a solution for div2 C (detail explanation with code ) Check Here

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

    Is this a sort of blog of yours?

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

    You say that for a node with c children and at level x from root, if we choose as tourism city then it will contribute (c)*(x). But that presumes that all the ancestors are tourism cities as well. What if not all ancestors are tourism cities?

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

      There is no meaning of building industry on the ancestors (it wont maximize) Because if a node has c*x happiness (assuming all the ancestor is tourism spot) Then we will first build industry on that not on its ancestor

      And thats why if a node give c*x additional happiness its ancestor will give less for sure

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

    In step 4 you said that if a node has c children and it is at a depth of x,then it will give c*x happiness if we select it...select it as what?? Industry or tourism?? if we select it as a tourism city, then i think happiness will be c*(x+1).As depth of a node u means the number of nodes in the path [1,u).u is excluded. So if we include u as a tourism city then the number of tourism city in front of the c children becomes (x+1). So happiness becomes c*(x+1).

    I am stuck here. Please Help.

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

      Suppose Node A has depth x [1,x] x included A has c children and as its tree if we are going to select A we must have build industry in all of its children (remember A is still tourism we have not build anything) A as a tourism spot — c*x ( as all children will pas through x nodes) A as a industry — we have now (c+1) industry and (x-1) tourism spot so (c+1)*(x-1)

      Remember its tree so we are just thinking about that particular branch and then comparing it with others

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

    There are a few places where you have mixed tourism and industry and the total contribution by each node towards the total happiness will be (c-x).

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

      I may have make it bit blurry . I took (x-1) as remaining tourism spot where taking it x will make it clear

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

Is there any specific reason for vector/set giving TLE in div1B ? I was trying to optimise my logic but couldn't come up with anything, so randomly changed vectors to arrays and it passed in around (1/15)th of the time limit. Got around 6-7 wrong submissions simply because of using vectors :/ I don't think I have ever gotten TLE before with n being 1e5 and the code running in O(n.logn) with vectors :(

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

    Looking at the code i guess you simply forgot to put the "&" when passing vector to functions.

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

      Oh damn. I completely ruined the contest because of this silly error. :( Thanks!

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

Is std::nth_element faster than std::sort?

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

    Yes, it has Linear complexity since it doesn't sort the entire sequence. Rather, places in the nth position the number which should have been in that position if the sequence was sorted. The rest of the elements won't be in any particular order except for the fact that all elements before the nth element won't be greater than the nth element and all the elements after it won't be smaller.

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

I solved the Div2D 1337D - Xenia and Colorful Gems a bit differently. I created an array $$$v = r \cup g \cup b$$$ and sort it with keeping track of from which set they come. Whenever I have found $$$3$$$ numbers, I calculate an answer and keep the best one. First, notice some observations.

  1. For an $$$rrrggggbbbb$$$ portion, it is better to take the latest $$$1st$$$ number and the earliest $$$3rd$$$ number in a sorted triplet to find the best result.
  2. For an $$$rggggb$$$ portion, the best $$$g$$$ would be the one which is the closest to $$$(r+b)/2$$$. One can easily prove this using some mathematical expression.

Once we read the first number (and know which set it's coming from), the $$$5$$$ cases are possible while iterating over $$$v$$$. Consider the array $$$v$$$ looks like this in the beginning.

$$$r_0 r_1 r_2 g_0 g_1 g_2 g_3 b_0 g_4 r_3 ...$$$

Cases:

  1. We are still reading the $$$1st$$$ type of number. If so, just take the latest one ($$$r_2 g_0 b_0$$$ is better than $$$r_0 g_0 b_0$$$, using observation $$$1$$$).
  2. A new type of number has been read. This is our $$$2nd$$$ number.
  3. Once we have found some $$$2nd$$$ number, we are looking for a $$$3rd$$$ one. If the $$$2nd$$$ number keeps repeating, we just take all of them to a temporary array.
  4. If the $$$1st$$$ type of number comes back instead of $$$3rd$$$ or $$$2nd$$$, make it the new $$$2nd$$$, and turn the old $$$2nd$$$ into new $$$1st$$$. ($$$b_0g_4r_3$$$ is better than $$$g_3b_0r_3$$$)
  5. Lastly, if we indeed reach a $$$3rd$$$ number ($$$r_2 g_0 g_1 g_2 g_3 b_0$$$ or $$$b_0 g_4 r_3$$$), we need to find the best $$$2nd$$$ number from the temporary array using binary search. Say, $$$r_2 g_1 b_0$$$ is the best we have found. After finding the result, make the current $$$2nd (g_1)$$$ into $$$1st$$$ and the $$$3rd (b_0)$$$ into $$$2nd$$$, waiting for an $$$r$$$ to occur and $$$gbr$$$ to happen. But wait, is that right? Not really. We indeed want a $$$gbr$$$ to occur, but the best $$$g$$$, in this case, is not $$$g_1$$$, it's $$$g_3$$$, the one that's right before the $$$b_0$$$ which we declared as the new $$$2nd$$$ (or the old $$$3rd$$$). It's similar to the Case $$$1$$$ described above. Be careful at this part.

This eventually goes over all possible triplets, and every time we find a triplet, we find the best middle ($$$2nd$$$) number using binary search. My submission: 76948887.

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

Why does finding 3 closest numbers using 3 pointers in the 3 sorted array(moving ahead the pointer with min value) fail in DIV2-D.Can someone please point out a case?

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

    I'm not 100% sure how are you going to update the pointers, so try this case.

    3
    2 2 2
    1 2
    2 3
    2 5
    2 2 2
    2 3
    1 2
    2 5
    2 2 2
    2 3
    2 5
    1 2
    

    All 3 here are actually the same, but I have a feeling that your pointer update process might fail in 1 or 2 cases.

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

    it will not fail, you just have to adjust according to requirement of min of the sum of squares. Check out my solution 76926016

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

      why are you using sum of squares to move the pointers instead of moving the pointer which points to the minimum element?

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

For Div2(C), my logic was to sort nodes ascending according to their degree(no of other nodes they are connected to) and then descending according to their depth. Then choose first k nodes as industry. Why is this approach incorrect ? Can anyone suggest a test case please?

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

EternalAlexander could you please simplify the notations of the problem div1 C?

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

Can Anyone explain the Top-Down Approach for Div.1 (C) 1336C — Kaavi and Magic Spell ???

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

Everyone seems to be solving 2E/1C in $$$O$$$$$$($$$$$$n^2$$$$$$)$$$ memory while tourist did in $$$O(n)$$$ — 76845451. Can someone who understands his approach please explain how it is different from the one discussed in the editorial?

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

I am not getting the solution of linova and kingdom can anyone explain me?????

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

For Div2 D. I used a simple 3 pointer search similar to this gfg link. My submission - 76926016

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

    My approach is same with you. I guessed this solution during the contest, but can't proof it until now:(

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

    on what basis u are incrementing i,j,k in while() loop??? plz explain :( cant get this. thank u

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

      I calculated 3 new sums(tmp1,tmp2,tmp3) by increasing each one of i, j and k. Then increased i, j or k whichever resulted in the smallest tmp value.

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

I dont understand the meaning of size(u) in problem C. Please explain me the reason why we subtracted it from the depth of every node??

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

    to subtract the losses because of converting industry to tourism. This is because there will be no convey from this city.

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

[problem:div2c]In this problem first i'm trying to add all the happiness values of all the farthest nodes then second farthest and so on untill i have taken <k nodes in last iteration. then all the nodes which are at height h are taken partially to make exact count of k. for this i subtract from ans this value: (sz[i] — 1)*h and add this value: sz[i] * (h -1). can someone tell why it's not working?? code just do cout<<ans<<"\n";

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

Can anyone help with this proof

no matter what z is, the bigger x is, the smaller (x−y)^2 and (x−z)^2 are; for z it's similar. Div2/D Problem Xenia and colourful gems

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

Can anyone help me understand the approach div2 E Kaavi and magic spell? What is j represent here? Dp[i] [j] represents what?

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

Can anybody explain why my submission 76966044 for Div 2C is getting Runtime error on Testcase 9? My approach is the same, i.e calculate depth — (no. of nodes in it's subtree) for every node and then print the sum of the k largest elements.

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

    I never used python. How does this work with local variables and recursion?

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

      If you are asking about the variable count1, I have already initialized it outside the function, on line no. 29

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

        So why do you return it, and copy to treecount?

        What about example 5 of this tutorial? As I understand it says the local variable is local.

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

          Right, the variable declaration might have been causing some problems in the recursion, so i changed from the recursive approach to an iterative approach and it finally got AC. Thanks a lot

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

Why the ans is b,c,c in the first question instead of b,c,d in the first question?

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

    let a=1,b=1,c=2,d=3 taking sides as b=1,c=2,d=3 . 1 + 2 == 3 . not Correct. the thing is b+c is always greater than c but if you choose third side as d , in some cases b+c will equal d ( because d > c )

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

      Means we haveto follow the property x+y>z, x+z>y && y+z>x Right?

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

        yes , sum of two sides greater than third

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

    By choosing b, c, c, notice that b + c > c and c + c > b. These 2 inequalities works for all positvie b and c, hence it always work.

    If you did b, c, d, b + c can potentially be less than d. For example, simply consider the input 1 1 1 10. You would print 1 1 10 instead, when you can just build an equilateral triangle with sides 1.

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

On 1337D i tried to sort all the three arrays, and for each fixed x, i would ternary search for y, but to make the decisions on this ternary search i would make another ternary search for z. Code . It did pass 22 test cases. It is not easy to find cases to make it fail.

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

Why once upper bound and lower bound is used? Why I can't use lower bound/upper bound twice? can squares return value zero? Can someone please explain?

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

    First lower bound used because you want to have a value which is not less than x(i.e greater than or equal to x).Second,upper_bound (with z--) to have the greatest value which is smaller than x in c,now we can't use lower_bound here because lower_bound will give a value not less than x(the value may be equal to x we don't want that we need strictly greater) for eg. say we have c= 2,3,6,6,6,7 and x=6 now when we use z=lower_bound(....)(which is wrong) z will be equal to 6 and z-- =3 but what we need is z to be 7 and z-- =6 which will minimise the difference.

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

      Thank you, It was very helpful and well explained.

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

      What if c = 2,3,7 and x = 6. We want z = 7 but z-- will make it 3 which is less than x?

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

        That's why we are trying different possible combinations

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

Cant find Tutorial of 1337D Problem (Ps: I am new here can anyone help)

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

For div.1 E2 Lemma 3

How to proof that the linear space B has exactly $$$m-k$$$ bases ?

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

    First, it is clear that the length of $$$B$$$ is $$$m$$$ when $$$k=0$$$.

    Every time we add a new base to $$$A$$$ (also, $$$k$$$ is increased by $$$1$$$). $$$B$$$ is impossible to be $$$B$$$ before, we must remove some bases in $$$B$$$. If we remove more than $$$2$$$ bases in $$$B$$$, the length of $$$B$$$ is minus when $$$k$$$ is increased to $$$m$$$!

    So the length of $$$B$$$ has to be $$$m-k$$$.

    UPD: I found a much easier way to prove it. See it in the new tutorial.

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

I am trying to implement div2C, my code clearly runs in O(nlogn) time, but I keep getting TLE.

one of my subbmissions. I have checked many times but couldn't find what is wrong.

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

i don't know why i am getting WA in div-2 D.I am using 3 pointer technique to minimize the difference between largest and smallest element chosen and then finding the mid element which minimizes the answer. here is link to my code: https://ideone.com/XzeUzs thanks in advance

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

Another solution for 1336C:

Spoiler

This solution is easier to think,understand and implement than the editorial.

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

Can anyone re-explain E1 to me ? :'(

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

My observations and solution for Div2 C / Div1 A and Div2 D / Div1 B in the Announcement thread:

Div2 C

Div2 D

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

There is another straightforward to think greedy solution using hld for Div1A:

Let, $$$t(u) = \text{number of chosen vertices in subtree of }u$$$, $$$l(u) = \text{level of }u\text{ if we root the tree at }1\text{ (in particular }l(1)=0)$$$.

Maintain $$$f(u) = l(u) - t(u)$$$ for all free (not chosen) vertices.

Initially, $$$\text{ans}=0$$$. Then, do this $$$k$$$ times:

  • Choose $$$v = \text{arg}\,\max\limits_{u\text{ is free}}\,f(u)$$$.
  • $$$\text{ans} := \text{ans}+f(v)$$$.
  • To maintain $$$f(u)$$$, you need to decrease $$$f(u)$$$ by $$$1\, \forall u \mid u \in \text{path}(1 \rightarrow v)$$$. (Do this using hld)

Complexity: $$$\mathcal{O}(n + k \log^2 n)$$$

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

    how is that straightforward

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

      $$$f(u)$$$ means how much I can gain from choosing $$$u$$$... this is the first thought that crosses mind.

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

        Trying to put tourism spots at nodes with maximum size subtrees first comes to mind first (which is incorrect, but can be fixed).

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

    Since we would choose all nodes in a subtree of node u before u itself, we would better use number of all nodes in that subtree in the first place. Instead of adding them one by one.

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

    Hey I have been trying to come up with solution div2c for a while. But even after reading editorial and some comments I could not understand the observations. May be I am thinking in a differnet away that is not close to the actual solution or I am lost. Can you please helpe understading some initial obersavtion made by others not actual soution. May be I am not on right path.

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

A question regarding 1336A - Linova and Kingdom tutorial: why are you saying that std::nth_element in STL implies an $$$O(n)$$$ solution? As far as I understand, std::nth_element works in $$$O(nlogn)$$$ time

Ref: https://en.cppreference.com/w/cpp/algorithm/nth_element

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

    In the page you mentioned, are you reading the correct footnote? Overloads 2 and 4 take an execution policy as an additional parameter, while overloads 1 and 3 are "Linear in std::distance(first, last) on average" according to your page.

    For more details, see https://en.wikipedia.org/wiki/Quickselect.

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

      Thank you, indeed, I misread the footnotes :)

      Then it's $$$O(n)$$$ on average and $$$O(nlogn)$$$ in the worst case, right?

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

      I reacted to the claim that the solution is $$$O(n)$$$, which is not the case, since big-O notation marks the upper bound of the function (time complexity), and not the average.

      With $$$1 <= k < n$$$ the solution complexity is still bound by $$$O(nlogn)$$$

      Similarly, you can't say that quicksort is bound by $$$O(n)$$$ — that's its average performance, but in the worst case it's bound by $$$O(nlogn)$$$

      Sorry for being pedantic, just wanted to point it out.

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

        You correctly state the average and worst-case complexities, and I agree with you that when someone says "a solution runs in O(something)", the implicit assumption is that they're talking about worst-case complexity. So the post should have said "O(n) average time" to avoid this confusion. Your concern is perfectly justified, in my opinion.

        I also want to point out your previous comment is absolutely correct too. Big-Oh notation can be used to denote an asymptotic upper bound to any function, and in particular you can use it to bound the average-case complexity as well as the worst-case complexity, and so "O(n) on average" is a technically correct use of big-Oh notation.

        Either way, nth_element could have been implemented with the Median of medians algorithm to guarantee worst-case O(n) complexity. In practice, the STL implementations we use rely on a variant of Introselect that combines Quickselect and Heapselect. Wikipedia seems to claim that the original Introselect combined Quickselect and the Median of medians algorithm for optimal worst-case complexity, but I can't confirm that.

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

I didn't understand the solution of 1336B — Xenia and Colorful Gems,

** z--; ** ans = min(ans, sq(x - *y) + sq(*y - *z) + sq(*z - x));

why z-- needed? can't we achieve the functionality? using,

if (z == b.end() ) z--;
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because You need the element which is strictly greater than x which is z than z-- which implies greatest element which is smaller than x in c

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

      then why not y++? because here now y is strictly less than x.

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

i did not understood the editorial for problem C, it is not written well,to clarify my doubts sizu is the size of the subtree of u and depu is its depth ,consider for the last node of the tree with 5 nodes its sizu will be 1 and depu will be greater than 1 , now the author is saying the total happiness will be increased by sizu−depu: here sizu−depu=1-x ,x>1 (sizu−depu) will be a negative value,now how can negative value increase the happiness ???

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

In 1336B - Xenia and Colorful Gems . Why the idea of choosing nearest element (Binary search) instead of lower bound fails in Test case 48? How is that approach incorrect? My submission 77012000 . I am using a give function to print closest element corresponding to k in some array. Edit: It passed now.

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

Can anyone tell me the bug in my code for Div2C? Here's the link. I followed the same solution which is mentioned in the tutorial. I sorted the nodes according to the children count and if the children count is equal for two nodes, then I chose the node with greater depth to develop the industry.

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

In div1B my code is giving correct answer for test case 1. but on submitting it is sowing some different answer(instead of 1999999996000000002 some other answer is printing)77017823. please help.

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

    Try using unsigned long long everywhere.

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

    The problem is: const long MAX = 9e18 -> const long long MAX = 9e18.

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

The solution to E2 is very interesting, but the tutorial is a little bit hard to understand for me at the beginning. Here are some suggestions:

(1) It would be better to use "Walsh-Hadamard transform" instead of "FWT" here, because fast or not does not matter here. (It's not affordable to explicitly compute it anyway.)

(2) Similar to (1), I feel that "XOR convolution" is a little bit distracting here, because we only care about one term anyway. It made me feel that "we do Fast Walsh-Hadamard transform because we want to do XOR convolution fast", but this is not true.

(3) The proof of lemma 4 doesn't really make sense. "The $$$i$$$-th number of $$$F^c$$$ only depends on $$$popcount(i)$$$, it certainly still holds after Fast Walsh-Hadamard Transform." is true because the the property here is "popcount". If you replace "popcount" with something else it will be false. The formula you listed below should be the actual proof for this lemma.

If I'm going to explain this solution I will try to rephrase it as follows. The main purpose of doing Hadamard transform is to move the analysis from linear subspace $$$A$$$, which has high dimension ($$$k$$$), to another linear subspace $$$B=\{y:\forall x\in A, \langle x,y \rangle=0 \pmod 2\},$$$ which has low dimension ($$$m-k$$$). Hadamard transform provides a linear transformation between $$$[x\in A]$$$ and $$$[y\in B]$$$: $$$[x\in A]=\frac{1}{|B|}\sum_y (-1)^{\langle x,y\rangle}[y\in B]$$$. Therefore if we want to count how many vectors in $$$A$$$ satisfy some properties, we can enumerate every $$$y\in B$$$ and calculate its "contribution" instead. Formally, let $$$F_c$$$ be the set of all vectors which have $$$c$$$ 1s. Then we have $$$\sum_{x\in F_c} [x\in A]=\frac{1}{|B|}\sum_{y} (\sum_{x\in F_c}(-1)^{\langle x,y\rangle })[y\in B]$$$. If we simply enumerate every $$$c\in[m],y\in B$$$ and calculate the contribution of $$$y$$$ in $$$F_c$$$ by some combinatorial methods, we have a $$$O(m^2\cdot 2^{m-k})$$$ algorithm already. By observing that the coefficient only depends on the number of $$$1$$$s in $$$y$$$, this can be squeezed to $$$O(2^{m-k}+m^3)$$$ as in the tutorial.

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

Really clean editorial and I like it a lot.

One small comment to add for Div2C.

I thought of the lemma during the contest but did not end up solving the problem.

For someone who wonders "why does sorting according to siz_u — dep_u and selecting the first N — K cities to develop tourism ensure that the selected cities stay connected?", it is because the siz_u — dep_u property makes it such that a child node is selected iff its parent node is selected.

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

Elegant problems and short, concise statements. Thank you for this fine contest!

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

Video tutorial Div1C/Div2E 1336C - Kaavi and Magic Spell here

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

Someone please explain Div 2 C briefly.

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

    since the capital city is at node 1 we have to place industries in such a manner that total sum of tourism cities is maximum for each of the industry

    greedy thought
    proof
    problematic situation which may occur to disturb our greedy solution
    solution to above situation

    hope it's clear now

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

      It is not the node as far as possible from root. Given node u 2 away from root and having 3 children. And node v 3 away from root but with one child only. Then you have to choose v before u, because it contributes more.

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

        that is what i have said in third and fourth spoiler correct me if I am wrong

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

solution for div 2 d is very elegant

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

I am trying to write an easier explanation for Div2E/Div1C.
Our target is to build a string of length $$$n$$$, which is initially empty.

1 2 3 ..... n

$$$dp_{i,j}$$$ is a state where we have already filled up all the positions in the range $$$[i+1,j-1]$$$.

1 2 3 ..... i i+1 ..... j-1 j ..... n
* ***** *

Now we will either add the next character at the beginning (at index $$$i$$$) if it is equal to $$$T[i]$$$ or we will add the next character at the end (at index $$$j$$$) if it is equal to $$$T[j]$$$. The first option will take us to the state $$$dp_{i-1,j}$$$ and the second option will take us to the state $$$dp_{i,j+1}$$$.
Our answer is $$$dp_{1,1}+dp_{2,2}+dp_{3,3}+.....+dp_{n,n}$$$.
Here is my submission.

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

    what if it's not equal to both T[i] and T[j].

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

      Then, you can't go to any of the two possible new states.
      So answer for the current state $$$dp_{i,j}$$$ will be $$$0$$$.

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

    I think it should rather be Our target is to build a string of length m, which is initially empty. or did i miss something?

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

      It's $$$n$$$. Because we will use all the characters from the string $$$S$$$.

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

    Thank's i Got it

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

For div2 C. When I submitted this solution. I got the Wrong answer at test case 7.

But when I submitted this solution it got accepted.

The only difference between these two starts from line number 34 in the wrong answer I declared the array res as vector int and for the right one, I declared it using pair of vector int.

So Why one is got accepted and the other one got rejected ?

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

someone please tell me that why we have added z==c.begin() condition in solve method in Div2. D in editorial I mean upper_bound is returning the smallest index which has greater value than the key searched so suppose if the min value of vector c is greater than the key the result will be c.begin() why would we do continue in this case (can't we form a triplet with value from vector c as c.begin() ) what's wrong with doing that

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

Why is this solution in Python giving Runtime Error on Case 9

76970117

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

can any one tell me why i am not getting this error wrong answer 2nd numbers differ — expected: '1999999996000000002', found: '1999999996000000000'

https://codeforces.com/contest/1337/submission/77100823

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

Can anyone please explain { DIV2 : E. Kaavi and Magic Spell }. I am not getting it from the editorial. Not even the intuition.

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

Nice round :) Thank you ^^

btw, you don't have to actually hold the dp matrix in div1C, as the update only use the next location for each update, you can update it from left to right.

Here is a very short solution:

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

    It's really short. I didn't fully understand the solution from the editorial though.
    I was able to solve it using O(n) space too. But I had to store two rows since my current state calculates answer using the values from the previous row.

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

How to solve the bonus part of E2? :(

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

In Div1 E in this part "build linear basis A with given numbers", what do you mean exactly? Build a set with minimum number of elements of the input such that all the elements are linear combination of those?

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

    consider each number as a zero-one vector in $$$\mathbb{F}_2^m$$$, then find a basis of this vector space. Then, each given number can be written as the xor of a subset of this basis.

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

      In that case a base could be { (1,0,...,0,0) , (0,1,...,0,0) , ... , (0,0,...,0,1) }, right?

      I don't understand why $$$ ans_i = p_i \cdot 2^{n-k} $$$.

      Do you know a post where i can learn this?

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

        "In that case a base could be { (1,0,...,0,0) , (0,1,...,0,0) , ... , (0,0,...,0,1) }, right?"

        No, that's a basis of $$$F_2^m$$$, but we want a basis of the subspaced spanned by the given vectors.

        As for why $$$ans_i=p_i\cdot2^{n-k}$$$: let $$$V$$$ be the set of input vectors, and let $$$A\subset V$$$ be a basis of the subspace spanned by $$$V$$$. First we look at linear combinations of $$$V\setminus A$$$, then we consider linear combinations of $$$A$$$ to get a desired popcount. Choose any linear combination of $$$V\setminus A$$$, there are $$$2^{n-k}$$$ of these, and suppose the xor sum is $$$x\in span(V)$$$. Each $$$x$$$ that we get this way can be expressed uniquely as a linear combination of vectors in the basis $$$A$$$. Now consider one of the $$$p_i$$$ linear combinations of vectors in $$$A$$$ such that the resulting popcount is $$$i$$$, and suppose the xor sum of this linear combination is $$$y$$$. There is a unique way to use the basis vectors to go from $$$x$$$ to $$$y$$$, ie. writing $$$y-x$$$ as a linear combination of the basis. This gives a bijection that shows $$$ans_i=p_i\cdot2^{n-k}$$$.

        "Do you know a post where i can learn this?"

        This is linear algebra with a bit of combinatorics.

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

          I don't get one moment.. Suppose we get any linear combination from $$$V \setminus A$$$ which have xor sum $$$y$$$. Then we get any subset $$$X$$$ from $$$A$$$ that have popcount equal to $$$i$$$ and xor sum -- to $$$x$$$. How come that we're always able to express $$$y - x$$$ as linear combination of vectors from $$$A \setminus X$$$?

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

            Oh, seems that otherwise we've couldn't express $$$y$$$ as linear combination of vectors from $$$A$$$. Cause linear combination of $$$x$$$ is also unique

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

          Can you elaborate more on the part where you say "This gives a bijection that shows ans_i = p_i * 2^(n-k)."?

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

            Every linear combination of $$$V$$$ is the sum of a linear combination of $$$A$$$ and a linear combination of $$$V\setminus A$$$. One way to get a linear combination of $$$V$$$ with popcount $$$i$$$ is to choose a linear combination $$$x$$$ of $$$V\setminus A$$$ and a linear combination $$$y$$$ of $$$A$$$ with popcount $$$i$$$. Once we fix $$$x$$$ and $$$y$$$, we can put $$$x$$$ as the linear combination of $$$V\setminus A$$$, and $$$y-x$$$ as the linear combination of $$$A$$$. The number of ways to choose $$$x$$$ and $$$y$$$ are $$$2^{n-k}$$$ and $$$p_i$$$ respectively.

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

          I have the same doubt as Ahmed_Salama, how can we say that the answer is $$$2^{n-k}.p_i$$$ Also can you please elaborate the bijection part? What exactly are we bijecting and on to what? And how does this relate to answer?

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

Can anyone please help?

Problem Div2 D : I have coded solution as per editorial, verified the data types of ans, vector. I am getting correct answer for the sample test on my machine, but on submitting I'm getting a different output.

wrong answer 2nd numbers differ - expected: '1999999996000000002', found: '2147483647'

submission 77118100

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

    Ok found the mistake. Was setting LONG_MAX to a long long.

    Still confused why I got correct output locally(on my machine),

    $ g++ --version
    Apple LLVM version 10.0.1 (clang-1001.0.46.4)
    
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      LONG_MAX could be defined differently. You could define your own infinities to avoid this.

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

        Ok. Wasn't aware. Thanks a lot for clearing my doubt.

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

Can someone please tell me why am I getting WA on test case 6 on div2 C . My logic is to find the depth and the no. of children of each and every node. Find depth[i]-children[i] for all nodes and return the sum of the top k values Here's the code https://codeforces.com/contest/1337/submission/77153692

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

Can anyone suggest more good problems like DIV2 'C'(1336A)

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

Heres My Solution to Problem 1336C Memoized Solution I couldnt come up with dp solution can any body tell why with memoized solution its giving TLE? :)

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

Solution

Why my code is not working for Div1 A, I have chosen all the leaf nodes then for the remaining k I have chosen nodes from that branch which had maximum happiness initially.Please help

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

I don't Understand Div 2 problem D can someone explain to me what's wrong in my idea Idea: First, assume the solution is of the form x<=y<=z fix x and found y by lower_bound(b.begin(),b.end(),x) then found z by lower_bound(c.begin(),c.end(),*y)

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

    Try this:

    1
    1 2 1
    1
    2 3
    5
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've also used the same approach.My code passes your test case. But fails System Case. For all possible 6 combinations of arrays r,g,b I've used finding x<=y<=z Approach. Please Help!

      Code

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

How to approach problem C. sizu−depu, how do we get to know about this? observation & intuition?

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

Can anyone help me why I am getting wrong answer for the test case 6 for this submission https://codeforces.com/contest/1337/submission/77191116. The problem is https://codeforces.com/contest/1337/problem/C (linova and Kingdom)

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

Hey Guys, If you want a solution for Div.2 B — Kana and Dragon Quest Game

Please check out this video!

https://youtu.be/DGo4IU143nQ

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

I use a Max heap in which I I store (-subtreesize,depth of node) and when all subtree nodes are marked ,I add parent(root) of that subtree to priority queue and Mark all the popped nodes from priority queue which are my industries still I am getting wrong answer.https://codeforces.com/contest/1337/submission/77251353

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

Given two integer arrays as input. Your function will return YES if any two of the numbers in the first array adds up to any of the number in second array. Time Complexity required O(n). EXAMPLE:1 A=[-1,8,3] B=[3,7,2] OUTPUT: YES as(-1+3=2, presend in array B) also (-1+8=7, present in array B)

EXAMPLE:2 A=[9,6,12] B=[1,2,3] OUTPUT: NO can some help me out in this(similar to two sum)

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

plz explain the logic i problem D

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

Can someone please explain Magic Spells ? Ashishgup I liked your code on this. Can you just tell, what is dp[i][j] in your solution ?

Thanks

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

Can anyone explain the time complexity for the 1336B problem?

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

For 1337C- Linova and Kingdom,

I did same but I was getting Runtime Error which must be due to recursion limit as it will be exceeded if we have all 10^6 nodes connected in a sequence.. So I tried to increase the limit to 10^6 but for that, I got memory limit exceeded error.

Then I tried to set it to 10^5, but for this one also I got Runtime error.

Can anyone suggest what should I have done?

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

I think I am missing something for Division 2 Problem C: Linova and Kingdom. I have the following problem with the author's solution:

When calculating increase in happiness, when we choose a certain node $$$u$$$ to develop into a tourism city, then the loss is $$$dep_u$$$, this is correct: since all the parent nodes are already taken by the lemma that the author proved at the beginning. But when we calculate the gain, it is, at that moment, equal to $$$size_u$$$. But when we color some predecessor of $$$u$$$ in subsequent (later) steps, then this gain value changes, because some nodes in the sub-tree of $$$u$$$ no longer remain as an industry city.

EternalAlexander, or anyone, please point out where am I wrong. Thanks!

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

    You can see that, when you colour node $$$u$$$ all its predecessors are already coloured in previous steps. Because for all predecessors of $$$u$$$ the $$$size-dep$$$ is greater than $$$u$$$.

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

      OK, sorting takes the predecessors first in a branch. But out of all the possibilities over all branches, how does sorting ensure that it takes the best possible node? Because the number $$$size_u - depth_u$$$ doesn't really make sense to me, because it loses its significance when we take a child of $$$u$$$, it's value completely changes. So why do we store these numbers in an array and sort them. I think this needs some kind of proof??

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

        We have proved that, in the optimal way, when you take node $$$u$$$, all its predecessors are already taken, otherwise you should take the predecessor first.

        So before we take node $$$u$$$, all the nodes in its subtree are definately not taken. So in the optimal way, when you take node $$$u$$$ the change to the answer is $$$size_u - depth_u$$$.

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

          Yes you have proven that, but how do you prove that out of all possible nodes in a given depth (all the nodes in previous depths are already taken), the optimal node is the node with the maximum value of $$$size_u - depth_u$$$? Because this number doesn't mean anything after a few steps. So why do we store it? And sort them?

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

            Ok, I'll try another way to explain.

            Here $$$k$$$ denotes to $$$n-k$$$, i.e. the number of tourism cities.

            Let $$$f_u$$$ be $$$size_u - depth_u$$$.

            First, the optimal answer is no less than the greatest $$$k$$$ of $$$f_u$$$. Because that's the answer when you take the first $$$k$$$ nodes.

            Second, the answer can not be greater than that:

            If there exists a way to make the answer greater, assume that the nodes you've taken are $$$u_1, u_2 \cdots u_k$$$, the sum in this way will be $$$f_{u_1} + f_{u_2} + \cdots + f_{u_k}$$$, because for any node taken, all its predecessors are taken, and you can calculate the answer in this way. And you can see this is no greater than the sum of the $$$k$$$ greatest $$$f_u$$$.

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

            The main idea is:

            1. In the optimal way, when you take node $$$u$$$, all its predecessors are already taken.

            2. If the nodes you take satisfy the condition above, assume the nodes you take are $$$u_1,u_2 \cdots u_k$$$, the answer is $$$size_{u_1} - depth_{u_1} + \cdots + size_{u_k} - depth_{u_k}$$$.

            3. If you take the greatest $$$k$$$ of $$$size_u - depth_u$$$, the nodes you take satisfy the condition above.

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

              OK I got it, thanks a lot!!!

              When you sum those values, the change in $$$f_u$$$ of parent due to child node gets added to the answer, and sorting ensures that the conditions $$$1$$$ and $$$2$$$ are always fulfilled, so it is optimal to take the best $$$k$$$.

              Thanks a lot, really!

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

can someone please give solution for 1336C - Kaavi and Magic Spell with proper explaination. I can't understand the editorial.

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

Div2.C Linova and Kingdom is giving Runtime Error on test 9 on several solutions. Can anyone who faced the similar issue clarify what correction they made?

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

    It's called integer overflow. So use long long as your 'ans' data type to accumulate the sum !

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

Can someone explain problem 1336A like I am a 6 year old please ?

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

In 1336B-Xenia and Colorful gems, why the value of ans is set to 9e18? I kept ans as unsigned long long, and set ans = -1, thinking it would set maximum value to ans. It didn't give correct output. But setting 9e18 gave. Can anyone help me telling why? TIA.

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

Why b,c,d can't give correct ans for problem A. https://codeforces.com/contest/1337/submission/81934213

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

    Input: $$$ a = 1,~b = 1,~c = 1,~d=1e9 $$$. By condition we should have $$$ (b + c) \geq d \to (1 + 1) \geq 1e9 $$$. It's false.

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

Does anyone know more problems like 1336C — Kaavi and Magic Spell ?

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

For Div2D/Div1B My Approach is very similar to Editorial's. Its failing System Tests.

We assume the solution is of the form x<=y<=z. Then Fix x and find y by lower_bound(b.begin(),b.end(),x). Then find z by lower_bound(c.begin(),c.end(),*y)

We do this for all 6 Possible Combinations of Arrays r,g,b.

Code

Please Help!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
#define ll long long int
#define inf 1000000000000
#define mod 998244353
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define for0(i, n) for (int i = 0; i < n; i++)
#define tc(t) int t; cin >> t; while (t--)
#define all(v) v.begin(),v.end()
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define ps(x,y)         fixed<<setprecision(y)<<x
using namespace std;
string s, t;
map<string, int> dp;
int n;
int steps = 0;
ll ways(string a, int ind)
{
	if (ind == n)
	{
		if (a.substr(0, t.size()) == t)
			return dp[a] = 1;
		else
			return dp[a] = 0;
	}
	if (dp.count(a))
		return dp[a];
	ll ans = 0;
	if (ind >= t.size())
	{
		if (a.substr(0, t.size()) == t)
			ans+= 1;
	}
	steps++;
	ans += ways(a + s[ind], ind + 1) + ways(s[ind] + a, ind + 1);
	return dp[a] = ans % mod;
}
int main()
{
	IOS
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	string a;
	cin >> s >> t;
	n = s.size();
	a = s[0];
	ll ans = ways(a, 1) % mod;
	cout << ans * 2 << endl;
	//cout << steps<< endl;
}

can anyone help me to optimize this ?? showing TLE on testcase 7...
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1336B — Xenia and Colorful Gems auto y = lower_bound(b.begin(), b.end(), x); auto z = upper_bound(c.begin(), c.end(), x);

why is z-- but not z = lower_bound(c.begin(), c.end(), x)?