awoo's blog

By awoo, history, 2 months ago, translation, In English

1469A - Regular Bracket Sequence

Idea: BledDest

Tutorial
Tutorial is loading...
Solution 1 (BledDest)
t = int(input())
for i in range(t):
    s = input()
    if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
        print('YES')
    else:
        print('NO')
Solution 2 (BledDest)
t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    a = [s[i] for i in range(n)]
    cnt = n // 2 - 1
    for j in range(n):
        if a[j] == '?':
            if cnt > 0:
                cnt -= 1
                a[j] = '('
            else:
                a[j] = ')'
    bal = 0
    minbal = 0
    for j in range(n):
        if a[j] == '(':
            bal += 1
        else:
            bal -= 1
        minbal = min(bal, minbal)
    print('YES' if bal == 0 and minbal >= 0 else 'NO') 

1469B - Red and Blue

Idea: BledDest and adedalic

Tutorial
Tutorial is loading...
Solution 1 (Ne0n25)
#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> r(n);
	for (int &x : r) cin >> x;
	int m;
	cin >> m;
	vector<int> b(m);
	for (int &x : b) cin >> x;
	partial_sum(r.begin(), r.end(), r.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
}

int main() {
	int t;
	cin >> t;
	while (t--) solve();
}
Solution 2 (pikmike)
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
	dp[0][0] = 0
	ans = 0
	for i in range(n + 1):
		for j in range(m + 1):
			if i < n:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
			if j < m:
				dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
			ans = max(ans, dp[i][j])
	print(ans)

1469C - Building a Fence

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }
        val h = readLine()!!.split(' ').map { it.toInt() }

        var mn = h[0]
        var mx = h[0]
        var ok = true
        for (i in 1 until n) {
            mn = maxOf(mn - k + 1, h[i])
            mx = minOf(mx + k - 1, h[i] + k - 1)
            if (mn > mx) {
                ok = false
                break
            }
        }
        if (h[n - 1] !in mn..mx)
            ok = false
        println(if (ok) "YES" else "NO")
    }
}

1469D - Ceil Divisions

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n;

inline bool read() {
	if(!(cin >> n))
		return false;
	return true;
}

void calc(int n, vector<pt> &ans) {
	if (n == 2)
		return;
	
	int y = max(1, (int)sqrt(n) - 1);
	while (y < (n + y - 1) / y)
		y++;
	
	fore (pos, y + 1, n)
		ans.emplace_back(pos, n);
	ans.emplace_back(n, y);
	ans.emplace_back(n, y);
	
	calc(y, ans);
}

inline void solve() {
	vector<pt> ans;
	calc(n, ans);
	
	cout << sz(ans) << endl;
	for(auto p : ans)
		cout << p.first << " " << p.second << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1469E - A Bit Similar

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;                 
int q;
char buf[N];
int n, k;

int ceilLog(int x)
{
    int y = 0;
    while((1 << y) < x)
        y++;
    return y;
}

int main()
{
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", buf);
        string s = buf;
        int m = min(k, ceilLog(n - k + 2));
        vector<int> used(1 << m, 0);
        vector<int> next0(n, int(1e9));
        if(s[n - 1] == '0')
            next0[n - 1] = n - 1;
        for(int j = n - 2; j >= 0; j--)
            if(s[j] == '0')
                next0[j] = j;
            else
                next0[j] = next0[j + 1];
        int d = k - m;
        for(int j = 0; j < n - k + 1; j++)
        {
            if(next0[j] - j < d)
                continue;
            int cur = 0;
            for(int x = j + d; x < j + k; x++)
                cur = cur * 2 + (s[x] - '0');
            used[((1 << m) - 1) ^ cur] = 1;    
        }
        int ans = -1;
        for(int j = 0; j < (1 << m); j++)
            if(used[j] == 0)
            {
                ans = j;
                break;    
            }
        if(ans == -1)
            puts("NO");
        else
        {
            puts("YES");
            string res(d, '0');
            string res2;
            for(int j = 0; j < m; j++)
            {
                res2.push_back('0' + (ans % 2));
                ans /= 2;
            }
            reverse(res2.begin(), res2.end());
            res += res2;
            puts(res.c_str());
        }
    }
}

1469F - Power Sockets

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (pikmike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int INF = 1e9;

int n, k, nn;

vector<long long> t, ps;

void push(int v, int l, int r){
	if (l < r - 1){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v] * (r - l);
	ps[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int val){
	push(v, l, r);
	if (L >= R)
		return;
	if (l == L && r == R){
		ps[v] = val;
		push(v, l, r);
		return;
	}
	int m = (l + r) / 2;
	upd(v * 2, l, m, L, min(m, R), val);
	upd(v * 2 + 1, m, r, max(m, L), R, val);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

long long get(int v, int l, int r, int L, int R){
	push(v, l, r);
	if (L >= R)
		return 0;
	if (l == L && r == R)
		return t[v];
	int m = (l + r) / 2;
	long long res = get(v * 2, l, m, L, min(m, R)) + get(v * 2 + 1, m, r, max(m, L), R);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int trav(int v, int l, int r, int cnt){
	push(v, l, r);
	if (l == r - 1)
		return l;
	int m = (l + r) / 2;
	push(v * 2, l, m);
	push(v * 2 + 1, m, r);
	int res = INF;
	if (t[v * 2] >= cnt)
		res = trav(v * 2, l, m, cnt);
	else if (t[v * 2 + 1] >= cnt - t[v * 2])
		res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int main() {
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	sort(a.begin(), a.end(), greater<int>());
	nn = a[0] + 500;
	t.resize(4 * nn);
	ps.resize(4 * nn);
	upd(1, 0, nn, 0, 1, 1);
	int fst = 0;
	int ans = INF;
	forn(i, n){
		while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
		upd(1, 0, nn, fst, fst + 1, -1);
		upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
		upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
		ans = min(ans, trav(1, 0, nn, k));
	}
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}
 
 
 
 
  • Vote: I like it
  • +121
  • Vote: I do not like it

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

Here is an attempt to make a unofficial video editorial of Educational Round 101 by COPS IIT BHU (in Hindi-English) (Problem A-E).

Do check it out.

https://codeforces.com/blog/entry/86076

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

    The editorials are great man ! Pls regularly upload on YouTube :)

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

    Sorry for this comment.

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

      No, it is right since Xi is refering to the height of the BOTTOM of block from common ground

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

        But I realized at this moment that they have not considered +k in initial segment itself.

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

    Can anyone give me a corner case for this submission or tell me how to fix this solution?

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

    Thank you for the video editorial. Really helpful for understanding and learning.

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

Pretty optimal solution of D if you fixed 8 and all other numbers from 3 to n-1 divide by n to obtain 1. These numbers are n-4, and after that will remain 9 operations. So you can obtain 1 from n in no more than 6 operations, and 1 from 8 in 3 operations. Since there is don't need to build binary search, this solution will be realised much faster

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

    same goes to 16. You can fix 16 and then make all elements from 3 to n-1 except 16 to 1 by dividing with n (n-4 steps) and then every possible n will be divided by 16 to 1 in atmost 5 steps and then 16 to 1 in 4 steps by dividing by 2 so total would be n+5 atmost.

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

    I think you meant 1 from 8 in 3 operations (using 2 as the divisor).

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

    Thank you so much for this solution.

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

I'm little bit confused about this test case for problem A

"?))?"

shouldn't it return "NO"?

Or, am i missing something?

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

    The question mentions that initially there will be exactly 1 opening bracket and exactly 1 closing bracket

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

    This is not a valid test case for problem A. Unfortunately, I think you missed this statement: "There is exactly one character ( and exactly one character ) in this sequence." (I also missed this statement initially and wasted an hour because of it)

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

    The question says there is exactly one of both.I wasted my time too ignoring this fact.

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

    I was also confused but later I got problem A says : There is exactly one character ( and exactly one character ) in this sequence.

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

In problem C, suppose the last fence's ground level is Hn. Why can't Hn be between(inclusive) [mn[n-1]-(k-1),mx[n-1]+k-1]

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

    According to the problem statement, the first section and the last section must stand on the ground.

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

      Yeah Thats what I am saying. In have a range mx and mn fof last second fence bcz it can move. I just wanna check for last fence it it can be somewhere between this range.

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

        You mean your code? Include a link next time then.

        In your code, looks like the former solution is wrong because it does not update l and r for the last section. Try changing for(int i=1;i<n-1;i++){ to go to i<n instead.

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

          Okay

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

          what if in given qsn C, the height/length of fence is not constant i.e. not 'k' for all.. then how to approach??

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

            Have you tried applying the same idea, about going from left to right and maintaining a segment of possible positions?

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

Can someone explain C in simpler words , its tricky for me rightnow

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

    We have got an uneven ground (better if you think of them as unit wide platforms at possibly different heights) with level at point $$$i$$$ being $$$H[i]$$$ (size $$$n$$$).

    We also have n fence_wood_sections (fws) all of whose dimensions are same and more importantly height being $$$k$$$ (width assume unit length) and $$$i th$$$ fws is to be placed above point $$$i$$$ on the ground (whose height is denoted in H[i]).

    For all $$$1 < i < n$$$ we can keep the distance between ground and bottom of fws at max $$$k - 1$$$ (1st and last ones should have 0 distance from their respective ground levels) and each consecutive fws(es) should have a vertical overlap of at least 1 unit (as we need to glue / nail them together as we respect gravity). Now you are to tell whether this is possible to do or not.

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

    Keep the maximum and minimum y-coordinate of bottom each section from left to right. And then don't forget that last section must be in the land (coordinate h[n-1])

    Let's minimum of the current section is d, and maximum is u. The next section must touch the current one, so difference of its coordinates no more than k-1 by abs. value. Then minimum of the next section is max(h[i], d-k+1) and maximum is min(u+k-1, h[i]+k-1) where h[i] is the height of the next place

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

      what is a[i] and h[i]?

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

        Height of the place. I forgot replace a[i] with h[i], cos i wrote my code with a[i]

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

      Why would this always give the answer?

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

        Segment [d1; u1], where d1 and u1 is minimum and maximum for next section, is intersection of segments [d-(k-1); u+(k-1)] and [h[i]; h[i]+(k-1)] So it's possible to choose any coordinate in segment [d; u] for all sections except first and last one

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

      Sorry for this comment

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

    Now I think you were asking for explanation of solution. Damn me.

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

Ended up doing 1469A — Regular Bracket Sequence using DP. Never read that there are only one '( and')' in the input string. Ended up costing me a lot of time thankfully the constrainst were quite small for a O(1) soln.

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

How to prove in D editorial that number of such segments isn't more than log(log n)?

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

    This SO answer has a pretty good explanation.

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

    We can observe that left boundary of segment can be represented by $$$n^{1/2^x}$$$ where $$$x$$$ is number of the segment , now process will stop when $$$n^{1/2^x} <=2$$$ , taking log both sides we get $$$(1/2^x)*logn <= C$$$ , where $$$C$$$ is constant depending on base of log (if base is 2 then C=1).

    Now equation can be written as $$$logn <=C*2^x$$$ . Take log both sides one more time , $$$log(logn) <= log(C)+x*C$$$ i.e $$$(log(logn)-log(C))/C <= x$$$ hence $$$x$$$ is $$$ceil((log(logn)-log(C))/C)$$$ , constant factors can be ignored , for log base 2 it will be $$$ceil((log(logn)-1))/2)$$$

    You can read properties of log if you are not able to get some step.

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

I can't understand the tutorial for question no.3 please help.

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

What should the test case "())?" and "()))" return for A? It returns "YES" according to the code, but I feel like it should be NO? It doesn't look like an RBS, or am I not understanding what RBS is?

Can someone please explain? Thanks!

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

    Both of your examples are invalid inputs as it is mentioned in the question that "There is exactly one character ( and exactly one character )". So, it should have only one character '(' and only one ')'.

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

When will the rating of all problems be added?

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

How to do A when the condition of only one ( and ) is removed?

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

    length should be even. edit: if you meant there are only '?'

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

      No any number of '(' ,')' and '?'

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

        checkout submission by handle "neal" and for explanation take a look at the post-contest stream he did on Twitch

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

    The first observation to make is that the length of the final string (when we replaced all the '?') should always be even and the count of '(' should be the same than the count of ')' (because '(' and ')' must balance themselves).

    Now, what we wanna do is find the most optimal way to place '(' and ')'.

    Let's imagine we placed some ')' before a '('. This is not optimal because maybe we will need the ')' later to close a '('. So placing all the '(' and then all the ')' will always be optimal.

    The algorithm is the following:

    • Place '(' till count('(') < len(s)/2

    • Then fill the remaining '?' with ')'

    • Check if the string is a valid RBS

    To check if the string is a valid RBS you need to maintain the balance of the parenthesis.

    Let's assume that '(' is +1 and '(' is -1.

    1. The total balance should be 0 (because we need to have the same ammount of '(' and ')' )
    2. At each index of the string, the current balance must be >= 0. In fact, if the balance is negative at index i, then we have more ')' than '(' in prefix [0, i] of the string.

    PS: what I mean by balance of prefix [0, i] is just the sum of the value of the parenthesis from index 0 to index i

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

Anyone help me where my code is getting wrong for problem E ?

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

Is ())(() a valid input for A problem? If yes, shouldn't the output be 'NO'?

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

    No, there should be only one ')' and one '(' characters as per question. Read the question carefully or the comments above.

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

Wow, Eduactional Round 101 getting exactly 101 contribution

»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int m,n;
        cin>>m;
        vector<int>v(m),v1(n);
        for(int i=0;i<m;i++)
            cin>>v[i];
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>v1[i];
        int maxi=0,run_max=0;
        for(int i=0;i<(min(m,n));i++)
        {
            run_max+=v[i];
            if(run_max>maxi)
                maxi=run_max;
            run_max+=v1[i];
            if(run_max>maxi)
                maxi=run_max;
        }
        int i=min(m,n);
        for(int j=i;j<max(m,n);j++)
        {
            if(m>n){
                run_max+=v[j];
                if(run_max>maxi)
                    maxi=run_max;
            }
            else if(m<n){
                run_max+=v1[j];
                if(run_max>maxi)
                    maxi=run_max;
            }
        }
        cout<<maxi<<endl;
    }
    return 0;
}

What is wrong with this code for B it shows runtime error on test 2

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
         int m,n;
            cin>>m;
            vector<int>v(m),v1(n);
            for(int i=0;i<m;i++)
                cin>>v[i];
            cin>>n;
    

    You declare a vector of lenght "n", while n has an undefined value

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

D problem has cheat-solution.

We can for one operation remove number $$$a_x$$$ from array if $$$\exists y, a_x < a_y$$$. So let's delete all numbers except $$$n$$$(we can't remove it). Also we won't delete $$$2^k, 2, \lfloor{\sqrt{n}} \rfloor$$$. Using two operations we can divide $$$n$$$ to $$$\dfrac{n}{\lfloor\sqrt{n}\rfloor} = n^\prime$$$ and $$$\lfloor{\sqrt{n}} \rfloor$$$ to $$$1$$$. Then let's divide $$$n^\prime$$$ by $$$2^k$$$ until it is $$$1$$$. So if $$$d(n , k)$$$ is number of operations needed to divide number $$$n$$$ by $$$2^k$$$, we need $$$d(n^\prime, k)$$$ operations to do it. Also we need to divide $$$2^k$$$, it will take $$$k$$$ operations. We will use $$$(n - 5) + d(n^\prime, k) + k + 2$$$ operations, so we need $$$d(n^\prime, k) + k + 2 \leqslant 10$$$, which can be easily secured. In my case $$$k = 2$$$ worked. (for all numbers less than $$$1000$$$, $$$d(x, 2)$$$ will be less than $$$5$$$)

Maybe we can find such $$$k$$$, that we don't need to reduce $$$n$$$ to $$$n^\prime$$$. It is much easier than author's solution, and also can be easily implemented, and it doesn't need observations like "number of iterations needed sqrt to become 1 is $$$\log \log n$$$"

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

It's possible to solve F in $$$O(n)$$$.

The bound on the $$$l$$$ values means these can be sorted in linear time. Moreover, instead of doing range updates, we can simply save where the two ends of the chain currently being used will end. This allows us to just iterate through the $$$cnt$$$ array. Solution: 103280970 (unfortunately probably unreadable) and some C++ nerds could probably speed up this idea to get the lowest execution time here too.

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

wait C makes no sense, for the second constraint, it says the first and last sections needs to be the same height. In the first test case in the first test, the graph shows that the first and last sections are on different ground levels or height but the output for it is still YES, why is that?

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

    They have to be placed on the ground. Not on the same height

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

      oh ok thank you that makes sense. Do you happen to understand the editorial for C though? It's kind of confusing for me.

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

In the explanation of problem C, can anyone explain why does a solution exist if the condition given in the tutorial is satisfied

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

...

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

can any one explain, in problem D) why there are atmost log(logn) segments?

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

    we could get this result in the following way: $$$\newline$$$ Let there be k segments. In recursion, from [1,n], we will go to [1,$$$n^{1/2}$$$], then [1, $$$n^{1/4}$$$], and so on up to [1,2] (because this is base case, and we cant go further after reaching 2). so the First segment has upper bound n (or $$$n^{1/2^0}$$$) ( its range is ($$$n^{1/2}$$$, $$$n^{1/1}$$$] ), second segment has upper bound $$$n^{1/2^1}$$$ (its range is ($$$n^{1/4}$$$, $$$n^{1/2}$$$]), third has $$$n^{1/2^2}$$$, and finally kth segment has upper bound $$$n^{1/2^k}$$$ which is actually 2. $$$\newline$$$ So $$$n^{1/2^k}$$$ = 2. Solving this you will get the answer :)