Sulfox's blog

By Sulfox, 5 years ago, In English

1337A - Ichihime and Triangle

Idea: Sulfox

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

Tutorial
Solution by Sooke
Solution by PinkRabbit

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

Idea: Sulfox

Tutorial
Solution by Sooke
Bonus

1336F - Journey

Idea: EternalAlexander

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

| Write comment?
»
5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.net/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?

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

      sorry I mistook something...just forget what I said

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

      forget about the logic.. n^3 dp array won't fit into memory limits

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

      we can define front and back of a string only if it is non empty. front and back are same for an empty string so solve case i==0 saparately .

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

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

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

Is there Chinese solution?

»
5 years 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

»
5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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

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

      This was greedy approach,i think so.

      • »
        »
        »
        »
        5 years 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.

        • »
          »
          »
          »
          »
          5 years 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.

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

    Manan_shah, probably you can contribute to this.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        4 years 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..

        • »
          »
          »
          »
          »
          4 years 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.

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

            ohh, now i got the point. thank you so much

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

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

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

    Video editorial of 635-Div2-C

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

      Thank you sir for your amazing contents and editorials ❣️

»
5 years 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

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

is the note of div 2 E right?

  • »
    »
    5 years 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

»
5 years 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!

  • »
    »
    5 years 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.

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

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

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

Thank you for funny legends!!!

»
5 years 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?

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

    Well, it is simply wrong logic.

    • »
      »
      »
      5 years 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.

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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!

        • »
          »
          »
          »
          »
          5 years 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.

          • »
            »
            »
            »
            »
            »
            5 years 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.

        • »
          »
          »
          »
          »
          5 years 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.

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

            Aren't you?

            • »
              »
              »
              »
              »
              »
              »
              5 years 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...

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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.

        • »
          »
          »
          »
          »
          5 years 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.

        • »
          »
          »
          »
          »
          5 years 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.

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

        This dude needs english classes for babies.

    • »
      »
      »
      5 years 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 :)

      • »
        »
        »
        »
        5 years 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.

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

        kaogu

»
5 years 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.

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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"?

        • »
          »
          »
          »
          »
          5 years 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

          • »
            »
            »
            »
            »
            »
            5 years 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.

            • »
              »
              »
              »
              »
              »
              »
              5 years 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

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

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

  • »
    »
    5 years 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.

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

      Thanks, now i got my mistake.

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

        Could you please explain why z is being decremented?

        • »
          »
          »
          »
          »
          5 years 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.

    • »
      »
      »
      5 years 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 ?

      • »
        »
        »
        »
        5 years 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).

  • »
    »
    4 years 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).

»
5 years 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?

»
5 years 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."

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

»
5 years 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?

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

    i need to know too

    • »
      »
      »
      5 years 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.

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

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

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

A bit different solution for 1336D:

Spoiler
»
5 years 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 :)

»
5 years 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

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

Is there a better explanation for Div1 C ?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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.

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

      Your approach of filling special character made the problem much easier to understand. Thanks for the explanation.

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

      Thank you so much !!!!

»
5 years 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

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

    Is this a sort of blog of yours?

  • »
    »
    5 years 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?

    • »
      »
      »
      5 years 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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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

  • »
    »
    5 years 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).

    • »
      »
      »
      5 years 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

»
5 years 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 :(

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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!

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

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

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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

»
5 years 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?

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

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

»
5 years 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 ???

»
5 years 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?

»
5 years 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

  • »
    »
    5 years 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:(

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

»
5 years 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??

  • »
    »
    5 years 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.

»
5 years 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?

»
5 years 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.

  • »
    »
    5 years 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
    • »
      »
      »
      5 years 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

      • »
        »
        »
        »
        5 years 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.

»
5 years 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?

  • »
    »
    5 years 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 )

    • »
      »
      »
      5 years 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?

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

        yes , sum of two sides greater than third

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

»
5 years 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)

»
5 years 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 ?

  • »
    »
    5 years 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.

»
5 years 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.

»
5 years 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.

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

    Thanks! Much easier to understand and implement.

    In case anyone needs the code — 77121142

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

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

»
5 years 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

»
5 years 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)$$$

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

    how is that straightforward

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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).

  • »
    »
    5 years 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.

»
5 years 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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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.

»
5 years 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 ???

»
5 years 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.

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

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

»
5 years 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.

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

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

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

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

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

Someone please explain Div 2 C briefly.

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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

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

solution for div 2 d is very elegant

»
5 years 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.

  • »
    »
    5 years 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].

    • »
      »
      »
      5 years 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$$$.

  • »
    »
    4 years 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?

    • »
      »
      »
      4 years 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$$$.

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

    Thank's i Got it

»
5 years 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 ?

»
5 years 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

»
5 years 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

»
5 years 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.

»
5 years 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
  • »
    »
    5 years 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.

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

How to solve the bonus part of E2? :(

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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.

        • »
          »
          »
          »
          »
          5 years 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$$$?

          • »
            »
            »
            »
            »
            »
            5 years 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

        • »
          »
          »
          »
          »
          5 years 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)."?

          • »
            »
            »
            »
            »
            »
            4 years 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 years 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

  • »
    »
    5 years 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)
    
    • »
      »
      »
      5 years 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.

»
5 years 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.net/contest/1337/submission/77153692

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

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

»
5 years 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)

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

    Try this:

    1
    1 2 1
    1
    2 3
    5
    
    • »
      »
      »
      4 years 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

»
5 years 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?

»
5 years 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

»
5 years 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

»
5 years 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?

»
5 years 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!

  • »
    »
    5 years 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$$$.

    • »
      »
      »
      5 years 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??

      • »
        »
        »
        »
        5 years 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$$$.

        • »
          »
          »
          »
          »
          5 years 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?

          • »
            »
            »
            »
            »
            »
            5 years 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$$$.

          • »
            »
            »
            »
            »
            »
            5 years 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.

            • »
              »
              »
              »
              »
              »
              »
              5 years 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!

»
5 years 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.

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

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

»
4 years 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!

»
4 years 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)?

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

There was a huge mistake in the tutorial of 1336F - Journey. I have fixed it now. Thanks sys. for pointing out!

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

In problem e1 the soluution has this written on it Build linear basis A what does this mean ?

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

Can anyone help me finding the error as my code is getting wrong ans on test case 6 problem A

My Code

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

nice problem div1A problem

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

I want to take some time to explain the Div2C/Div1A's solution (Linova and Kingdom).

So the tutorial already mentions that we need to get the $$$val_u = size_{u} - depth_{u}$$$ for each node, and then sort the values, such that the bigger ones are first, and select the first $$$n-k$$$ values, and those are the ones that are selected as the tourist spots. Also, the summation of the $$$val_u$$$ for these $$$n-k$$$ values would give us the answer, But why?

So why are we taking $$$size_u$$$?

This is taken, while assuming that all the nodes under the current node will be industries. Now, if our current node is a tourist node, then in that case, each of the industry in the subtree will count this tourist node as one. Therefore we take the $$$size_u-1$$$ value. (The -1 is cancelled out later)

Why are we decreasing $$$depth_u$$$?

All the parent nodes of the current node would have taken the current node as an industry (as per the $$$size_u$$$ calculation). Now, since we are considering the current node as a tourist spot, we need to remove the "industry assumption" values from the total. This can simply be done by counting the number of nodes from 1 to the current node. That will be $$$depth_u-1$$$

The -1s cancel out, so we get $$$size_u - depth_u$$$.

Now this works because the sorted order forces us to go from parents to children. I hope this helps.

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

    can you please explain why this assumption is correct? This is taken, while assuming that all the nodes under the current node will be industries.

    Because it may happen that we assumed that all the subtree will be industries but we did not take all the subtrees

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

      Yes it can be false definitely. That's what the $$$-depth_u$$$ part is for. So you add $$$size_u$$$ assuming that all the nodes under the current node will be industries. Let's say this node as N, whose children we have assumed to be industries.

      Now let's say, when you reach some node A, in the subtree of N, which is to be taken as a tourist spot. In that case, the assumption for N becomes wrong, and you remove need to remove A's contribution from all it's parents. That's just $$$depth_u - 1$$$.

      So this handles the scenario when the node in the subtree is not an industry.

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

Why not a,b,c can be a answer in Problem A? Why b,c,c?

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

what if i do cout << b << " " << c << " " << d << endl;

it should be accepted but shows error