**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int index = 0;
int gap = 1;
while (index < n)
cout << s[index], index += gap, gap++;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << min(a[n - 2] - a[0], a[n - 1] - a[1]) << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
map<int, int> ans;
queue<int> q;
for(int i = 0; i <= 30; i++)
if(n & (1 << i))
{
if(i > 0) q.push(1 << i);
ans[1 << i]++;
}
if(int(ans.size()) > k)
{
puts("NO");
return 0;
}
int cnt = ans.size();
while(cnt < k && !q.empty())
{
int z = q.front();
q.pop();
ans[z]--;
ans[z / 2] += 2;
if(z / 2 > 1)
{
q.push(z / 2);
q.push(z / 2);
}
cnt++;
}
if(cnt < k)
{
puts("NO");
return 0;
}
puts("YES");
for(auto x : ans)
for(int i = 0; i < x.second; i++)
printf("%d ", x.first);
puts("");
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> a;
void check(int l, int r) {
vector<int> ans;
for (int i = 0; i < n; ++i) {
int nxt = -1;
if (a[l][0] == r) {
nxt = a[l][1];
} else if (a[l][1] == r) {
nxt = a[l][0];
} else {
return;
}
ans.push_back(nxt);
l = r;
r = nxt;
}
for (auto it : ans) {
cout << it + 1 << " ";
}
cout << endl;
exit(0);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
a = vector<vector<int>> (n, vector<int>(2));
for (int i = 0; i < n; ++i) {
cin >> a[i][0] >> a[i][1];
--a[i][0];
--a[i][1];
}
check(0, a[0][0]);
check(0, a[0][1]);
assert(false);
return 0;
}
```

1095E - Almost Regular Bracket Sequence

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
string rs(s.rbegin(), s.rend());
for (int i = 0; i < n; ++i) {
if (rs[i] == '(') {
rs[i] = ')';
} else {
rs[i] = '(';
}
}
vector<int> pref(n + 1), suf(n + 1);
vector<bool> okp(n + 1), oks(n + 1);
okp[0] = oks[n] = true;
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!okp[i] || !oks[i + 1]) {
continue;
}
if (s[i] == '(') {
if (pref[i] > 0 && pref[i] - 1 - suf[i + 1] == 0) {
++ans;
}
} else {
if (pref[i] + 1 - suf[i + 1] == 0) {
++ans;
}
}
}
cout << ans << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
typedef pair<long long, pair<int, int> > edge;
const int N = 200043;
int p[N];
long long a[N];
int get_leader(int x)
{
return (x == p[x] ? x : (p[x] = get_leader(p[x])));
}
bool merge(int x, int y)
{
x = get_leader(x);
y = get_leader(y);
if(x == y) return false;
p[x] = y;
return true;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%lld", &a[i]);
vector<edge> es(m);
for(int i = 0; i < m; i++)
{
scanf("%d %d %lld", &es[i].y.x, &es[i].y.y, &es[i].x);
es[i].y.x--;
es[i].y.y--;
}
int z = min_element(a, a + n) - a;
for(int i = 0; i < n; i++)
if(i != z)
es.push_back(mp(a[i] + a[z], mp(i, z)));
sort(es.begin(), es.end());
long long ans = 0;
for(int i = 0; i < n; i++)
p[i] = i;
for(auto e : es)
if(merge(e.y.x, e.y.y))
ans += e.x;
printf("%lld\n", ans);
return 0;
}
```

In problem C, what if the constraints for n and k are 10

^{18}? Is there any other better solution possible since the given one will run out of space and time !since in worstcase you need to print k numbers... there is no way... if we change the output format to print tuples (2^x, count) it is possible

Yes ! Completely forgot about it (maximum allowed output constraint)! Thanks..

I would like to know if my AC algorithm for problem D could actually be hacked somehow

https://codeforces.com/contest/1095/submission/47607217

What the program does is:

If the I kid remembers kids A and B in front of him, that means I is before A and B, so we draw two directed edges I->A, I->B.

There is an order to be decided between A and B that we don't know of yet, so we also draw a pointed line A---B between them.

When all the lines have been drawn, we iterate over each directed edge U->V, and if there was a pointed line U---V, then i assume the order U->V is indeed correct, so we add this directed edge U->V to an answer graph G. Note that there might be multiple solutions, so U->V and V->U might end up existing at the same time.

When we finished generating this answer graph G, visit all the nodes, starting from 0 and going to a

anynon-visited neighbor that we can go to through an edgeI think the

go topart might actually be hackableanyIn problem C, the for loop is from i=0 to i=30. As we know that 'int' is of 32 bytes,so I am unable to understand as to why the loop is not from i=0 to 31. Also I saw the codes of many programmers for the problem C and nearly everybody has done it from 0 to 30. So please explain the reason for this.

2

^{30}= 1073741824. You don't even need 30 in this cycle, 29 is pretty enough, because for numbers up to 10^{9}the maximum power of two in their representation is 2^{29}= 536870912.Ohk.. I understood it is due to the given constraint. Thanks!!

not just the given constrains , but actually bit number 31 is the sign bit so (1<<31) would give you negative number so as long as n is positive you don't need to worry about this bit (if you use integer not unsigned integer).

Where is editorial for problem 1095C - Powers Of Two?

P.S: "Unable to parse markup [type=CF_MATHJAX]" in spoiler.

Oops, sorry. Fixed now.

So my solution for D was completely different... I created a matrix in which placed the 2 neighbors for each kid. But how? Well, for example, if the next 2 kids after the first one are 3 and 5, 3 will be a neighbor for 5 and vice versa. Now i could just pick a number, go through this matrix and find the next one. But one more problem.. Sometimes the result was counter-clockwise, so i just added an extra condition : so for the first kid, i would go through that matrix and see which one of those is a 3 or a 5 (one of them), then pick it and do the same thing for it and so on. It was such a rushed solution, yet it worked and i am really please with it ;)

anyone please explain Problem E..I am unable to understand "if conditions in loop" especially.

Problem E can also be solved easily using a segment tree+lazy updates

actually just segment tree works, without the lazy updates.

true, didnt think of that thanks

Then i wonder how it is implemented

we convert the string to +1 and -1 (+1 when opening parens, -1 when closing parens) then we compute the cumulative sum array, and then we put the cumulative sum array in a segment tree.

To check if changing the i-th parens "fixes" the sequence we do the following: if the i-th element in the string is opening parens we subtract 2 from me segment [i,n] and if its a closing parens we add 2. (this simbolizes changing the parens to the oposite one) then we do rmq(0,n) and rmq(n,n) if rmq(0,n)<0 or rmq(n,n)!=0 then its an invalid sequence

the way i did it was in each node of the segment tree, I stored

While merging the nodes, observe that the unpaired opening brackets in the left can be paired with unpaired closing brackets in the right child.

In the end, just check whether the root has any unpaired opening or closing brackets.

The problem is similar to https://www.spoj.com/problems/BRCKTS/

Please give me the segment tree idea for problem E

https://codeforces.com/blog/entry/64130?#comment-480345

Thank You <3

Is there any easy explanation of problem E.

The problem is similar to this one SPOJ/BRACKETS

I am getting TLE with segment tree.

Here's a nice article about the implementation with segment trees (https://www.geeksforgeeks.org/range-queries-longest-correct-bracket-subsequence/)

Can you check https://codeshare.io/5MnWVe why I am getting TLE.

In E, can you explain your choice of indices for this part:

It seems arbitrary to me whether you'd do that or do something like

`pref[i] = pref[i-1] + (s[i] == '(') : 1 : -1)`

. The code is actually different, but I don't understand the difference.You can also solve F by Prim's algorythm with asymptotics O(NlogN+MlogN).

For Problem E with test case 8 )))((((( why is the answer 0? Can't I change it to ()()()() with modifications at positions 1, 3, 4, 6 and 8?

Because you can and only can change exactly one bracket according to the problem description

one type of bracket or just any one bracket (i don't get the logic for above example) , also then how come answer to 6 (((()) is 3

Just one bracket. Possible for (((()) : ()(()) ; ((())); (()())

In the D task:Why needs to decreases the input by one? I tried not to do and not works, but i don't get why needs to be done. Can someone explain to me?EDT:get itfor(int i = 0; i <= 30; i++) if(n & (1 << i)) //This if condition { if(i > 0) q.push(1 << i); ans[1 << i]++; } please explain what the first if condition in this piece of code does.

In problem C solution in the while loop why the if statement if(z/2>1) is given. please anyone explain it??

Because if you push 1 in your queue, then when 1 will get popped, ans[1/2]+=2 will happen, you cannot break 1 into two 0s, where as you can break other power of 2 into 2 parts to increase your count by 1

ohh thanks i got it.@siddharthp538

1095A — Repeating Cipher Solution & explanation :

https://cyclocoder.blogspot.com/2019/01/codeforces-1095a-solution-and.html

I m not satisfied with

B. Array Stabilizationtutorial logic which is given here ...because let's assume`5`

`2 4 8 2 7`

after doing sorting .. according to ur logic ans will bemin(7-2,8-2)=5that should bemin(7-2,8-4)=4and u didn't mention about that all element are distinct. if i was wrong please let me know

In problem C what is the function of map<int,int> ? and what it is doing in program i don't understand

The map stores the number of occurrences of various powers of 2. It comes in handy when we want to split a set-bit ( a power of 2 ) into two lesser powers of 2.

In problem E, in the first example, why the answer can't be

`()(())`

? this is a regular bracket sequenceIt can. You can flip positions $$$2$$$, $$$3$$$, and $$$4$$$ (1-indexed) while being valid in that test case, and your answer is a result of flipping the position $$$2$$$.

For 1095F, my algo is to generate all normal edges with cost and insert them into set with special edges(with their costs). Now ANS set to maintain the the edges for graph, the condition for insertion in this set will be that both vertices of edge(which is being inserted) should

nothave another edge connected to it, & that edge isnotpresent in ANS set, parallelly caculating the min_cost.In Problem D, why is the counter clockwise not acceptable?