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

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
33:05:05
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя spookywooky

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

Автор spookywooky, история, 5 лет назад, По-английски

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 лет назад
26

Комментарии (23)

Показать архивные | Написать комментарий?

spookywooky

5 лет назад, # |

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.

→ Ответить

zephxr

4 года назад, # ^ |

← 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.

→ Ответить

spookywooky

4 года назад, # ^ |

Which part is unclear? The statement or the solution?

→ Ответить

zephxr

4 года назад, # ^ |

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

→ Ответить

spookywooky

4 года назад, # ^ |

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.

→ Ответить

zephxr

4 года назад, # ^ |

← 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 ?

→ Ответить

spookywooky

4 года назад, # ^ |

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.

→ Ответить

zephxr

4 года назад, # ^ |

You mean to say

0 1 is segment 1

1 2 is segment 2

2 3 is segment 3

and so on... spookywooky?

→ Ответить

mudit

4 года назад, # ^ |

light only belongs to the left segment

light on 1 means 1-1 and 2-n

→ Ответить

pllk

5 лет назад, # |

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

→ Ответить

snorkel

4 года назад, # ^ |

Fixed? Nothing has been changed. Can you recheck?

→ Ответить

MasterMind

5 лет назад, # |

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

→ Ответить

aboAdnan

5 лет назад, # ^ |

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

→ Ответить

MasterMind

5 лет назад, # ^ |

Thanks for the hint man

→ Ответить

15411019

5 лет назад, # ^ |

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

→ Ответить

qmk

5 лет назад, # ^ |

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() << ' ';
}

→ Ответить

15411019

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

rotavirus

5 лет назад, # ^ |

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

→ Ответить

qmk

5 лет назад, # ^ |

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];
}

→ Ответить