### natalina's blog

By natalina, history, 3 months ago, translation,

1941A - Rudolf and the Ticket

Author: daha.002

Tutorial
Solution
Rate the problem

1941B - Rudolf and 121

Tutorial
Solution
Rate the problem

1941C - Rudolf and the Ugly String

Author: Mordvin13

Tutorial
Solution
Rate the problem

1941D - Rudolf and the Ball Game

Author: Alexey_Parsh

Tutorial
Solution
Rate the problem

1941E - Rudolf and k Bridges

Author: t0rtik

Tutorial
Solution
Rate the problem

1941F - Rudolf and Imbalance

Tutorial
Solution
Rate the problem

1941G - Rudolf and Subway

Author: natalina

Tutorial
Solution
Rate the problem
• +64

 » 3 months ago, # |   +4 I have seen many people code segment tree solutions for E (including tourist). Can someone please explain how segment tree was used in this question? PS: I understood the solution explained here using dp.
•  » » 3 months ago, # ^ |   +8 For checking the minimum cost for the previous d cells and the sum of dp starting from the ith row and i+kth row I used a segtree as I had a pretty flexible template and it would pass the TL and be easy to code.
•  » » » 3 months ago, # ^ |   0 Ooooohhhhh I get it .... That's nice.... thanks for clarifiation.
•  » » 3 months ago, # ^ |   +1 It is easy to use segment tree just to calculate the minimum in the range where range is D elements before it using segment tree.See my code maybe you can understand it easily :- Submission Link
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I see... Understood how you have used seg tree here. Thanks very much.
•  » » » 3 months ago, # ^ |   0 can also be done using minheap.
•  » » 3 months ago, # ^ |   +3 It could be used to find minimum elementsin O(logn), however this is absolutely not necessary, I for exmaple got E with a deque.
•  » » 2 months ago, # ^ |   0 is there a way to solve this problem using topdown dp ? I used brute force method checking for each d using top down approach , got TLE .
 » 3 months ago, # |   +12 if I want to propose problems to div.3 , how I can do ?
 » 3 months ago, # |   +24 Alternate G solution:Use each subway line as nodes and each station as edges. The trick is to process each station only once.
•  » » 3 months ago, # ^ |   +3 can you explain more.I saw jiangly using the similar technique but can't understand why process each station only once?
•  » » » 3 months ago, # ^ |   0 Why not read his submission 250862298
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 How can this solution distinguish between vertices and colors? For example node 1 is connected to node 2 with edge of color 1. Edit : Ok so this is taking two graphs for that one is pointing to the adjecent color and another is pointing to the adjecent nodes.
 » 3 months ago, # |   +13 I considered myself a pro at binary search and then problem F happended :/ Nevertheless learned something new. Thanks to the authors.
•  » » 3 months ago, # ^ |   +1 A similar problem link
•  » » » 3 months ago, # ^ |   0 Thanks bro!
•  » » 3 months ago, # ^ |   +6 I think this was a typical binary search ques, nothing new
•  » » » 3 months ago, # ^ |   0 Maybe, I was having a bad day, lol.
•  » » 3 months ago, # ^ |   0 uhhhh.. binary search is not necessary for F, 2Pointers would also work.But anyway, sorry for your loss.
 » 3 months ago, # |   0 why my state dijsktra to G problem is TLE? 250857953
 » 3 months ago, # |   +3 E can be solved in O(n) using deque
•  » » 3 months ago, # ^ |   +10 Yes, I think it would be similar to maintaining the sliding window minimum over the dp array for each row, storing the minimum costs, and then finally finding minimum sum over $k$ consecutive costs for the answer.
•  » » » 2 months ago, # ^ |   0 I did the same and I'm still getting an error in the second test case. Can anyone point out the mistake? 251067871
•  » » 3 months ago, # ^ |   0 fax
•  » » 2 months ago, # ^ |   0 can E be solved using topdown appraoch without getting TLE ?
 » 3 months ago, # |   0 I really enjoyed solving problem D. I also think that B wasn't suitable for a div 3 B. C, B or maybe D should've been swapped with each other.
•  » » 3 months ago, # ^ |   0 maybe, B had a trick that may have been harder to catch than C which is easier to figure out, but harder to implement. Though, this would be splitting hairs. D, though, in my opinion, is significantly harder than B to implement and earned its spot.
•  » » » 3 months ago, # ^ |   0 respect your opinion but personally, D was very easy.
•  » » » » 2 months ago, # ^ |   0 I agree. D was easy, but generally Div3 A-D are easy for me. Div3 E/F are medium, and Div3G is hard. This contest fits this mold fairly well.
 » 3 months ago, # |   +9 Problem C can also be solved with Aho Corasick Automaton. Build a $dp[n][m]$ where $n$ is the length of the string and $m$ is the number of states in the automaton, where $dp[i][j]$ tells us the minimum number of changes needed to be in state $j$ of the automaton (which represents some partial or complete matching with some pattern) considering the prefix $s[0...i]$. It's kinda overkill for this problem, but it's an interesting idea to know. Here's my submission 250707601.For more details, refer to: CP Algorithms
 » 3 months ago, # |   0 Dislike if you are a ebantuza
 » 3 months ago, # |   0 Oh I solved prob E with just O(n*m) xD
•  » » 3 months ago, # ^ |   0 I saw your code but can you explain it to me please ? iam still learning ,thx.
•  » » » 3 months ago, # ^ |   0 You can calculate the answer for one row in O(m) by using monotone deque (afterward, you can obviously find the minimum amongst all windows of size k in O(n)). How to calculate the answer for a row in O(m)? • Make a deque (storing the indices of the relevant elements amongst the last ${d + 1}$ elements).• Iterate over array. For ${i^{th}}$ element, pop the back elements of the deque as long as they are greater than the current element. Then push the current element and pop the front element if it doesn't lie in the last ${d + 1}$ elements.• Now, the front element of the deque is the smallest element amongst the last ${d + 1}$ elements. Update ${dp_i}$.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 yeah that's rightthe technique I used in that code is to find the nearest element on the left of i (call it j) which a[j]
•  » » » » » 2 months ago, # ^ |   0 i will definitely give it a look , thanks for the help
•  » » » » 2 months ago, # ^ |   0 thanks for explain it to me i understood it now :)
•  » » 2 months ago, # ^ |   0 Same, O(m) to find max on bridge, O(n) for each bridge
 » 3 months ago, # |   0 My approach to G was as follows: make a new graph $G'$ where each node represents an edge in the original graph. There will be an edge between nodes corresponding to $(u,v)$ and $(v,w)$, with weight 0 if they have the same color and 1 otherwise. Then I'm doing 0-1 BFS from $(b,x)$ for all $x$ which are neighbors of $b$. Can someone please help me in optimizing the creation of this graph, because currently my method to generate this new graph is giving TLE. Link to submission — Here
•  » » 3 months ago, # ^ |   0 Just look few comments above. Edge graph can easily become $n^2$
 » 3 months ago, # |   0 Problem E can be solved using deque to calculate the minimum cost of each bridge in O(m), not O(mlogd); so the final complexity will be O(nm) My submission: https://codeforces.com/contest/1941/submission/250832314
 » 3 months ago, # | ← Rev. 2 →   0 ABC — average, div-4 level problems.D — bad, why set a problem about naive simulation at this level? Also, editorial code has a $\log$ factor that is not reflected in the complexity analysis. It may not sound like a big deal to you, but beginners regularly get confused by such things.E — bad, unusual distance definition. Also, the editorial solution has an extra $\log$ factor for no reason. Finding minimums/maximums in a sliding window is a well-known monotonic queue problem with equally short implementation. Div 3 rounds are supposed to be educational for beginners, please live up to the name.F — bad, the unusual 2e9 limit was unnecessary. What are you, fishing for overflows? 1e8 was enough to TLE all convolution-based solutions, but you may as well have used 1e18 if you really wanted to avoid anything unintended. And once again, binary search is not necessary. Just sort both arrays and use two-pointers.G — Good.
•  » » 3 months ago, # ^ |   0 What is a convolution based solution ? Can you explain please ?
•  » » » 3 months ago, # ^ |   0 Consider a polynomial product $P(x) = (x^{d_1} + x^{d_2} + \ldots + x^{d_m}) (x^{f_1} + x^{f_2} + \ldots + x^{f_k})$. $[x^n]P$ is nonzero iff there exist $1 \le j \le m$ and $1 \le l \le k$ s.t. $d_j + f_l = n$.
•  » » 3 months ago, # ^ |   +13 G : lol
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 I'm interested in your suggestion to use two-pointers here. Could you explain how that works, when there are two arrays in play?EDIT: Rather I am wondering a bit if we can prove that following the two pointers approach will give us the correct answer here.
•  » » » 3 months ago, # ^ |   +3 250732405 When looking for $d_j + f_l$ as close to some target as possible, increase the sum if it's less and decrease otherwise (in code all numbers are multiplied by 2 to avoid floating-point math).
•  » » » » 3 months ago, # ^ |   0 How can we prove that this will actually give us the closest pair to target as possible? Using binary search it's pretty straight forward but I'm can't prove it for your two pointers approach.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +2 Say both $d$ and $f$ are sorted in ascending order (wlog all numbers are unique).If $d_j + f_l < x$ then $d_{j'} + f_l < d_j + f_l < x$ for all $j' < j$ and hence $|(d_{j'} + f_l) - x| > |(d_j + f_l) - x|$. Therefore, no pair $(j', l)$ with $j' < j$ is optimal. Similarly, no pair $(j, l')$ with $l' < l$ is optimal. We already considered all pairs with $l' > l$, so the remaining candidates are pairs with $j' > j$. Hence we should increment $j$.Similarly, we should decrement $l$ if $d_j + f_l > x$.Alternatively, you may show that this two-pointers algorithm finds the same indices as your binary searches.
•  » » » » » » 3 months ago, # ^ |   0 Thank you for the neat explanation! Took me some time to fully comprehend but yeah that makes a lot of sense!
•  » » » » » » 3 months ago, # ^ |   0 Thanks, this was exactly was I was looking for!
•  » » » » » » » 3 months ago, # ^ |   +3 Here's a practice problem for you and dekatin: LC 240. Search a 2D Matrix II
•  » » 3 months ago, # ^ |   0 F — ... binary search is not necessary. Just sort If sort is O(n*log(n)) and m (2**16) is much bigger than k (2**8):Sort m and k, then two pointers: 2**16 * 16 + 2**8 * 8 + 2**16 + 2**8 = 2**20 Sort only k, then binary search: 2**8 * 8 + 2**16 * 8 = 2**19
•  » » » 3 months ago, # ^ |   0 Bold of you to assume that constant factors are the same. std::{lower,upper}_bound is a straightforward algorithm that implements binary search exactly how you do. It also makes a lot of jumps in memory. Meanwhile, std::sort is quite heavily optimized, and two-pointers make no jumps whatsoever.
 » 3 months ago, # |   0 Slightly less casework required solution for C: count of "map" + count of "pie" — count of "mapie" For D, state DP is better, has better time complexity, and far more braindead (literally obvious to everyone after enough practice?). May or may not require vector.resize() (note to self: CLEAR THE ENTIRE VECTOR BEFORE RESIZING YOU DUMB FUCK) For E, multiset has horrendous constant factor (see: My -9 in that Div3 D several contests ago). Use a priority queue instead. To get the minimum "available" value, just throw every value that could no longer be used out of the pq
 » 3 months ago, # |   0 Can someone explain me jiangly's solution for problem G ? What was the approach and what does dist[{e, 0}] mean?
•  » » 3 months ago, # ^ |   -13 dist is a map which stores pair as key, and int is valueSo "cout << dist[{e, 0}];" means print the value of {e, 0} key{e, 0} is a pair, e is first and 0 is second
•  » » 3 months ago, # ^ |   0 The technique he used is 01-BFS
•  » » 3 months ago, # ^ |   0 As we arrive at some unvisited color we first travel along it, and only then go to adjacent colors. 0 is the nice trick that means "line processed".
 » 3 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1941/submission/250749988 could someone help me figure out why this isn't working?
 » 3 months ago, # |   0 what is wrong in this code : https://codeforces.com/contest/1941/submission/250787705Is my logic wrong or am I missing some edge cases. Please Help me . Thank you in advance!
•  » » 3 months ago, # ^ |   0 In addition to considering breaking down the maximum difference $(a_{i+1}-a_i)$, the second biggest difference between $a$ elements should also be factored in. Consider the test case: 3 1 1 1 7 12 2 2 Also, when performing binary search (function f in your code), the boolean that it should answer would be: is there $d \in D$, $f \in F$ such that $max\left(d+f-a_i \, ,\, a_{i+1}-\left(d+f\right)\right) \leq mid$.
•  » » » 3 months ago, # ^ |   0 can you suggest a way to correct the code or is my approach completely. I tried by myself but I am not getting any idea. Thank you
•  » » » » 2 months ago, # ^ |   0 I made modification to your code (251127599) and it runs correctly.To elaborate on how to binary search on getting an optimal split between $[a_i, a_{i+1}]$: for $d$ and $f$ we would want to minimize $|(\frac{a_i+a_{i+1}}{2} - (d+f))|$. For a $mid$, we seek $d$ and $f$ such that $a_i + a_{i+1}-mid \leq 2 \cdot (d+f) \leq a_i + a_{i+1}+mid$ If res is the minimum such $mid$ which satisfies, then the required imbalance between newly added problem and $a_i, a_{i+1}$ would be (a[i+1]-a[i]+res)/2
 » 3 months ago, # |   0 In my opinion the TL on G was very constrained. I had to switch to deque to make it pass. Was an extra logn deliberately disallowed?
•  » » 3 months ago, # ^ |   0 Can u please explain me the editorial elaborately.What are the new nodes created and how to make edges between them?
•  » » » 3 months ago, # ^ |   0 You've got the original nodes (station vertices) and the newly created color vertices (corresponding to all the distinct colored edges possible). Now you draw an edge from the two groups (station to color and vice versa). An edge is drawn from station vertex a to color vertex b if and only if there is an edge color b incident to station vertex a. Now you perform simple BFS and report the destination distance/2. Note: You consider the edge weight to be 1. Now think why we divided by 2. Also think how this is a bipartite graph.
 » 3 months ago, # |   -8 Problem D: chatGPT solved this question just by entering question statement in prompt
•  » » 3 months ago, # ^ |   0 bro leave me happy it was the first time I solve till D :D
 » 3 months ago, # |   0 please anyone can explain the solution of peoblem of B ?
 » 3 months ago, # |   0 can someone explain to me this line of code ? for (string sul : {"mapie", "pie", "map"})i dont understand the code of the editorial why they alwayes make it hard to read for beginners?
•  » » 3 months ago, # ^ |   +3 It's a simple combination of range-based for loop and initializer lists. Both are available from C++11 and are very basic.
 » 3 months ago, # |   0 can someone help with problem E ? i get WA 251001023
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 just remove this line from your sliding window: int yans = ans; declare yans outside the loop.refer to my version of this snippet, my win is your yans: win = 0; res = 0; f(i,0,k) win+=costs[i]; res = win; f(i,k,n) win += costs[i] - costs[i-k], res = min(res, win);
•  » » » 3 months ago, # ^ |   0 it gives TLE now. i did the dp in a different way but i think it should be fine ?? 251010002
 » 3 months ago, # |   +6 Regarding problem F: It is relatively easy to see that we must decrease the maximal $diff = a_{i}-a_{i-1}$, but my question is, what if there are more than 1 such $j's$ where $a_{j}-a_{j-1} = diff$. How do we choose which difference to take?
•  » » 3 months ago, # ^ |   +3 if there are more than 1 such that maxDif is same then answer is always maxDif i also had this same doubt during contest and now i feel extremely dumb its over for me
 » 3 months ago, # |   0 For $G$, I noticed that if a particular vertex has edges of colors $(c_1, c_2, c_3 ... c_k)$ then the sub-graphs of these colors can be reached by others of this set through at-most 1 different colored edge. So all we need to do is keep track of which "color" belongs which "clusters" (I call each such set a cluster), and vice versa. Then just expand the cloud of visited colors, till we reach a color which is connected to the destination. As someone who has little math background and is algorithmically weak. I think it is quite intuitive and easier to come up with. Submission-->251004746
•  » » 3 months ago, # ^ |   +3 I Have the same idea Like for a vertex , find the set of distinct colors it attached to What it means is , we can go from a color of this set to any other color of this set Now , But i do know how i proceed to implement it Let me check your submission
 » 3 months ago, # |   0 Why is problem F labeled as two-pointers? Can't think of a solution that uses the two pointers technique.
•  » » 3 months ago, # ^ |   +1 We need to decrese the max gap right (the one having max A[i] - A[i-1]) Now,we can just insert one element (What it would be!!) Obviously mid , mid = (A[i] + A[i-1]) / 2 So indirectly , Question transform to find (i,j) such that D[i] + F[j] is closest to mid This is two pointer right, (Sort D and F and then find it right)
 » 3 months ago, # |   0 I would love to contribute problems for Div 3. Is there a way I can do that?
 » 3 months ago, # |   0 Ref B tutorial, What does the following meanapplying the operation to a more leftward element is either impossible or will make some elements less than zero
•  » » 3 months ago, # ^ |   0 We are iterating from left to right. We'll apply the operation to i+1th element. Since op=a[i] and a[i]=-op, the elements to the left would already have been 0
•  » » » 3 months ago, # ^ |   0 So, it's implying to only move left to right. Got it, thanks!
 » 3 months ago, # |   0 Can someone please tell me what's wrong with this (https://codeforces.com/contest/1941/submission/251042147) approach for 'E'? Why do I get the wrong answer?
 » 3 months ago, # | ← Rev. 2 →   +14 Very real-life G. In reality the answer is seldom greater than 4，at least in Shanghai, 4 applies to a suboptimal route from Fudan to SJTU: source Fudan U, dest Dongchuan Rd, Fudan U -L18> Jiangpu Park -L8> People's Sqr -L1> Xinzhuang -L5> Dongchuan Rd. But you can choose Zizhu Hi-tech Zone(L15 terminal) as the destination if you want to goto SJTU and reduce the answer to 3.In Tokyo this answer might be larger
 » 3 months ago, # |   +5 I found an interesting solution to the problem G . I reformulate the graph G to G' as follows:1) Each colour is a node in the graph G'.2) Each node which is an endpoint of atleast 2 edges of different color is also inserted as a node in my graph. These nodes are special as they "link" 2 different colors. Now for the type (2) nodes I insert an edge E of the original graph , with one endpoint at the node itself and the other endpoint at the color of the edge of our considered type (2) node in the original graph . For example: for the given sample input in the question n = 6 m = 6(Edge , colour)1 2 12 3 15 2 22 4 24 6 23 6 3In the reformed graph G': Nodes : (color1) , (color2), (color3) , (2) , (3) , (6) Edges : (6->color3) , (6->color2),(2->color1),(2->color2) , (3->color1),(3->color3) Note : 2,3,6 were added as they were part of edges of atleast two distinct colors ,and their edges were added as shown above.The approach seems long in writing but intuitively its quite simple. Each connected component of a colour is treated here as a SUPER NODE and the other nodes were added to simplify how the colours are connected amongst themselves. As a multisource BFS is sufficient to find number of minimum colors required to go from set of colors to any particular colors the answer can be found easily.The link to my submission:251061492Here for type(2) nodes i insert their negatives , so that they dont collide with the colors. Please excuse me for the messy code.
•  » » 2 months ago, # ^ |   0 You can also add half weight in the newly formed graph and then apply dijiskstra
 » 2 months ago, # |   0 E problem was beautiful.
 » 2 months ago, # |   0 https://codeforces.com/contest/1941/submission/250969634This is my code for Problem E using memoization which is giving TLE on test case 6 (obviously because Time Complexity is O(n.m.d). I saw various optimised iterative DP approaches used by people with multiset/dequeue/priority queue, but cant find a memoized solution. Can anyone help me out with optimising my memoized approach. Thanks.
 » 2 months ago, # |   0 can anyone please help me (i have read editorial & i m still stuck) my approach is getting WA on testcase 2 https://codeforces.com/contest/1941/submission/251049209 thanks in advance
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 There are two problems here the line if (b[i] > md) break; is wrong. consider this test 1 2 1 1 1 100 98 1 here is the answer is $98$, but your output is $99$. This happens because your code ignores any other value greater than the mid. However a pair of number might work but their summation is greater than mid, as in the above test you are also getting the mid value wrong. In your code, int md = a[l] + a[r]/2;. Consider, $l=3, r = 5$, here $mid = 4$ however your $md = 5$ which is wrong valueIf anything isn't clear please don't hesitate to ask
•  » » » 2 months ago, # ^ |   0 you are such an amazing person, thank you so much (can thank you enough), you even checked why my answer is not working , thanks a ton mate
•  » » » » 2 months ago, # ^ |   0 nothing to thank for my friend :3. Have a great day and keep the good spirit :)
 » 2 months ago, # |   0 D is nice
 » 2 months ago, # |   0 Can anyone pls help me with my solution .idk wht i am doing wrong https://codeforces.com/contest/1941/submission/251038815
 » 2 months ago, # |   0 https://codeforces.com/contest/1941/submission/250877308I implemented this solution but i am getting wrong answer :( i even checked with the editorial its the same :(
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 17418 from CF Stress for a counter example.
 » 2 months ago, # | ← Rev. 2 →   0 Could anyone please help me with the Problem 'C'. I am getting a wrong answer for test 2.[contest:https://codeforces.com/contest/1941/problem/C]Please find my submission below: 251308448
•  » » 2 months ago, # ^ |   0 Try: 1 3 amp The answer should be 0.
•  » » » 2 months ago, # ^ |   0 Ohh, makes sense. I will have a look into it. Thank you
 » 2 months ago, # |   0 can g be solved by this approach. Basically we will visit the vertices in a bfs fashion firstly at a distance of 1(this includes all the vertices that are connected by the same color of subway line to src). Then we will take all those visited vertices at a distance of 1 and visit the next vertices. Also unlike the trivial bfs we won't mark the vertex visited the 1st time we reach it but only when all the edges incident on the vertex are traversed.
 » 2 months ago, # |   0 This question is pretty similar to https://leetcode.com/problems/bus-routes/description/, one of the most asked questions in Google.
 » 2 months ago, # |   0 help about c++17 in problem G at test 3's wa #include using namespace std; #define int long long int n,m; struct edge{ int to,w; }; vector e[400001]; int dis[400001]; struct node{ int id,dis; bool operator<(const node &A)const{ return dis>A.dis; } }; priority_queue p; bool vis[400001]; void dij(int s){ memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; p.push(node{s,dis[s]}); while(!p.empty()){ node u=p.top(); p.pop(); if(vis[u.id]){ continue; } vis[u.id]=true; for(edge i:e[u.id]){ if(dis[i.to]>dis[u.id]+i.w&&!vis[i.to]){ dis[i.to]=dis[u.id]+i.w; p.push(node{i.to,dis[i.to]}); } } } } int tot=0; signed main(){ ios::sync_with_stdio(false); int cases; cin>>cases; while(cases--){ cin>>n>>m; tot=n; map mapping; for(int i=1;i<=m;++i){ int x,y,z; cin>>x>>y>>z; if(!mapping.count(z)){ mapping[z]=++tot; } e[x].push_back(edge{mapping[z],1}); e[y].push_back(edge{mapping[z],1}); e[mapping[z]].push_back(edge{x,0}); e[mapping[z]].push_back(edge{y,0}); } int b,eu; cin>>b>>eu; dij(b); cout<
 » 2 months ago, # |   0 Can any one help me please ,why i am getting WA in F (https://codeforces.com/contest/1941/submission/253003605)
 » 6 weeks ago, # |   0 In problem D TCx is written n*m however at worst case there can be n elements inserted in set so the complexity should be something like O(m*nlogn) (bcoz insertion in set is log(n)).I am not getting it plz somebody explain.
 » 6 weeks ago, # | ← Rev. 5 →   0 Have anyone managed to complete D using recursion? I tried but I am getting TLE. Here is my submission: https://codeforces.com/contest/1941/submission/257239620.I dont know any other languages as efficiently as python so I tried using python. But IDK how to optimize it further. Can someone help me?
»
3 weeks ago, # |
0

why i got tle in problem number b.

# include <bits/stdc++.h>

using namespace std;

# define ll long long int

void solve() { long long int n; cin>>n; vectorv(n); for(long long int i=0;i<n;i++) { cin>>v[i]; }

for(long long int i=1;i<n-1; )
{
if(v[i-1]!=0&&v[i+1]!=0&&v[i]>=2){
v[i-1]=v[i-1]-1;
v[i]=v[i]-2;
v[i+1]=v[i+1]-1;
}
if(v[i-1]==0||v[i+1]==0||v[i]<2)
{
i+=1;
}

}

int flag=0;
for(long long int i=0;i<n;i++)
{
if(v[i]!=0)flag=1;

}
if(flag==1)cout<<"NO\n";
else cout<<"YES\n";

}

int main() { int t; cin >> t; while (t--) { solve(); } return 0; }