TheScrasse's blog

By TheScrasse, 10 months ago, In English

1654A - Maximum Cake Tastiness

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

Official solution: 150288088

1654B - Prefix Removals

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288210

1654C - Alice and the Cake

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288232

1654D - Potion Brewing Class

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150288255

1654E - Arithmetic Operations

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288285

1654F - Minimal String Xoration

Author: dario2994, emorgan5289
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288326

1654G - Snowy Mountain

Author: emorgan5289
Preparation: dario2994, emorgan5289, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288345

1654H - Three Minimums

Author: dario2994, TheScrasse
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150306974

 
 
 
 
  • Vote: I like it
  • +133
  • Vote: I do not like it

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

didn't solve C :(

However I really like this kind of easy problems that high rated users might stuck on!

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

    Same here... Was second in the contest to solve F, but smh couldn't do C at all. Locked myself into trying to recover stuff in bottom-up manner rather than top-down...

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

      Aha, I was just the opposite. I solved C rather quickly, then locked myself in the top-down manner for problem F for a long time.

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

      Can I know why does bottom-up doesn't work? Even I thought of same approach, but it gives WA on TC 2 150395732

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

        Try this Testcase on your code: 1 1 1 2 2 2

        The answer should be Yes but your code will give No.

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

    Yes, good contest. Loved solving.

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

    i didn't solve c (avoiding brute force)thinking there must be some pattern to answer yes and no so I was just trying to make cases stupid me :(

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

    really? it's hard to believe I was able to solve the problem that red_id ignores :v

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

    How to prove the complexity of C?

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

      Here's a rough sketch of why at most $$$O(n)$$$ iterations can happen:

      1. If we exit with an answer of YES, it's $$$O(n)$$$ iterations.

      2. Let $$$p$$$ and $$$q$$$ be the multisets in the official solution. At any point in time, all the elements of $$$p$$$ lie in an interval $$$[c, 2c+2]$$$ for some constant $$$c$$$.

      3. If we exit with an answer of NO, one step before we exited, there was an element of $$$p$$$ larger than the largest element of $$$q$$$, and $$$\sum p = \sum q$$$. Combining with fact 1, we get that $$$|p| \leq 2|q|+O(1)$$$ (this is the hardest step).

      4. So, we insert into $$$p$$$ about $$$2n$$$ times, and remove from $$$q$$$ at most $$$n$$$ times. So it's $$$O(n)$$$ in total.

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

        if we take priority queue for b and multiset for a ,

        ignore the condition (if max(b)<max(a)) court<<"no"<<endl; ,

        Why would this give me TLE

        pq=b; mset=a; sm=sum(a)

        pq.push(sm);
        
        while(!pq.empty()){
        	ll curr=pq.top();
        	pq.pop();
        
        	if(mset.find(curr)!=mset.end()){
        		auto ptr=mset.find(curr);
        		mset.erase(curr);
        	}
        	else{
        		if(curr==1){
        			cout<<"NO"<<endl;
        			return;
        		}
        		ll f=curr/2, s=curr/2;
        		if(curr%2) f++;
        		pq.push(f);
        		pq.push(s);
        	}			
        
        }
        
        if(mset.empty()){
        	cout<<"YES"<<endl;
        }
        else{
        	cout<<"NO"<<endl;
        }
        
        
        
        

        i feel total complexity would be O(n*log(max(a)) ?

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

      We can simply exit with an answer of NO as soon as we make N splits, because that'd generate N+1 numbers, so there's at most N splits and at most N "consume up both equal numbers" operations.

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

      At least add one cake in a turn, the max complexity is O(n) as you cut the initial big cake

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

    Nice, now I feel less Dumbass, at least I was thinking like a red somewhere XD

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

    If you have solved it now then can you provide proof (in a less mathematical way that one would come up in contest) of how it would take O(n) operations (so time complexity is O(nlogn)) in the official solution of problem C?

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

It's a balanced contest in terms of difficulty.

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

F is really awesome!

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

Video editorial, if anyone prefers that

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

जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।

Nice questionset. Thanks!

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

I solved F using hashing and xor segment tree. We can maintain a segment tree to answer queries to get the rolling hash of $$$s_{l \oplus x} s_{(l+1) \oplus x} \ldots s_{r \oplus x}$$$ so we can compare $$$2$$$ strings in $$$O(n^2)$$$ by finding the longest common prefix. I think this can be optimized to $$$O(n)$$$ if you really wanted.

Code $$$O(n^2 2^n)$$$: 150271155
Code $$$O(n 2^n)$$$: 150276264

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

    Me too. The intended solutions looks so much simpler and easier to implement tho :(

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

Problem E asks for the same condition as 1616C - Representative Edges, though the constraints make the two problems quite different. I don't think there's anything problematic here, just thought it was interesting.

Edit: There's actually an important distinction because problem E requires the sequence to consists of integers. I feel quite dumb because I failed to solve E in contest due to trying to map fractional slopes and getting TLE due to costly hashing...

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

Great round! Thank you.

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

Great problem!

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

Problem E: Was this simple $$$O(n \sqrt{n} \log n)$$$ (with maybe good constant) allowed?
150252654

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

The TL for problem G is suspicious.

I implemented another algorithm with $$$O(n\sqrt n)$$$ runtime: note that either the resulting height will be $$$\le W$$$, or only at most $$$W$$$ energy could accumulate and be used during the process for $$$W=\sqrt n$$$. One might find the submission here: 150268402. However, it got TLE even with setting $$$W$$$ to 105, which takes precisely $$$O(nW)$$$ time. (I passed during the contest with $$$W=25$$$)

I suspected that either the std constant was very small, or the test cases were weak such that std takes far less than $$$O(n\sqrt n)$$$ time on them.

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

    I am not understanding, so I will ask some questions:

    • What is "std"? It usually stands for "standard" or "sexually transmitted disease", here it seems like it means neither.
    • You use the letter $$$W$$$ but in the solution you linked it seems like the letter $$$W$$$ does not appear. What is $$$W$$$ in the solution you linked?
    • The solution you mention with $$$W=25$$$ shall get WA? Or it should get TLE? Or it is correct that it gets AC?
    • Your point is that you have a correct solution with complexity $$$O(n\sqrt{n})$$$ which gets TLE? If so, then you are saying the the TL is too small?
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      1. I mean the code of standard solution. Sorry for the unclear abbreviation
      2. It appears as S and T
      3. It should get WA (and I hacked it)
      4. Yeah, I think the TL might be small, and std might take more time on stronger tests.
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Thanks a lot for the explanation, now I see the point.

        Regarding your solution getting AC instead of WA, that's unfortunate (but not for you :p). I have seen (thanks to your attempted hacks) that you seem to be the only contestant affected, so that's not too bad (for sure not for you :p).

        Regarding the TL being too small for your solution. I would guess that you have a bad constant factor, but I have not checked so I don't know (and I will not investigate further).

        Regarding the TL being too small in general and the authors not noticing because of weak tests. I don't think this is the case. The official solution's slowest behavior (i.e., when $$$z\approx 100$$$, where the letter $$$z$$$ counts the number of interesting heights) is triggered by the tests (just checked adding an assert). Moreover there is also an alternative solution (not mentioned in the editorial) with complexity $$$O(n\log(n))$$$ which fits easily in the TL and whose running time is almost independent of the structure of the tree.

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

Implementing E in $$$O(n\sqrt{n} \log{n})$$$:

*remembers -is-this-fft- said it is evil complexity in his last post and should be avoided at all costs

-> alright i will just use array of size 70 million

150284056

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

    Can you, please, clarify your approach?

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

      When $$$d \le \sqrt{M}$$$ it is same as in editorial, and when $$$d >\sqrt{M}$$$ you can look at my approach as:

      Consider each starting point $$$i$$$ (first element that will be "saved") and check next $$$\sqrt{M}$$$ elements and their possible $$$d$$$, reason why it is enough to check only $$$\sqrt{M}$$$ elements is because after that even when $$$a_i=0$$$, $$$a_j$$$ where $$$j>i+\sqrt{M}$$$ would must be $$$> M$$$ which isn't possible (because $$$a_j=a_i+d*(j-i)$$$)

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

I got MLE in C by popping the largest $$$b_i$$$, as in the editorial, and had to switch to a min heap to pop the smallest $$$b_i$$$ instead. Am I miss something? In this case the solution is $$$O(n\log^2n)$$$ I think.

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

    Your submission is $$$O(sum*\log sum)$$$

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

Problem C was good :)

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

    The best problems are those you solve, find intuitive and clear, but the others don't

    --Not me, That guy's (that is not me) hypocritical arguments

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

In question D, the same solution can be done for node 2,3 and all. So why should we not take max of all of them. In other words, why taking node 1 as lcm of denom and setting others accordingly works?

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

    If you start DFS from any node $$$s$$$, the result is already the minimum possible, so you would get the same result for any node.

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

      Ah, I thought of exact same logic, but thought will have to check for al vertices. F

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

My Approach for Problem C:

Perform BFS starting from the total sum of the given weights(root node). There can be maximum of two child nodes of a parent node. Child Nodes are $$$ceil(p/2)$$$ and $$$floor(p/2)$$$, where $$$p$$$ is a parent node.

Only explore those child nodes which are not present in the given weight array.Reason for this is, because If we have already found a weight(value of the child node) which is present in the input weight array, we should not divide it further, instead we will count this weight in our answer.

(Exploring means cutting a piece of cake, Or dividing the child node into 2 halves.)

For example, If both child nodes of a particular parent node are $$$64$$$ and If $$$64$$$ is present in the input array ($$$1$$$ time), then we will explore only one child node.If its present more than $$$1$$$ time, we will not explore these $$$2$$$ child nodes, because we will be counting these $$$2$$$ child nodes in our answer.

Note- You can draw a tree on a paper, It will be more clear.Start from sum of all given weights, and divide it further, It will look like a binary tree.

If we have explored $$$n-1$$$ nodes, that means we have performed $$$n-1$$$ cuts to the cake.Hence we have divided the cake into $$$n$$$ weights.

Answer will be YES, If we found all the input weights in our binary tree.Otherwise, It will be NO.

Time Complexity — $$$O(n)$$$, where $$$n$$$ is number of input weights (size of the array). Reason being, BFS will stop as soon as we explored $$$(n-1)$$$ nodes.

My AC Solution-Click Here

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

Wow, F is just awesome, I have never seen use of suffix array in this manner.

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

[Deleted]

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

https://codeforces.com/contest/1654/submission/150245226

Could someone explain why this solution work ? Isn't it has complexity $$$O(n^2)$$$ so it should be TLE ?

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

Lesson learnt rest well before contest!

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

C is really a good problem. I was confused at first, but when I finally solved it, the solution seems to be obvious.

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

The editorial is amazing! I hope all the editorial have "Hints".

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

In problem G, there is

The largest possible value of $$$\sum\limits_{v\in S}h_v$$$ is $$$O(n)$$$.

I don't know why, can anyone help me?

Thanks in advance.

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

    I dont have a rigorous proof of this fact, but I believe this can be obtained by giving a lower bound for the number of vertices with height $$$i$$$ given the number of flippable vertices with greater or equal height (for example, lower bounded by half of this quantity).

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

    I am not able to prove strict linear dependency but it is very close. Let's have an array{X1,X2,X3...,Xn} which denotes the frequency of flippable vertex for each height. Then let S = X1*1+ X2*2 ...+ Xn*n The S is amount of nodes that will be needed generate all flippable vertex. For example, flippable vertex with H=3 will require 3 vertex with H=0,1 and 2. There will be overcounting. Specifically, a node can be contribute to multiple flippable vertex. Let O be that value. We then have S-O <= n. We can use small to large to proof that there will atmost Logn flippable nodes that a single node can contribute to.That gives O <= Nlogn. Thus we have S<= N(Logn + 1).

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

    Here are my thoughts. qwq

    First root the tree at a base lodge. Consider a BFS cover process below.

    BFS from the root and we can find some nearest base lodges.

    A pair of "flippable points" must exist at the midpoint of the path from these lodges to the root. We pair the lower endpoints of each point pair with certain nearset lodge and cover the path between them.

    In addition, there are no other flippable point pairs on the merge of paths from these lodges to the root (blue area in the figure).

    So we delete blue area and the original tree is divided into several subtrees with roots. We can do similar process in each subtree.

    Finally, we can see the coverage areas do not intersect so half of $$$\sum\limits_{v\in S}h_v$$$ is $$$O(n)$$$.

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

    I figured out another proof of this. First, we can group the vertices in a way that each vertex and its nearest base lodge are in the same group. Let $$$k$$$ denote the number of base lodges. Then we get $$$k$$$ group. Each group forms a tree, let $$$T_i$$$ denote the $$$i$$$-th tree, $$$|T_i|$$$ denote the number of vertices in the $$$i$$$-th tree.

    Besides the edges inside every tree, there are $$$k-1$$$ cross-tree edges, each of which connects two vertices in different trees. The difference of the height of two vertices of a cross-tree edge is no more than 1. If the height is equal, then the two vertices form a pair of flippable vertices. Since we want to make the sum of these height as large as possible, we can assume that all $$$k-1$$$ cross-tree edges connect equal-height vertices. In other words, we have $$$k-1$$$ pair of flippable vertices.

    For a pair of flippable vertices with height $$$h$$$, if they belong to $$$T_A$$$ and $$$T_B$$$ respectively, then we can get $$$h \leq |T_A|, h \leq|T_B|$$$.

    If we compress each tree $$$T_i$$$ as a single vertex, and all $$$T_i$$$ and the $$$k-1$$$ cross-tree edges will form an abstract tree. We can let $$$T_1$$$ be the root of this tree, then the edges of the tree can be listed as $$$(T_2, p(T_2)), (T_3, p(T_3))... (T_k, p(T_k))$$$, where $$$p(x)$$$ is the parent of $$$x$$$.

    Thus, $$$\sum h \leq 2(|T_2| + |T_3| + ... + |T_k|) \leq 2n$$$.

    Q.E.D.

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

I tried explaining my solutions for problem A,B and C . Link to the video

Hope this can be of any help.

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

D claims that to recover LCM it takes the minimum of all powers for each prime p over DFS. This claim does not make sense to me — and in the code itself it seems like it takes the maximum

for (int p : factors[x]) f[p]++, cmax(wf[p], f[p]);

It would be good to know where I have misunderstood

Edit — Ah I see, taking the max and multiplying by 1 is the same as taking the min and multiplying by -1.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--)
    {
     string s;
     cin>>s;
     unsigned int i,j;
     if(s.size()==2)
     i=1;
     else if(s.size()%2==0)
     i=s.size()/2-1;
     else
     i=s.size()/2;
     while(i>0)
     {   
            string a=s.substr(0,i),b=s.substr(i+1,s.size());
            
             if(strstr(b.c_str(),a.c_str()))
            {
                s=b;
                if(s.size()==2)
                i=1;
                else if(s.size()%2==0)
                i=s.size()/2-1;
                else
                i=s.size()/2;
            }
            else
            i--;
     }
     cout<<s<<endl;
    }
    return 0;
}

my code is failing for "bbbbbbbbbb" expected is "b" but i am getting "bb" please check my code once

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

I didn't solve C. because I'm keep writting solutions of bottom-up during the contest... :(

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

    i can 100% relate to this when testing the round D:

    Sometimes thinking too hard can screw you over :/

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

Problem C, my solution is based on something that I can't prove...

I guessed that if the initial value is $$$k$$$,then the numbers we can get by spliting $$$k$$$ is like $$$\frac{k}{2^w}$$$ and $$$\frac{k}{2^w}+1$$$.

according to this conclusion, I passed this problem. 150259381

I don't know how to prove or hack this submission.If you can help me I will be very thankful :D

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

    In my submission, $$$x$$$ is the number of $$$s$$$, and $$$y$$$ is the number of $$$s+1$$$

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

    Your claim is true. In fact, if you define $$$f(x) = \lfloor \frac{x}{2} \rfloor$$$, $$$g(x) = \lceil \frac{x}{2} \rceil$$$, you get $$$f^w(x) = \lfloor \frac{x}{2^w} \rfloor$$$, $$$g^w(x) = \lceil \frac{x}{2^w} \rceil$$$.

    Sketch of proof:
    Let $$$x = 2^w \cdot \lfloor \frac{x}{2^w} \rfloor + b_0$$$ ($$$0 \leq b_0 < 2^w$$$). Then, $$$f^v(x) = 2^{w-v} \cdot \lfloor \frac{x}{2^w} \rfloor + b_v$$$.
    $$$b_v = \lfloor \frac{b_{v-1}}{2} \rfloor$$$, so $$$b_w = 0$$$ and $$$f^w(x) = \lfloor \frac{x}{2^w} \rfloor$$$.
    Same proof for $$$g$$$.

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

I literally got stuck in C and couldn't solve C and did not try to move on

At last I lost 171 rating

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

I think in the Hint 5 of the editorial of H, the ODE should be:

$$$y'(t)=a(t)y(t)+b(t)$$$

In the current version, the ODE has 2 "+", without any "=".

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

G can also be solved in O(nlog^2n) with centroid decomposition

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

    It's also possible to improve this to $$$\mathcal{O}(n \log n)$$$, since the positions of the segment tree you need to update and query are bounded by the current centroid's subtree size, so you can simply use an array with prefix minimums. Code: 150307419

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

      I realized that I don't even need a segment tree since I am also only checking the maximum number in the complete segment tree and not a subrange.Can just maintain the maximum in one variable.Code

»
9 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

I solved C using BFS .. multiset and queue ..and got AC ..you can see my simple code here: https://codeforces.com/contest/1654/submission/150350334

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

Can someone help me with this code Solution ,I guess there is some issue due to modular operations.

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

Could anybody explain why this code is giving me TLE string x; cin>>x; string y=x; unordered_map<char,lli>ump; loop(i,0,x.length()-1){ ump[x[i]]++; } loop(i,0,x.length()-1){ if(ump[x[i]]>=2){ reverse(y.begin(),y.end()); y.pop_back(); reverse(y.begin(),y.end()); ump[x[i]]--; } else{ break; } }

cout<<y<<nl;
»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I really loves this kind of editorials. This helps soo much!

»
9 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I am trying to solve D by running DFS twice: First Bottom-Up and then Top-Down.
The solution seems to be working fine on smaller test-cases (5-6 edges) but its output slightly differs on the pretest's 3rd test-case, which is difficult to analyze.
Submission.

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

The editorial with serveral hints was great help to me! It can always help me understand how to come up with the correct ideas. And the solutions are also very comfortable to read and easy to understand.

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

In problem C, can anyone please explain that if i process the divisions like the dfs match the values with elements in 'a' and along with keeping track of whether the current value can be further splitted if the list 'a' has no smaller value then will it work? I tried in this way and somehow getting TLE. Couldn't find where i'm wrong. My Submission : 153465444

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

1654C - Alice and the Cake

why am i getting TLE for this java solution??

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer t = Integer.parseInt(sc.nextLine());
        for(int tt=0; tt<t; tt++) {
            Integer n = Integer.parseInt(sc.nextLine());
            String[] inte = sc.nextLine().split(" ");
            long sum = 0;
            HashMap<Long, Integer> map = new HashMap();
     
            for(int i=0; i<n; i++) {
                long val = Long.parseLong(inte[i]);
                sum += val;
                map.put(val, map.getOrDefault(val, 0)+1);
            }
            
            Queue<Long> q = new LinkedList();
            q.add(sum);
            
            int pc = n;
            while (q.size() > 0) {
                if (pc == 0) break;
                long val = q.poll();
                if (val == 0) break;
                if (map.getOrDefault(val, 0) > 0) {
                    map.put(val, map.get(val)-1);
                    pc--;
                } 

                    long f = val/2;
                    long c = val - f;
                    
                    if (map.getOrDefault(f, 0) > 0) {
                        map.put(f, map.get(f)-1);
                        pc--;
                    } else {
                        q.add(f);
                    }
                    
                    if (map.getOrDefault(c, 0) > 0) {
                        map.put(c, map.get(c)-1);
                        pc--;
                    } else {
                        q.add(c);
                    }
                    
                
            }
            if (pc == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }

        }
    }
}
»
7 months ago, # |
Rev. 4   Vote: I like it -11 Vote: I do not like it

Problem C editorial solution will get TLE for bellow case:

1
200000
1000000000 1000000000 1000000000 1000000000 1000000000 ... all 2*10^k element of a is 10^9

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

    I did some wrong maths, and finally understood the solution. thanks.

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

anyone please tell me my mistake in problem C 156969000

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

    It's a really silly error, but in line 52, you wrote bb.top() when you actually meant bb.pop(). This led to time/memory limit exceeded because if you enter that case even once, then it would perpetually add new elements forever while the top remains unchanged.

    For future reference, to better identify the mistakes you made, my suggestion is to:

    • try the sample input first
    • if that fails, try running only one test case at a time, for each test case in the sample input. This will allow you to identify which test case breaks your program.
    • For the problematic test case, try to trace through what happens in your program for this specific case, carefully reading each line that is executed and writing out intermediate values and so on. This should reveal why the output differs from your expectations (or why the time/memory limit was exceeded).

    (if the sample input passes, then you'd want to construct edge cases or tricky cases that do not seem to be covered in the sample input, and follow the same steps)

    By the way, I only tested your code on the sample input, and the correction was sufficient. However, I don't actually know if the rest of your code is actually correct.

    Yes, I know this is like, two months late, but I understand the frustration of not knowing why your code is failing, so hopefully this may be a little comforting and can help you avoid similar errors in the future, with proper debugging.

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

Tags for C can include bfs...

queue q; q.push(sum); int op=0; while(!q.empty()) { ll t=q.front(); q.pop();

if(m.count(t))
  {
      m[t]--;
      if(m[t]==0)m.erase(t);
  }
  else if(t!=1 && op<=n-1)
  {
      q.push(ceil((double)t/2LL));
      q.push(t/2LL);
      op++;
  }

} if(m.empty())cout<<"YES\n"; else cout<<"NO\n";