https://cses.fi/problemset/task/1163

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:22:58
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

spookywooky's blog

https://cses.fi/problemset/task/1163

By spookywooky, history, 5 years ago, In English

Hello,

I am trying to solve https://cses.fi/problemset/task/1163, but got some problem to understand it. It states that "There is a street of length x whose positions are numbered 0,1,…,n. " That should be "0, 1,..., x", not n, isn't it?

Then the example:

Input:
8 3
3 6 2

Output:
5 3 3

I think output should be 5, 3, 2, not 5, 3, 3. Since obviously the longest segment without a traffic light is 2, not 3.

0 1 2 3 4 5 6 7 8
    x x     x

Can somebody explain? A lot of people solved that problem, I think I am missing something. Thanks.

#sorting, cses

spookywooky
5 years ago
26

Comments (23)

Show archived | Write comment?

spookywooky

5 years ago, # |

Found it by myself ;)

Two things one must notice:

There is an "implicit" traffic light after position 0. The length of the segment is calculated as without left bound, but including right bound.

So, the traffic lights are placed kind of "right of the positions". After adding the three lights, it looks like

0 1 2 3 4 5 6 7 8
 x   x x     x

The longest segment is the one "4,5,6", of length 3.

→ Reply

zephxr

4 years ago, # ^ |

← Rev. 2 →

spookywooky Can You Explain it in simple words.I am also stuck at this problem but not able to get it.Problem Statement is not clear.

Thanks in Advance!

PS-Why this post is getting downvoted?I have done nothing wrong.If asking a doubt is an offense to community then why a discuss section was made on Codeforces.This discuss section is made for discussing doubts and problems.

→ Reply

spookywooky

4 years ago, # ^ |

Which part is unclear? The statement or the solution?

→ Reply

zephxr

4 years ago, # ^ |

I am not getting the statement! i think the output should be 5 3 2 and not 5 3 3

→ Reply

spookywooky

4 years ago, # ^ |

The traffic lights are placed between the numbered segments of the street, after the given number.

In the testcase above there are 3 lights, at positions between 2 and 3, between 3 and 4, and between 6 and 7.

So the longest segment without a traffic light is {4,5,6} of size 3.

→ Reply

zephxr

4 years ago, # ^ |

← Rev. 3 →

After adding 6 wouldn't be answer 4 Because we have 3 segments which do not contain traffic lights :

0 1

1 2

2 3

and size is 4. I am sorry if its a dumb question but i can request if you can clarify this! spookywooky ?

→ Reply

spookywooky

4 years ago, # ^ |

Nah, the numbers are not the spaces between the segments, the numbers are the segments.

There is a segment 1, a segemnt 2 etc... We place the lights between the segments.

→ Reply

zephxr

4 years ago, # ^ |

You mean to say

0 1 is segment 1

1 2 is segment 2

2 3 is segment 3

and so on... spookywooky?

→ Reply

mudit

4 years ago, # ^ |

light only belongs to the left segment

light on 1 means 1-1 and 2-n

→ Reply

pllk

5 years ago, # |

You are right, the task statement had a typo. This has now been fixed, thanks!

→ Reply

snorkel

4 years ago, # ^ |

Fixed? Nothing has been changed. Can you recheck?

→ Reply

MasterMind

5 years ago, # |

Can you please give me a hint on how to solve this problem? I am stuck in it.

→ Reply

aboAdnan

5 years ago, # ^ |

Hint: Think about the number of segments that could be affected after adding a new traffic light.

→ Reply

MasterMind

5 years ago, # ^ |

Thanks for the hint man

→ Reply

15411019

5 years ago, # ^ |

Hey, I am still not able to figure it out, can you share your approach?

→ Reply

qmk

5 years ago, # ^ |

Solution

Code

int x, n, a[200002];
set <int> s;
multiset <int> m;
cin >> x >> n;
s.insert(0);
s.insert(x);
for(int i = 1; i <= n; ++i) {
	cin >> a[i];
	auto l = s.lower_bound(a[i]), r = --s.upper_bound(a[i]);
	if(*l > a[i]) --l;
	if(*r < a[i]) ++r;
	auto f = m.find(*r - *l);
	if(f != m.end()) m.erase(f);
	m.insert(a[i] - *l);
	m.insert(*r - a[i]);
	s.insert(a[i]);
	cout << *--m.end() << ' ';
}

→ Reply

15411019

5 years ago, # ^ |

← Rev. 2 →

Thank you :) Hey, If you know how to approach "Throwing dice"? https://cses.fi/problemset/task/1096

→ Reply

rotavirus

5 years ago, # ^ |

it is an easy linear reccurence:
$$$f(x) = \sum_{i=1}^{6} f(x-i)$$$ which can be solved by the matrix multiplication

→ Reply

qmk

5 years ago, # ^ |

Solution

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 2e5 + 5, mod = 1e9 + 7;
 
struct matrix {
	vector <vector<int>> a;
	matrix(int n, int m) {
		a.assign(n, vector <int> (m));
	}
	matrix operator * (const matrix &b) const {
		int n = a.size(), m = b.a.size(), p = b.a[0].size();
		matrix c(n, p);
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < p; ++j) {
				for(int k = 0; k < m; ++k) {
					c.a[i][j] = (c.a[i][j] + (a[i][k] * b.a[k][j]) % mod) % mod;
				}
			}
		}
		return c;
	}
};
 
matrix binpow(matrix n, int k) {
	int s = n.a.size();
	matrix ans(s, s);
	for(int i = 0; i < s; ++i) {
		ans.a[i][i] = 1;
	}
	if (k < 0) return ans;
	while(k) {
		if(k & 1) ans = ans * n;
		n = n * n;
		k >>= 1;
	}
	return ans;
}
 
signed main() {
	int n;
	cin >> n;
	if(!n) return cout << n, 0;
	matrix k(6, 6), ans(6, 6);
	k.a = {{0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1}};
	k = binpow(k, n - 6);
	ans.a[0] = {1, 2, 4, 8, 16, 32};
	if (n <= 6) return cout << ans.a[0][n - 1], 0;
	ans = ans * k;
	cout << ans.a[0][5];
}

→ Reply