Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

DeadlyCritic's blog

By DeadlyCritic, history, 2 weeks ago, In English,

A. FashionabLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

B. AccurateLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

C. RationalLee :

Invented by DeadlyCritic and adedalic.

Brief Solution
Complete Proof
Python solution
C++ solution

D. TediousLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

Challenge : Try solving problem D for $$$n \le 10^{18}$$$. (no matrix-multiplication)

E. DeadLee :

Invented by DeadlyCritic.

Hints
Brief Solution
Complete Proof
Python solution
C++ solution

F. BareLee :

Invented by DeadlyCritic and AS.82.

Brief Solution
Complete Proof
Python solution
C++ solution
 
 
 
 
  • Vote: I like it
  • +397
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -83 Vote: I do not like it

I appreciate your effort, but this contest was very mediocre. Problemsetting might not be the job for you guys. It was basically Geometryforces, and I'm not good at geometry. Please, no more geometry problems.

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

    If you know you're bad at geometry, study up on geometry and stop blaming the author for using too many geometry problems.

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

      As I know the round has minimum possible non-zero geometry.

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

    I'm not good at CP. Please no more CP problems. Only 1+1 problems.

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

    It sounds like "I don't know geometry, dp, binary search so don't make contests with such problems". Moreover, the only task there with geometry is A...

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

    O looks like a circle. All statements have at least 1 occurrence of the letter o in them. That's the most geometryforces round I've ever seen!

»
2 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

faast tutorial..

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

    Is there anyone who can explain me the second problem. I can't understand it properly.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 4   Vote: I like it +2 Vote: I do not like it

      In second one you are given a binary string Carry out the following steps ; .

      1.Select a 1 such that there is immediate 0 next to it
      2.Delete either 0 or 1

      . Repeat the above two steps and continuously reducing the string. There will exist a optimal choices on part 2 such that the string is reduced to smallest length possible and if such lengths strings are many you need to output the lexico wise smallest.

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

        Nice!!! Thanks

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

        .

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

          thnx for pointing out .. its the same logic we are just searching for (10) basically

          # Consider the example in Q

          11001101 → 1100101 → 110101 → 10101 → 1101 → 101 → 01

          # Let me explain
          • here we found 10 pattern at 5th index so we removed 1)
          • Again we found 10 at 1st index ( taking in account of index change due to prev step) then we removed 0
          • Again we found 10 at 0th index then we removed 0
          • Again we found 10 at 1st index then we removed 1
          • Again we found 10 at 0th index we removed 1
          • No match found for 10 so terminated
          Note
          • If you take another choice of removing 1 or 0 in any steps above you'll end up with a larger string by length or by lexico.
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can't erase any charecter (neither '0' nor '1') from the input string until you get a '1'.So,you must print all '0' from the beginning.If you get '1' then stop.Now starting from this index of '1' find the position of the last '0'.Now there are two condition=>Condition::1)If there is no '0' then you can't get any index to erase satisfying the problem's condition(s[i]='1' and s[i+1]='0').So,you have two print the whole remaining string(as shown in sample input-output:query-1)......Condition::2)If there is at least one '0' then starting from the idex of the first '1' you can erase all the charecters till the last position of '0'. As stated in the problem you have to print the lexicographically smaller string.So,when the string seems to be "10" then you have to erase the '1'. Summery::1)Print all '0' from the beginning till you get '1'. 2)Print the last '0'(if there is '0')then,all the remaining '1'(if there remains '1').

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

      This is the Video Tutorial for B https://youtu.be/PYPoOCav4Jk

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

    Video solutions to all problems are available at the end of my screencast, for people who are interested.

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

      Please keep doing these videos.. they are really helpful.

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

      One for all!!Now I don't need to watch different video as I get everything in one place!!!

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

      It's really helpful. Thanks.

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

      The quality(explanation) of video forced me to press the bell icon..keep doing this brother .Take love.

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

      Thank you. Please keep doing this.

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

    A better way to solve B is to find the first occurrence of 1 and the last occurrence of zero, as you can always erase all the elements from the first 1 till the last zero by deleting one of 0 or 1. You can see my submission for reference.Thankss!

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

      Why did you take fo!=mod && lz!=mod ?

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

        That is to make sure that cases like this pass: 5 11111 Peace!

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Really enjoyed the problemset!

»
2 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

In pD: I saw some people use max even under mod 1e9 + 7. Why is that correct.

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

    Because the numbers you take the max of are very close to each other, so if you assume that the dp values are almost random the chance of there being an error in $$$n \leq 2 \cdot 10^6$$$ is pretty small.

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

    It seems like there is no $$$n \le 2 \cdot 10^6$$$ such that $$$dp[n][0] \equiv 10^9 + 6 \mod (10^9 + 7)$$$, since otherwise the answer for $$$n = 2 \cdot 10^6$$$ will be different

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

      Will you please elaborate what are you talking about? Because i solved D and did not have any such doubt but i want to know?

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

        max(9,11)%10=11%10=1 , but max(9%10, 11%10)%10=9. That's why it "looks" possible that if you always keep the answer mod-ed, taking the max might create problems. That's what people tried to prove/disrove above. I hope it helps.

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

    And I was so afraid to do that!! Wasted an hour and then ended up doing the same thing. Lowkey felt it was going to fail systest.

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone help in knowing why B was so hard for me? I didn't struggle on C as much as I did in B. Please help me realize what's wrong in my practice and thought process.

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

    You should first work out a sound algorithm for every question and then you can code! I hope you use pen and paper to help visualize stuff?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

D can be solved with matrix exponential as well. And one can make the constraint to be n <= 1e9 to force using fast matrix power.

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

    I am unable to understand this point. Could you pls share some resource to digest your point

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

    how will you handle the case if i%3==0 then dp[i]++

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

      You can take vector $$$a_k = [x_{3k}, x_{3k+1}, x_{3k+2}, 1]$$$ and derive formula for $$$a_{k + 1}$$$ in terms of $$$a_k$$$

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

    Is this method same as what is used for finding Fibonacci numbers ??

    I think it can be done only if we have the relation:

    dp[i] = dp[i-2]*2 + dp[i-1]

    But we also have additional constraint:

    for every i divisible by 3, dp[i]+=4

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

    The best I could get is a $$$10\times 10$$$ matrix (84825762), which might TLE on $$$n\leq 10^{9}$$$ and probably TLE on $$$n\leq 10^{18}$$$, with $$$10^4$$$ testcases. Can it be done with a smaller matrix?

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

      A $$$4 \times 4$$$ matrix should work, but matrices doesn't help with solving the challenge, the intended solution works in $$$O(1)$$$ for each test case. (considering $$$x^y$$$ to be calculated in $$$O(1)$$$)

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

        3*3 can do (in the comment)

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

          Sure, I can't count, my matrix was $$$3 \times 3$$$ as well.

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

        Yeah it's not for solving the challenge; I just need to work on my matrix expo skills lol

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

      Can you do it with a 5x5? You need just a linear combination of dp[n-1], dp[n-2], n%3==0, n%3==1, and n%3==2, in order to determine dp[n], right?

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

        Your method seems cool too!

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

        Oh, so you cycle the extra addition instead of the whole equation. That's neat! Edit: implemented this here 84829787

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

          Can you explain what does the matrix represent? How does the values of matrix a are filled?

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

          Can you explain how do you use the (i%3) condition in your linear relation?

          Sorry if it's a trivial question.

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

            If you write out the matrix on paper, you'll see that each time you multiply some initial vector by the matrix, the last 3 entries will shift cyclically. You can use that to add a value every 3rd step.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it -7 Vote: I do not like it

            dp[n]=2*dp[n-2]+dp[n-1]+( n%3>0 ? 4:0); dp[n]%=1000000007;

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

    T =
    0 1 0 dp[i-1]
    2 1 0 dp[i]
    0 0 1 1

    T3 =
    0 1 0 dp[i-1]
    2 1 1 dp[i]
    0 0 1 1

    T3 * T * T

    Hope this is clear enough :)

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

      maxwill Using your relation, I came up with a formula for when n%3==0,1,2 respectively, but there seems some mistake which I'm not able to figure out.

      [T_(n-1)]     T^(2*(n-3)/3) * T3^((n-3)/3) * [0]
      [T_(n)  ]=                                   [1]
      [1      ]                                    [1]
      

      The above applies when n%3==0, and similarly I've worked out other two cases, but idk why this starts giving wrong output from 9 onwards. Is there some mistake in this relation? How do I correct it. I've spent hours.

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

        (ABC)^n != A^n B^n C^n. And your T is ambiguous.

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

          T_n is the nth term. T and T3 are the matrices {{0,1,0},{2,1,0},{0,0,1}} and {{0,1,0},{2,1,1},{0,0,1}} Final answer of any n will be n*4. I haven't made any mistake in calculating power of the matrix, I've checked that function. I don't know what am I missing x

          UPD: I was doing a blunder in multiplication. Therefore, changed the matrix. Now, rather than using multiple 3X3 matrices, I am using one 4X4 matrix and finally got AC. 84893815.

          I still wonder, how do we solve it using two 3X3 matrices.__

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

            Your program is doing TTT*...*T3T3T3*x
            While the answer should be T3TT*...*T3TT*x

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

    That is a force online solution, which would've make it a bit much more harder :)

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

      I don't think so. Whoever can come up the recurrence AND knows matrix exponentiation will definitely be able to implement it quite quickly. In fact, I tried the mat expo first, only to notice later that it wasn't necessary. A little harder, yes. But still, well within the range, I believe.

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

        Maybe, but I messed up with recurrence (mod 3) part and didn't think about matrix expo.

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

WOW!! the editorial came fast!!

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

a great contest!

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

what's wrong with my solution?

DIV 2/C

solution link : https://codeforces.com/contest/1369/submission/84811103

»
2 weeks ago, # |
Rev. 2   Vote: I like it +90 Vote: I do not like it

Lee

»
2 weeks ago, # |
  Vote: I like it -54 Vote: I do not like it

How the fuck is the editorial blog uploaded 5 hours ago when the contest started 2.5 hours ago !!?

»
2 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Did you really expect the contestant to prove C during the contest, or just do a Proof By AC? I mean I got 3 WA trying different greedy algos without proving them and I knew that almost everyone submitted without being completely sure of the proof.

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

    Lol is there something to prove? It was obvious for me

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

    I did proof it in $$$2$$$ minutes, but my English sucks so It became so long.

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

    I think the proof is quite intuitive. The author's explanation is too wordy.

    Notice that

    • We can break down the problem into finding the $$$\sum_i MAX(friend_i) + \sum_i MIN(friend_i)$$$

    • For some large $$$a_i$$$, it is easy to use it to maximize the $$$\sum_i MAX(friend_i)$$$ by giving it to a person with no gifts. This suggests for each person's initial gift, we should be handing out one gifts to each person in decreasing order

    • In order to maximize $$$\sum_i MIN(friend_i)$$$ as well, we notice that $$$MIN(friend_i) == MAX(friend_i)$$$ if $$$w_i = 1$$$. So, we reorder our gifts so people with $$$w_i = 1$$$ get the largest gifts.

    • Because of the way the MIN function works, it' doesn't make sense to give someone many gifts with high $$$a_i$$$, then one gift with low $$$a_i$$$. Similar to last point, it's more efficient to give the better gifts to friends with smaller $$$w_i$$$. This way, we burn less of the good gifts on people. This suggests that we should use a greedy solution to fill the remaining $$$w_i$$$ for each friend and we should fill the friends with smaller $$$w_i$$$ first, with the largest unused $$$a_i$$$.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -55 Vote: I do not like it

      This is a garbage proof.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +37 Vote: I do not like it

        The purpose of a proof is to convince someone that a solution is correct.

        Can I spend 10 more minutes to come up with a more rigorous proof? Probably. Do I want to spend 10 more minutes to do it during a contest? Probably not.

        And since we're being evaluated on our ability to code and not on our ability to prove our solutions, using non-rigorous proofs is the correct way to go as long as the proofs can convince OURSELVES that a solution is correct.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -53 Vote: I do not like it

          This is not an unrigorous proof because it is not anything resembling a proof.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -53 Vote: I do not like it

          But don't reply now, I have got no patience.

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

          In almost every wrong greedy you can come up with something to convince yourself. The purpose of the proof is NOT to convince, the purpose of the proof is to give 100% confidence. Convince seems a weaker word to me, I am usually convinced by every other wrong solution.

          I don't feel good about your proof. For example, why try to maximize MAX for each friend first? Can increasing MINs at the cost of some MAXs be better? Of course, the answer is NO. Simply, because here, the algorithm is indeed correct. But your proof is a bit too handwavy to address many of the critical issues.

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

        Ok, how about this proof? First, you sort your integer Array from largest to smallest and start distributing to friends from the front. also you sort your friends from smallest to biggest by w.

        the first priority friend is the friend with w = 1. because if you give to that friend, the happiness is boosted twice. After giving the integers to that friends with w=1, the second priority is maxing the MAX of the leftover friends. that way, you dont waste your big numbers between MAX and MIN of the friends. you distribute your numbers one by one to your friends and max their MAXes.

        then you need to start wasting your numbers, the way to do it is starting with friends with small w so you dont waste as much numbers.

        end?

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

          This is an excellent proof

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

          There is no point of considering the case when w = 1 , just sort the array of integers in non — ascending order and distribute the maxes among K friends. That way, w = 1 case already got handled. And then continue with your process.

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

      The first bullet point in your proof was the main thing I needed to realize to solve this problem.

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

Stucked at B for a while? Thinking what should i remove 1 or 0 in the middle part? Can someone gimme idea?

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

    The key intuition here is that you cannot change the leading 0s or trailing 1s. Anything in between, however, can be converted into a 0 in some way, so you don't need to remove anything. All you have to do is keep the leading 0s and trailing 1s, and if elements remain in the middle, add a 0 in between.

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

    the 0 is added is the 0 right before the trailing 1s in original string

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

    There were just certain observations that

    1.You can't change leading zeros and trailing 1s
    2.Anything in between can be transformed to 1 or 0

    Like *****110010**** — ****10010**** — ****1010**** — ****110**** — ****10**** — ****1**** or — ****0****

    3.But since we need lexico wise smallest we'll take 0
    4. Hence our answer becomes (leading 0s) + 0 + (trailing 1s)
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this out for solution to C

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

An ideal contest with ideal timing and ideal problems! Liked it!

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Fastest system testing I have ever seen.

»
2 weeks ago, # |
  Vote: I like it +65 Vote: I do not like it

The problems were LoveLee!

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

Wow. What an editorial. I honestly felt like I made some problems harder for myself than they actually were LOL

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

I will add implementations soon.

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

Tutorials are so fast , Thank YOU !

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

In problem D I am not getting where I am making mistake Can some one help https://ideone.com/RyTb1E

»
2 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

unrated

»
2 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

O(N + M) solution for E. We need to make the observation that as long as the degree of a node is not greater than the value of the node, it is always optimal to remove it as late as possible. Then we can run a process similar to topological sort to check if we can remove all edges.

Link: https://codeforces.com/contest/1369/submission/84803734

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define readl(_s) getline(cin, (_s));
#define boost() cin.tie(0); cin.sync_with_stdio(0)
 
const int MN = 200005;
 
int n, m, cnt[MN], freq[MN], vis[MN], rem[MN];
pii a[MN];
vector<pii> adj[MN];
vector<int> v;
 
int main() {
    boost();
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> cnt[i];
    for (int i = 1; i <= m; i++) {
        cin >> a[i].f >> a[i].s;
        freq[a[i].f]++; freq[a[i].s]++;
        adj[a[i].f].push_back({a[i].s, i});
        adj[a[i].s].push_back({a[i].f, i});
    }
    queue<int> q;
    //for (int i = 1; i <= n; i++) printf("%d ", freq[i]);
    for (int i = 1; i <= n; i++) if (freq[i] <= cnt[i]) q.push(i);
    while (q.size()) {
        int cur = q.front(); q.pop();
        vis[cur] = 1;
        for (pii nxt : adj[cur]) {
            if (!rem[nxt.s]) {
                rem[nxt.s] = 1, freq[nxt.f]--; v.push_back(nxt.s);
                if (freq[nxt.f] <= cnt[nxt.f] && !vis[nxt.f]) q.push(nxt.f);
            }
        }
    }
    int mis = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) mis++;
    if (mis) return 0 * printf("DEAD\n");
    printf("ALIVE\n");
    for (int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]);
 
    return 0;
}
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Nice. :)

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

    this is clean

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

    Thanks for the solution. I have a doubt though. instead of checking !rem[nxt.s] why can't we just use !vis[nxt.f]. I tried it didn't work but couldn't understand why.

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

      Hopefully you see why with this case:

      2 1
      2 2
      1 2
      

      Edit: Sorry, this case does not disprove your point due to the weird way I checked the vis array. However, you must realize that edges should still be removed even if both nodes it connects are visited :)

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

        I got the case See the 5th test case. The logic that we need not remove an edge if both nodes are visited is perfectly alright. But what is happening is if we check only that we will be repeating operations for the same edges because queue may contain multiple entries of the same node. suppose you have three nodes between 1 and 2. Then if you start from 1, you will push 2 into the queue 3 times. Now when you iterate for 2 if you don't check the edges then you will loop 3 times for each edge. Hence you get an error. Btw, thanks for looking into it.

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

          Precisely. The duplicate entries are caused by the abnormal placement of the vis[cur] = 1 line, which in turn causes the error you mentioned. Please see the more accurate implementation here, where the case I mentioned would effectively break if you checked for !vis[nxt.s] instead.

          I guess the lesson to be learned here is to always implement as precisely as possible, otherwise debugging may become a lot harder :D

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the great quality questions! I really enjoyed solving it :) The difficulty gradient was so good for me ;)

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

Fast system testing as well as tutorial. Seemed that it was programmed that tutorial will be uploaded automatically when the system testing is over. :D

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Extremely well written tutorial,super easy to get

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Special thanks for hints in problem E, actualLee they are better than the complete solution.

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

Really really cool problemset. Thoroughly enjoyed. Kudos!

»
2 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

ezgif.com-add-textccba5ace14bf767d.gif.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it
    while(t-- > 0) {
        int n = sc.nextInt();
        String s = sc.next();
        int left = 0;
        int right = n - 1;
        while(left < n) {
            if(s.charAt(left) == '0') {
                left++;
            }
            else {
                break;
            }
        }

        while(right >= 0) {
            if(s.charAt(right) == '1') {
                right--;
            }
            else {
                break;
            }
        }
        String result = "";

        for(int i = 0; i < left; i++) {
            result += "0";
        }
        if(right + 1 != left) {
            result += "0";
        }
        for(int i = 0; i < n - right - 1; i++) {
            result += "1";
        }
        System.out.println(result);
    }

B. TLE on test case 9. How to optimise it?

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

Can someone please tell me why am i getting WA on pretest 2 in C : Link to code

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

nice contest.

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

An easy greedy strategy for B:

Iterate over the string from the end, and for every "10":

  • Delete all consecutive 1s before it
  • Delete all consecutive 0s after it
  • Delete the "1" from the "10"

Solution here.

»
2 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

rated or not?

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

Nice problemset!

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

Fastest system testing as I have seen

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

You need to multiply (i % 3 == 0 ? 1 : 0) part in D's brief solution by 4

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

    cause as you can see after every 3 there is one extra claw that is getting added to the tree like in the case of N being 6 answer should be ans[5]+ans[4]*2 plus that extra claw . btw I don't own this image

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

Can anybody explain how we form the graph in problem D? I read the problem statement multiple times but couldn't figure out how they made the Level 4 graph. :(

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    1. Add one child to nodes with 0 children
    2. Add 2 children to those nodes which already have one child
    3. And if the node has already more than 1 child, we don't need to add any more child to it.

    So,3rd level graph is given int the question

    Nodes with no children -> 3,5,4 Add 1 child to these(8,10,9 respectively) , Nodes with 1 child -> 2 Add 2 children to it(7,6) ,

    No need to add children to 1 as it already has more than 2 children

»
2 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Man. Div. 2 A's are getting harder and harder these days. Most people will probably intuit the right answer, but I usually prove before submitting, and some recent Div. 2 A's have very non-trivial proofs.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved D using normal 2D dp,

dp[i][1] = dp[i-1][0] + dp[i-1][0] + dp[i-1][1] and

dp[i][0] = max(dp[i-1][0],dp[i-1][1]) + max(dp[i-1][0],dp[i-1][1]) + max(dp[i-2][0],dp[i-2][1])

I created a DS to store quotient and remainder to compare modulo values

My solution: Link

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

Can someone explain why my solution is giving WA on tc2 Link: 84818110 I am unable to identify any loop holes

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow, I made solution to problem D that is different from editorial https://codeforces.com/contest/1369/submission/84820772 I used cnt[i] — count of added vertices in i level, and lol[i] — answer for i level

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

Very Good Contest and Fast Editorial

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

Lee is everywhere :D

»
2 weeks ago, # |
Rev. 2   Vote: I like it +66 Vote: I do not like it

Here's an easier analysis for A. The exterior angle (diagram below) of a regular polygon of n sides is 360/n
In order for one side to align to the vertical and another side to the horizontal, the sum of the exterior angles of some k consecutive sides must equal 90.

We must have
(360/n) * k = 90
k = 90*n/360 = n/4
So n must be a multiple of 4 for such an integer k to exist.

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

    I came up with the same proof, but it was harder for me to write it in English. Thanks for doing it instead of me. :D

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

      My pleasure. I wish coming up with solutions quickly was easier for me than writing proofs :D

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

can someone give me a link or explain to me the proof to A as i don't really get the editorial which is my bad :)

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

https://codeforces.com/contest/1369/submission/84793979

could someone help me with this submission.dont know why is this wrong, i guess its the same approach as in editorial

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

    Try

    2
    4 2
    4 3 2 1
    3 1
    4 2
    4 3 2 1
    1 3
    

    Should it matter if $$$w = [1, 3]$$$ or $$$w = [3, 1]$$$ ?

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

Great contest with perfect Timing and as well as excellent problem set.

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

Is there a greedy solution for D.TediousLee

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

I have done the exact same thing , why am i getting wrong ans verdict on c qn https://codeforces.com/contest/1369/submission/84794143

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

Feeling Very Sad,this is the first time i have solved 3 problems in div 2. But could not submit C because of the power supply went off for about 30 minutes.

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

So fast tutorial!Thank you Codeforces.

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

DeadlyCritic In problem E, the last sample test case:

INPUT:  
4 10   
2 4 1 4  
3 2  
4 2  
4 1  
3 1  
4 1  
1 3  
3 2  
2 1  
3 1  
2 4  
OUTPUT:  
DEAD  

Suppose, following is the ordering in which Lee's friends eat[u -> v means (u-th friend eats v-th food)]:

9 -> 3
6 -> 1
4 -> 1
8 -> 2
7 -> 2
1 -> 2
10 -> 2
5 -> 4
3 -> 4
2 -> 4

My answer:

ALIVE
9 6 4 8 7 1 10 5 3 2
Why is this ordering wrong?

Please help!

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

    when friend i goes to kitchen, he tries to eat x_i AND y_i, even the x_i is exists

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

      so, the 9-th friend eats not just 3, but 1 too

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

      Oh, Okay! So, if both favourite foods of the friend exist, he/she will eat both of them? You mean this, right?

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

        It was clearly explained in the statements =(.

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

          I am sorry but I thought the same too ... Except for that it was a great problemset, looking forward to more contests by you

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

            We were expecting some people to thing like this, so we spent quite a long time to write the statements as clear as possible, I'm sorry that it was not as good as I expected.

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

i really don't see how the proof for problem D says that we should use i % 3 and that magic while computing the answer?

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

    Let the answer for RDB of level $$$i$$$ be $$$dp_i$$$ . Also an RDB of level i is connected to two RDB of level $$$i-2$$$ and one RDB of level $$$i-1$$$.

    1. Note that it is beneficial to ignore the root vertex of RDB of level $$$i$$$ if $$$dp_{i-2}$$$ requires the root to be included. Because, at the cost of adding one claw of $$$i-1$$$, we'll lose two claws, one for each RDB of level $$$i-2$$$.

    2. For $$$dp_{i-1}$$$, it doesn't matter whether we include the root or not because either way no extra claw gets added or removed.

    3. Also if both $$$dp_{i-1}$$$ and $$$dp_{i-2}$$$ doesn't require their root to be included to get their respective values, we'll add root of RDB of level $$$i$$$.

    Point 3 gives an idea on whether to include root or not in point 2. That it is if including the root doesn't matter in getting $$$dp_i$$$, we'll always not include it. Because in doing so, we may get a better answer for $$$dp_{i+2}$$$. Say we'll include root for $$$i$$$, then we can't (or rather shouldn't) include root for $$$i+1$$$ and $$$i+2$$$, but this implies we'll include root for $$$i+3$$$. In the question, we have to include root for $$$i = 3$$$, so we have to include root for $$$i=6,9,12,..$$$ as well. That is where that $$$i$$$ % $$$3$$$ comes into play.

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

      Great explanation, thank you, idk how didn't that cross my mind.

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

Is there any way to see full test case, my code failed system testing in B but I can't figure out on which test case: https://codeforces.com/contest/1369/submission/84767454

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

Why this doesn't work for D? I find for every level how many more(new) vertices with 3 children were added from previous level and then do dp[i]=dp[i]+dp[i-2]. Solution: https://codeforces.com/contest/1369/submission/84822790

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

    You are saying you count new vertices but you are doing dp[i][2] = dp[i-1][2]+dp[i-1][1]. So it is getting added cumulatively.Also for ith layer you need to do dpp[i] = dp[i][2]+dpp[i-3]. You can see this after drawing some trees.

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

      Yea dp is adding cumulatively but dpp stores the added vertices as they come only from dp[i-1][1].

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

https://codeforces.com/contest/1369/submission/84819647 Can anyone tell me whats wrong with my C solution. First I sorted the interger lee has in descending order.Then I sorted w array in ascending order. Then I took the case for when w[i]=1. I gave them maximum value.Then I disitributed interger to W[i] one by one. It will be a great help if anyone call tell me my mistake

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

What's wrong with my solution ? Question B ; My solution : https://codeforces.com/contest/1369/submission/84814815

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why there are not the codes for the solutions in the editorial?

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

    I'm working on it, I have a very bad headache right now so I'm pretty slow.

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

In D can someone explain why is 1 added if i is divisible by 3

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Because that gives an AC !

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

    Because when i%3 u can use the top claw (1;2;3;4)

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

      Oh damn, can you also explain how did you reach to this in the contest? What was your approach to the question?

      Thank you!

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

        Suppose you used the root for some x. Now, x will be a child of both x+1, and x+2 so, in either of them, you can't use the top claw (because it's child is x and it's root has been used already). Now, for x+3, it's children will be x+1, and x+2 whose roots are free and you can use the top claw in this case. It's a period of 3, just check where it starts.

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

        Here's my thought process in this problem:

        If you look at the case n=4 closely, you'll see that the tree RDB(4) is actually composed of a root node linking to 2 instances of RDB(2) and an instance of RDB(3).

        Now, because of this, we might start to think that a[i]=a[i-1]+2*a[i-2]. This formula holds true for n=5, but doesn't for n=6 if you check by hand. Why is this? It turns out that, again, checking by hand, in the case n=6 we can use the top claw.

        Again, we think about when it is possible to use the top claw. Clearly, when n=4 and n=5 we couldn't use the top claw because we did that when n=3. However, when n=6, we can use the top claw as we did not when n=4 and n=5.

        We see that we can use the top claw in the case n when we didn't in the case n-1 and n-2. Seeing as 3 is the first n to allow this, we conclude that we can use the top claw if n is divisible by 3.

        Therefore we have the above formula: a[i]=a[i-1]+2*a[i-2]+4*(i%3==0).

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

          This was very helpful. Thanks a lot!

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

question B sucked my whole contest.

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

hi guys try these video solutions ->

Problem A

Problem B

Problem C

Problem D Tried to explain graphically how DP is working :)

Hope it Helps.. :)

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

I accidentally used Ideone on public settings and someone copied and submitted the same code int this contest and now i received a system email regarding the penalty for this. Can someone guide me as to what should i do. This is the link of my submissions https://ideone.com/qDpu3b

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

simple and clear

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Nice way of writing editorial...!!! DeadlyCritic

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

Implementations are out, sorry Python solution for D is missing yet.

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

    Just volunteering:)

    python code for D
»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For pB I tried to use a "more greedy" approach, which consisted on going backwards on the string and once I had a zero I would starting deleting ones until the last one. Then I looped again though the string, starting from the first One and deleting all zeros that followed, except for the last, which was kept and the One deleted. It ended up being pretty messy, but it worked, even tough I didn't had time to submit it during the contest because of some stupid bugs. Here is my solution, you won't have a good time looking at code(it is pretty messy as I said), but here it is: 84823891

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

https://codeforces.com/contest/1369/submission/84825830 is there anyone who can tell me why I am getting Memory limit exceeded on test 2

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

for problem D,someone please tell me why this dp relation is wrong,i made two cases if we color root and if not, v[i]=max(((2*v[i-2])+v[i-1]),((4*v[i-4])+4*v[i-3]+v[i-2]+4))

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

Can someone help me figure out why am I getting a WA in Problem C.

Link to my submission

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Even after giving so many contests, I can't solve div2 C problems. I can solve them in upsolving but I can't solve them during contests. Can anyone please help me to overcome my this problem, please even single advice will help me. Btw here is the link to my upsolved div 2 C problem. I am expecting help from the community. Help me.

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

What's wrong with my solution? 84826635

I use a 3d dp to keep a count of vertices with 0, 1 and 3(the outer ones, as they will only contribute to the next state) children. Then I say that:

dp[0][i] = (2*dp[1][i-1]%MOD+dp[0][i-1]%MOD)%MOD;
dp[1][i] = (dp[0][i-1])%MOD;
dp[3][i] = (dp[1][i-1])%MOD;

I fill the dp till i = 2000002 using the above relation. And finally output (dp[3][n]*4)%MOD

There is some mistake in this logic. But I'm not able to figure out where and how to fix it?

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

    you can't take all claw. In n'th level if you have total m claw then you can take less then m claw. Because some claw's overlap with another claw. see my solution.

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

      Can you elucidate it a bit, please? I don't understand what is the use of calculating dp[i][3], in your solution? And how exactly are you working out states in sol[]?

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

        okay.in my solution here,

        dp[i][0] is the number of nodes which has 0 child in i'th level, dp[i][1] is the number of nodes which has 1 child in i'th level, dp[i][3] is the number of nodes which has 3 child in i'th level, at the same time dp[i][3] denotes total number of claws.

        in sol[] array I calculate the solution for n'th level in sol[n].

        in my solution,

        sol[n]= sol[n-3] + number of new claw added in n'th level * 4 .

        ** claws which were added newly in n-1 and n-2 th claw are overlapped.So i didn't count them.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you provide a test case where this method would fail..?

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

B. Accuratelee Explanation Video >>> https://www.youtube.com/watch?v=EoJetsWa9k0

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

I can't understand problem F. Why in this sample case

2
1 9
4 5

The output is

0 0

?

I thought, these scenarios is possible:

  • 1 -> Lee 2 -> Ice Bear 4 -> Lee 8 -> Ice Bear 16 (Lose) -> Next Round 4 -> Ice Bear 5 -> Lee 6 or 10 (Lose)

  • 1 -> Lee 2 -> Ice Bear 4 -> Lee 8 -> Ice Bear 9 -> Lee 18 (Lose) -> Next Round 4 -> Lee 5 -> Ice Bear 6 or 10 (Lose)

Hence Lee can win and can lose too.

Where did I go wrong? Or maybe, what does it mean by "can be the winner independent of Ice Bear's moves or not" and "can be the loser"?

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

    Here "can be the winner" means that Lee has a strategy where he will definitely win and Ice Bear can't prevent this. Similarly for "can be the loser".

    Indeed, the problem statement is a bit ambiguous.

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve D for n <= 10^18 without matrix multiplication?

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

https://codeforces.com/contest/1369/submission/84784718 O(N + M) solution for E. It's basically finding an ordering such that if you use that order to direct the edges, out_degree[i] <= a[i]. So you can code it in almost the same way as you would code finding a topological ordering.

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

hello sir, the editorial is awesome and one more thing you provided all code in python too. Thanks a lot sir

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

E question can be solved using data structures

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorial with complete proof is good. It helps me with my poor math......

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

Div2D : Can someone please explain me why are we adding 1 extra claw every 3 levels?

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

Thank you for amazing contest and detailed tutorial!

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

I have a better solution for D(which is close to phrasing the question in another way),

you can think of nodes in 3 — levels

level1 — it is just one node without any children (when it moves to level 2 it gives rise to 1 another node)

level2 — it is node with one child (when it moves to level3 it gives rise to 2 other nodes)

level3 — this node will be our matter of interest which won't give rise to any other node but it signifies atleast one claw(4 nodes)

you can compute level1 ,level2 ,level3 nodes for height-MAX_n using simple dp

level3[i] = (level3[i-1]+level2[i-1])%MOD

level2[i] = level1[i-1]

level1[i] = (level1[i-1] + level2[i-1]*2)%MOD

now precompute all answers for 1 <= i <= 2* 10^6,

which is easy to compute using simple observation, for some i , ans[i] = (ans[i-3] + level3[i] — level3[i-1])%MOD

which means the, if you include claws which changed from level2 to level3 during transition of height i-1 to i , you cannot include nodes which became level3 at height i-1 but you can add nodes which became level3 at height i-2 but not at i-3 ...so on (which is just ans[i-3])

now output ans[height]*4

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

[video editorial for third question] — (https://www.youtube.com/watch?v=5V-RiprjfJQ)

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

In the announcement of the Contest, Author should have written in the name of Lee as its heading.Lol!

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

For question C, can anyone please tell me why this solution is giving wrong answer and why the other one is being accepted. They both are doing the exact same thing.

Wrong Solution — https://codeforces.com/contest/1369/submission/84832565 Right Solution — https://codeforces.com/contest/1369/submission/84832850

Thank You!!

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

Video Solutions for A B C Hope u guys like it :)

Problem A:

Problem B:

Problem C:

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice explanation for solution B.

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

In problem E, I still can't figure out why the situation where si>wi for all i has no solution after I read Complete Solution, could someone explain it in more detail?

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

    The easiest way to look at it is that in this situation you won't be able to fix the last friend in the permutation. Suppose we fix some friend as the last one in the permutation with food choices as (x,y) , now there will be 0 x left and 0 y left when it is his/her turn because sx-1 times people have eaten X before him and as sx>wx , hence we will have 0 'x' left and same argument for 'y' , so there cannot exist any last friend which implies there is not solution.

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

@DeadlyCritic Apparently the naive n^2 AC's in java for B: 84798072

I guess the moral of the story is make n 3e5 in the future :(

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

    This is not n^2. It's linear.

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

      ArrayList.remove() is O(n) and that is called O(n) times, so it is n^2.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        Yes but it depends from which index we are removing. We say it's O(n) because we need to shift the elements after the index of removal. But here we can clearly see that this person is removing either the last element of the list or 2nd last. So in the worst case time taken will be O(2n) not O(n^2). :)

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

          That's not true. If the string is 100000... then they are removing the second element each time, so it is n^2. You see this by running it locally on a 1 followed by 10^6-1 0s and it will take forever.

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

            Yes you test case is right. It will give TLE. Sorry!. but this is true best complexity for removal is O(1) when we remove from the last index. You can see this

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

              Yeah, I know, I'm a java main. My point is that this code is the n^2 and AC's anyway even though it shouldn't because the max n is too small.

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

    Interesting, thanks for letting me know.

»
2 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

worst D in a contest ever. Really stupid.

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

Could you please in Problem F, elaborate how did you conclude that

$$$w_{s,e} = w_{s,\frac{e}{4}}$$$
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because whoever wins that game gets to play in (e / 4, e / 2], thus wins.

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

For problem D, consider the following dp: let a[n] be the answer if we color the root, and b[n] be the answer if we do NOT color the root. They obey the recurrence given in the code below. Then the solution is max(a[n], b[n]). But this does not coincide with the results using the code from the editorial. What am I missing?

int N = 20;
vector<ll> a(N+1); //use root
vector<ll> b(N+1); //do not use root
vector<ll> c(N+1); //editorial
a[2] = 4; b[2] = 0; c[2] = 4;
for(int i=3; i<=N; i++){
    a[i] = 2*b[i-2] + b[i-1] + 4;
    b[i] = 2*a[i-2] + a[i-1];
    c[i] = 2*c[i-2] + c[i-1] + (i%3==2) * 4;
    cout << i << " " << max(a[i], b[i]) << " " << a[i] << " " << b[i] << " " << c[i] << endl;
}
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because you are thinking $$$unrooted_n = rooted_{n-1} + 2*rooted_{n-2}$$$. This is not correct. $$$unrooted_{n-2}$$$ might be better than $$$rooted_{n-2}$$$. In other words, for $$$unrooted_n$$$, you have the capability to take the children rooted, but it is not mandatory. You are making it mandatory. This wrongful enforcing causes the problem.

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

Can anyone explain the reason behind adding (i%3==0) in problem D?
The explanation seemed a bit less explanatory! (and without any pictures)
I almost figured out the solution during the contest except this part :\

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

Can anyone please explain me the approach of problem D? Thanks :)

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

    If you start constructing the tree, you will find a pattern.
    The tree of level "i" will have a subtree of level "i-1" in the middle and 2 subtrees of level "i-2" on the 2 sides. The structure will be exactly the same as obtained for levels "i-1" and "i-2".
    Thus, dp[i] = dp[i-1] + 2*dp[i-2] + (i%3==0)
    The last part comes from the fact that after every 3 steps, the root claw becomes available to use.
    Credits for the explanation of the last step: anshumankr001

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

what's wrong with my solution of C? 84837182

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Small improvement of tutorial's C code. If you want to sort array in descending order, instead of sort and reverse (also you could write std::reverse), you can use sort(v.rbegin(), v.rend()) for vectors or sort(a, a+n, greater) for arrays

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

I solved problem D by keeping count of nodes with 0,1,3 children. The claws (nodes with 3 children) at level n-3 do not overlap with the bottom most claws at level n and can simply be added to the answer of level n . The bottom most claws will contribute 4 yellow nodes each. If we keep track of how many claws there are at level n we can find our answer.

For every n counts are updated as -

cnt_0[n] = cnt_0[n-1] + 2 * cnt_1[n-1]
cnt_1[n] = cnt_0[n-1]
cnt_3[n] = cnt_1[n-1]

ans[n] = cnt_3[n] * 4 + ans[n-3]

84837417

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

Can someone please explain why my code for C doesnt work?

Link to code -> (https://codeforces.com/contest/1369/submission/84837647)

Explanation -> I first sorted the array "a" in descending order, and "w" in ascending order.

Then i calculated the sum of all elements in a. Now if some w[i]=k,(k>1) then we do not take into account (k-2) elements in the array a. For eg if w[i]=3 then one element is not added to the answer, only the maximum and minimum ones are.

So i calculated how many elements are "lost" this way in the variable lose.

Now to find the optimal answer, the "lose" number of elements must be subtracted from the sum of all elements, starting from the second smallest element (since the smallest element has to be added to the answer at some point since it will be the minimum of any subsequence it falls in).

Also if w[i]=1 then the greatest number shall be added to the sum again.

Any help is appreciated. Thanks!

»
2 weeks ago, # |
Rev. 12   Vote: I like it +41 Vote: I do not like it

Four methods for Problem D:

Method 0. using dp as the Editorial given: $$$a_i = a_{i-1} + 2 \cdot a_{i-2} + (i \% 3 == 0?4:0)$$$ (use $$$a_i$$$ instead of $$$dp_i$$$ for short) Code: 84808226

there is a typing mistake in Brief Solution of D: $$$(i \% 3 == 0?4:0)$$$ instead of $$$(i \% 3 == 0?1:0)$$$ DeadlyCritic

Expand the above recurrence formula we have

$$$ \begin{pmatrix} a_{3n+2} \\ a_{3n+1} \\ a_{3n} \\ 1 \end{pmatrix} = \begin{pmatrix} 5& 6& 0& 12 \\ 3& 2& 0& 4 \\ 1& 2& 0& 4 \\ 0& 0& 0& 1 \end{pmatrix} \begin{pmatrix} a_{3n-1} \\ a_{3n-2} \\ a_{3n-3} \\ 1 \end{pmatrix} $$$

with $$$a_0 = a_1 = a_2 = 0$$$, and $$$A$$$ indicate the coefficient matrix.

Methods below are $$$O(\log n)$$$ time complex since size of $$$A$$$ is a constant.

Method 1. using fast matrix power we can get $$$a_{3 \lfloor \frac{n}{3} \rfloor + 2}, a_{3 \lfloor \frac{n}{3} \rfloor + 1},a_{3 \lfloor \frac{n}{3} \rfloor}$$$, and $$$a_{3 \lfloor \frac{n}{3} \rfloor + n \% 3}$$$ is the answer

Method 2. It is well known that If you know the characteristic polynomial of matrix, then you can use polynomial multiplication instead of matrix product to get $$$(a_{3n+2},a_{3n+1},a_{3n},1)^T$$$ which is faster that Method 1, especially when the size of $$$A$$$ becomes bigger. Best method in general as I know (can't use NFT, since neither size of A is big nor 1,000,000,007 is NFT-friendly.)

Method 3. Note that the special $$$A$$$ can be diagonalized, thus there exist an invetible matrix $$$X$$$ such that

$$$ X^{-1} AX = diag(8,1,0,-1) $$$

thus we have

$$$ X^{-1} \begin{pmatrix} a_{3n+2} \\ a_{3n+1} \\ a_{3n} \\ 1 \end{pmatrix} = (X^{-1}AX) X^{-1} \begin{pmatrix} a_{3n-1} \\ a_{3n-2} \\ a_{3n-3} \\ 1 \end{pmatrix} = (X^{-1}AX)^n \; X^{-1} \begin{pmatrix} a_{2} \\ a_{1} \\ a_{0} \\ 1 \end{pmatrix} $$$

We can calculate $$$X$$$ above by hand or using following SageMath Code:

A = matrix([[5,6,0,12],[3,2,0,4],[1,2,0,4],[0,0,0,1]])
A.eigenvalues()
X = A.eigenmatrix_right()[1]

Actually we can calculate $$$A^n$$$ with only 3-lines SageMath Code:

n = var('n')
A = matrix([[5,6,0,12],[3,2,0,4],[1,2,0,4],[0,0,0,1]])
A^n

and the last column of $$$A^n$$$ is

$$$ \begin{pmatrix} a_{3n+2} \\ a_{3n+1} \\ a_{3n} \\ 1 \end{pmatrix} = \begin{pmatrix} \frac{32}{21} \cdot 8^{n} - \frac{2}{3} \, \left(-1\right)^{n} - \frac{6}{7} \\ \frac{16}{21} \cdot 8^{n} + \frac{2}{3} \, \left(-1\right)^{n} - \frac{10}{7} \\ \frac{8}{21} \cdot 8^{n} - \frac{2}{3} \, \left(-1\right)^{n} + \frac{2}{7} \\ 1 \end{pmatrix} = \frac{1}{21} \begin{pmatrix} 2^{3n+5} - 14(-1)^{3n+2} \\ 2^{3n+4} - 14(-1)^{3n+1} \\ 2^{3n+3} - 14(-1)^{3n} \\ 0 \end{pmatrix} + \begin{pmatrix} -\frac{6}{7} \\ -\frac{10}{7} \\ \frac{2}{7} \\ 1 \end{pmatrix} $$$

Code: 84843466

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

    By using another approach based on the ideas in this blog, thinking of the +4 as impulses in the recurrence f(x+2) = f(x+1) + 2*f(x) we can end in a nicer formula using geometric sums: $$$\frac{4(\frac {1 - 8^{floor(N/3)}} {1-8} \cdot 2^{N mod 3 + 1} - \frac {1 - (-1)^{floor(N/3)}} {1-(-1)} \cdot (-1)^{N mod 3 + 1})}{3}$$$

    Code

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

      That's the intended solution, nice!

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

      Thanks! I understand how you get the geometric sums, by calculating generating function. Really much nicer!

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

      tfg how did you add the impulse in the recurrence relation and get a closed formula for the generating function

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

    dna049 How did you come up with this matrix. can you please elaborate the steps. If the (i % 3 == 0) condition is not present than it is easy because we can have a 2*2 matrix. But when this condition comes into play how to construct that matrix? I struggle coming up with matrices for linear recurrence, is there a good resource to learn from?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • $$$a_{3n} = a_{3n-1} + 2 a_{3n-2} + 4$$$
      • $$$a_{3n+1} = a_{3n} + 2 a_{3n-1} = 3 a_{3n-1} + 2 a_{3n-2} +4$$$
      • $$$a_{3n+2} = a_{3n+1} + 2 a_{3n} = 5 a_{3n-1} + 6 a_{3n-2} + 12$$$

      and then write in matrix form

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

Problem C my process 1. Inserted the array of n elements into priority queue(max heap) 2. Inserted the k numbers into priority queue(min heap) 3. For all k=1, extracted max n one by one so that 2*value gets maximum! :D 4. For all k=2, same thing.extracted max twice because when k is 2, both are added! And both were max in the heap! 5. From k=3 onwards, counted how many k. Extracted that n