Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
from collections import deque
def solve():
n = int(input())
s = deque(input())
while len(s) > 0 and s[0] == 'W':
s.popleft()
while len(s) > 0 and s[-1] == 'W':
s.pop()
print(len(s))
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
cnt = [0] * 26
s = ''
for i in range(n):
for j in range(26):
if cnt[j] == a[i]:
cnt[j] += 1
s += chr(97 + j)
break
print(s)
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
cnt = [0] * (k + 1)
for e in a:
if e <= k:
cnt[e] |= 1
for e in b:
if e <= k:
cnt[e] |= 2
c = [0] * 4
for e in cnt:
c[e] += 1
if c[1] > k // 2 or c[2] > k // 2 or c[1] + c[2] + c[3] != k:
print("NO")
else:
print("YES")
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
p = [-1] * n
for i in range(1, n):
p[i] = p[i - 1]
if a[i] != a[i - 1]:
p[i] = i - 1
for i in range(int(input())):
l, r = map(int, input().split())
l -= 1
r -= 1
if p[r] < l:
print("-1 -1")
else:
print(p[r] + 1, r + 1)
t = int(input())
for _ in range(t):
solve()
if _ + 1 != t:
print()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n, k = map(int, input().split())
l, r = 1, n
ans = [0] * n
for i in range(k):
for j in range(i, n, k):
if i % 2 == 0:
ans[j] = l
l += 1
else:
ans[j] = r
r -= 1
print(*ans)
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const ll inf = 1e18;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
struct dsu{
vector<int> p, lvl;
dsu(int n){
p.resize(n);
iota(p.begin(), p.end(), 0);
lvl.assign(n, 0);
}
int get(int i){
if (p[i] == i) return i;
return p[i] = get(p[i]);
}
bool unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return false;
if(lvl[a] < lvl[b]) swap(a, b);
p[b] = a;
if(lvl[a] == lvl[b]) lvl[a]++;
return true;
}
};
bool found;
vector<int> ans, path;
void dfs(int v, int p, vector<vector<int>> &g, int f){
path.push_back(v);
if(v == f){
ans = path;
found = true;
return;
}
for(int u: g[v]){
if(u != p) dfs(u, v, g, f);
if (found) return;
}
path.pop_back();
}
void solve(int tc){
int n, m;
cin >> n >> m;
vector<vector<int>> sl(n);
vector<pair<int, pair<int, int>>> edges;
for(int i = 0; i < m; ++i){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
edges.push_back({w, {u, v}});
}
sort(rall(edges));
dsu g(n);
pair<int, int> fin;
int best = INT_MAX;
for(auto e: edges){
if(!g.unite(e.y.x, e.y.y)){
fin = e.y;
best = e.x;
}
else{
sl[e.y.x].push_back(e.y.y);
sl[e.y.y].push_back(e.y.x);
}
}
found = false;
path.resize(0);
dfs(fin.x, -1, sl, fin.y);
cout << best << " " << ans.size() << "\n";
for(int e: ans) cout << e + 1 << " ";
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));
d[0][0][0] = 0;
forn(i, n)
forn(j, n)
forn(k, n + 1)
if (d[i][j][k] < INT_MAX) {
int ai = a[i];
// Z
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : (k == 0 ? 1 : 0);
int nk = max(0, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k]);
}
// L
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : 0;
if (nj <= ai)
nj = 0;
int nk = max(0, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
}
// R
{
int ni = i + 1;
int nj = j > 0 ? j + 1 : 0;
int nk = max(ai - 1, k - 1);
d[ni][nj][nk] = min(d[ni][nj][nk], d[i][j][k] + 1);
}
}
cout << *min_element(d[n][0].begin(), d[n][0].end()) << endl;
}
}
Nice contest. Thnx, Mike!
No,I do not think so
Can't solve it nicely doesn't mean the contest is not nice.
skill issue
Good round!
The system testing is going on for last >4 hrs. Is there a way I can submit problems while system testing goes on for contests?
loved this round. the problems were so unique but system testing is not ending :'(
Exactly.
when will our rating will be updated? This is my First contest participation
Idk either:( we should wait
oh ok ;( thanks for the reply mate
Good round. I done abcde. We will be waiting for new and interesting rounds from MikeMirzayanov. Thanks for fast editorial.
Problems were really nice. Thanks!
Please someone tell me, why did I get TLE on problem B with this approach??
int main() { // Code int t; cin >> t;
int total = 0; while(t--) { int n; cin >> n; vector<int> arr; int temp; for(int i = 0; i < n; i++) { cin >> temp; arr.push_back(temp); } int freq[26] = {0}; string result = ""; // trace traversal for(int i = 0; i < n; i++) { // letter frequency traversal for(int j = 0; j < 26; j++) { if(arr[i] == freq[j]) { freq[j]++; // add the frequecy result = result + char(97 + j); break; } } } cout << result << endl; } return 0;}
i think problem in this:
result = result + char(97 + j);
you can use this instead:
result += char(97 + j);
ok :)
result = result + char(97 + j);This is a O(n^2) operation.
use this instead
result.push_back(char(97+j));ok thanks :)
The time complexity of push_back is how much?
$$$O(1)$$$ for sure. string = basic_string, and basic_string is just like a extended vector.
but "result = result + char(97 + j)" will have a worse time complexity because it is equivalent to string splicing and it is $$$O(N)$$$.
You're making things unnecessarily complicated. Take a look at my submission: 245110216
result = result + char(97 + j); This line gives tle because you are adding result in result this takes o(n^2) time that is why you are getting tle. to avoid this you can create a char array instead of the result string and add single elements to the array. Hope this helps.
s is a std::string, then s+='a' is O(1) but s = s+'a' is O(s.size()).
ac submission
The time complexity of str=str+str2 is O(2n) as it process both the string so it TLE's almost everytime on the large testcases .Use either str.push_back(str2) or str+=str2.
Here is a relevant link regarding this :
https://stackoverflow.com/questions/57132337/difference-between-string-s1-and-string-string-s1
fast editorial
Can someone tell when rating gets updated.
got updated
Here is how i explain C:
Same as Mike, i have:
Cnt0 = the number of x that only appear in A
Cnt1 = the number of x that only appear in B
(1<= x <= k )
(Remember, if a number satisfy Cnt1 condition -> both Cnt0 and Cnt1 is increased) Call Cnt0-k/2= y
So imagine that we have an answer array C of size k, then we put all numbers from A to C, and then what we do next is to replace each number in array C that belongs to A by numbers from B (we can choose to put a number in C from A/B if it appears in both arrays) -> Check if y <= Cnt1
When the answer if no? when there is x (1 <= x <= k ) that doesnt appear in both 2 arrays or y<0 (cant have enough k/2 numbers in C from A).
Sorry if my English is bad.
I did it like this.
I marked the values till k as 1 if they occurred in a, and same in b as well using two arrays mark_a[10^6+1], mark_b[10^6+1].
The iterate till k and do the following. mark the no of missing values in a and b.
if both of them have a missing value i.e
mark_a[i] == mark_b[i] == 0then answer is no, else if any of them have more thank / 2missing values then answer is no.if any of the above conditions aren't true then the answer is yes.
Here is my submission id 245227353
You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1
The last for loop is unnecessary btw you can remove it.
The solution will still get accepted.
Thanks For reading,
sorry if my explanation was bad.
it's my first idea, but i set the mark array limit to 2e5... and then i lost 20 mins more to figure out the idea in the tutorial
You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1no you cannot create mark_a and mark_b of length
k+1, why?let say
n=2andm=2andk=2you have array elements as{101,102}and{102, 103}thenmark_a[k+1]ismark_a[3]where you only have position0, 1, 2and so formark_b[3], now you don't have position101 102 103in your mark_a and mark_b where will you assignmark_a[101]=1ormark_b[101]=1.why you declare
mark_aandmark_bof size10^6+1is because that is the range ofarray elements 1<=a[i]<=10^6, so now for every possible element you have in array you have position where you will mark 1 if found in mark_a or mark_b.//(sorry for bad english)
i am saying you can't create mark_a or mark_b of length k+1 as per your code which will possibly generate out of bounds error 245227353
but you can create mark_a and mark_b of length k+1, if you check whether if a[i] or b[i] is <=k and then assign 1 as mark_a[a[i]]=1 or mark_b[b[i]]=1 246066103
Another idea for problem F
We can get all the bridges in the graph using Tarjan.
If the edge is a bridge then it's impossible to make a cycle by this edge.
Sort edges by weight and the first edge that is not a bridge surely will make a cycle, then find it by dfs.
submission: https://codeforces.com/contest/1927/submission/245226535
nice one(
Yess, I also used the same logic
Another idea is to count the number of encountered cycles on the DFS tree and figure out from those counts if an edge sits on some cycle.
You can do that by tracking the enter time
ins. Ifins[child]<ins[x], then you know you encountered a cycle. You increase the number of cycles that start withC[child]and the total number of cycles foundcycle_countand consider edge{x, child}for the minimum (as it sits on a cycle).When you exit the node that starts cycles, you decrease the cycle count
cycle_count-=C[x]andC[x]=0.If the
cycle_countwhen you exit the node is greater than the cycle count when you entered the node, then the edge from parent to that node is also on a cycle, so you can consider it for the minimum edge.Total complexity is $$$O(2\cdot m)$$$.
https://codeforces.com/contest/1927/submission/245472637
Hey! I am using the exact same approach but getting MLE. Can you please help. code
Amazing Implementation Skills
245202834 why it is wa 2? I'm trying to use two pointers help me please problem C
im not sure but I think that when in case of both you can just increase both variable by one and do nothing else and when you finish the loop just check if c1 and c2 both are less than or equal to k/2 and also check if the remaining space in both c1 and c2 is enough for the both variable
245205769 this is correct solution, but I uses maps. I want do the same things using two pointers^ but it as WA
Another solution for D: Build 2 segment trees on array: for min and max values on range (vertices store min/max value and index). Then we can answer on query: if
max(L, R).value==min(L, R).valuethen answer is-1 -1, elsemin(L, R).index max(L, R).indexcan be easily handled by building the tree with each node representing the position of the max/min value, not the value itself
This is exactly what I tried to do during the contest (as I've been studying segment trees and I'm in love with them lol)
I couldn't figure out the implementation details during the contest, but afterwards, I tried it and got TLE. I'm using Python, so maybe that's it, but I would like some help and feedback on my implementation:
TLE Submission
Sorry but i dont know much about python (cant even read the syntax). Here is my C++ code:https://codeforces.com/contest/1927/submission/245178309
Thanks! It's pretty much the same thing, with some optimizations (I really like how you avoid having two separate trees :). I'm sure the efficiency of C++ really helps as well.
I'll work on mine, and see if I can optimize it further
remember that python is about 4-5x slower than C++ (It's not allowed for national OI in my country lol)
Oh wow :_(
But that's valid, yes. Even with PyPy and all the possible optimisations, it is still really slow.
I've been trying to learn C++ recently, but I'm not comfortable enough yet to use it in a contest. It's one of my goals for this year though
You can use
time.time()to check which parts of code takes much time. It can be input parsing or building tree, taking query or outputing.Sometimes python may fail you just because it's slower than c++ (for example, python list acessing is quite slower than c++ native array).
You are right, the value actually is not required.
I used sparse tables instead, but the idea is the same
It's an overkill, but I did the same lol :P.
Can anyone share the $$$n^2$$$ solution about G? Thanks a lot.
My $$$O(n^2)$$$ submission: 245368999
Let $$$dp[i][j]$$$ be the minimum operations to paint all cells from $$$1$$$ to $$$j$$$ by only using charges before $$$i$$$-th cell.
Then for each cell $$$i$$$, we try to update the cells that can be reached from $$$i$$$. Make sure to contain the following case, that is, we use charge $$$i$$$ to paint the cells at left side of $$$i$$$, and use another charge (at $$$(i-a_1+1)$$$ ~ $$$(i-1)$$$) to paint the cells at right side of $$$i$$$. (See example testcase 8.)
This is my first time trying to write a comment, and I'm not good at explaining things ><. See my code for more details.
Hope y'all have a nice day :).
wow! are you anonymous LGM?
by the way, i couldn't understand your code even though i looked at it for an hour. forgive me for my stuipidness. if you don't mind, could you explain this part in more detail? : if (j >= l+1 && j <= i-1){int r2 = min(j+v[j]-1, n);dp[i][r2] = min(dp[i][r2], dp[j-1][max(l-1, 0ll)]+2);} i believe this part is the part you mentioned "Make sure to contain the following case, that is, we use charge i to paint the cells at left side of i ," but i really can't understand it.
Great round with unique problems, thanks!
Problem G
$$$O(N^{2})$$$ time complexity
UPDATED https://codeforces.com/contest/1927/submission/245921562
uhh, can you explain it ?
dp[i][j] is the rightmost index we can achieve(filling all the prefix..) if we have first i elements of the array and we have used j of them. final answer is minimum j that dp[i][j] >= n in each step we can either pick the i th element and use it to the left either to the right .
there is one more case when we pick 2 elements(A and B) .....A.....B.....
and use A to the right and B to the left(other cases to use left and right is not optimal.. I can prove)
KLEFT[i](you can see the implementation) pair shows the rightmost two k values, if we use the k th element to the left and it covers from i to k segment
This is my $$$O(N^{3})$$$ solution which easily can be optimized to $$$O(N^{2})$$$ https://codeforces.com/contest/1927/submission/245217545
I think it got WA?
D using Segment Tree too.
Could you please explain the dry run of the solution of E. Suppose, n=7, k=4 Why, the permutation 1,4,5,7,2,3 6 would not be valid? Why I have to take in this way: 1,8,3,5,2,7,4 ?
The differents values of sum ok k elements from left to right are 17, 18, 19, 18, so the difference between minimal and maximun is 2 > 1 so It will not work. The apprroach to resolve E and minimize the answer is going to alternate maximum value and minimum, You can have one number i, and inscrease it each time, for odd indexes give number from left, and for even indexes give it from right.
1.1+4+5+7=17 2.4+5+7+2=18 3.5+7+2+3=17 4.7+2+3+6=18 So the difference of sum of k value doesn't exceed more than 1.
Sorry I took the case : 1,8,3,5,2,7,4
Another idea of problem G:
Because every cell must be colored, I considered greedy.
Enumerate each $$$i$$$ from $$$1$$$ to $$$n$$$, suppose that at this moment, all cells from $$$1$$$ to $$$i-1$$$ are colored.
Thinking greedily, it is definitely necessary to color as many cells as possible in $$$i+1$$$ to $$$n$$$ while coloring the cell $$$i$$$, suppose the number as $$$l$$$.
So preprocess the one with the highest number of stained cells out of all the painting schemes starting with $$$i$$$.
Then it is easy to dynamically maintain the $$$l$$$ for each $$$i$$$.
I am not sure if this algorithm is correct. It is even $$$O(N)$$$.
upd: this algorithm is probably wrong. In the last case of the sample, my implementation will use $$$a_3$$$ twice.
the algorithm won't work on many cases
Could you give me an example?
1 1 1 1 1 1 | 0 0 0 0 0 0 0 0 0 0 0
1-> means colored cell , 0 means not colored
according to your algorithm in next step this happens
1 1 1 1 1 1 | 1 1 1 1 1 1| 0 0 0 0 0
then you start considering from first cell of 3rd part and it can happen they only paint themselves and they require total 5 steps to be painted
but it could happen that among the unconsidered cells in 2nd part one could paint till the nth cell to the right direction
I realised this, so I didn't skip the cells that were already coloured, instead considering the contribution of these cells to $$$l$$$.
But $$$R$$$ could give you better answer right?
what is "R"? My $$$l$$$ is clearly defined in the algorithm description.
why don't you just implement to check whether it really works?
it won't improve the time complexity
I got TLE ON problem D with binary search any one have an idea why ? https://codeforces.com/contest/1927/submission/245354533
u are passing the vector instead of a reference to it to the function look at this:
https://codeforces.com/contest/1927/submission/245372067
yes you are right it passed now thanks
Thank you for the contest. I finally reached expert.
Interesting pset. Thanks!
hey , the contest counted as unrated for me and I have solved a problem ?????
Can someone explain me why the author’s solution for problem B is not of complexity O(N^2)? I would assume doing s += chr(97 + j) to be of O(N) since strings are immutable and don’t have append in amortized O(1) like lists do
no its o(1) search on the internet strings are mutable you can append at the back but if you want to append at the beginning then it will be o(n)
@SuperMo I don't understand your answer, strings aren't mutable in Python and the author's solution is in Python
yeah sorry I thought it was c++
Is it possible to detect whether an edge belongs to a cycle by just DFS in linear time?
Yes, moreover — there is an algorithm for finding all bridges in a graph in linear time, based on dfs
Looks like a more or less normal description of this algorithm: https://cp-algorithms.com/graph/bridge-searching.html
Thanks for the tutorial. I was said that G can be resolved in O(n^2) can someone say me how?
Can someone explain G in simple terms
in my dp solution of $$$G$$$ I have 3 states :
here is the code tell me if you don't understand the transitions
can someone please explain the editorial of $$$F$$$ in details?
A. For the first part, we use DSU to find out which vertexes are connected. For each edge (u->v), if u and v is already connected, then this edge completes cycle.
B. We should iterate through each edge only once. And we should iterate descending order to find minimal weight edge. Consider three vertexes v1, v2, v3 form a cycle. Evaluating first two edge will make all three vertexes connected together. Then evaluating the third edge u->v will found out u and v is already connected, thus we can claim the third edge completes the cycle. If we don't iterate edges in descending order, the third edge might have bigger weight than first two edge!
C. For the second part, there exists two paths from u to v. The minimal edge, and longer path without minimal edge. To travel in a cycle, we travel u -> v without minimal edge. Then we travel v -> u with minimal edge. If we want to find the path without minimal edge, simply exclude the minimal weight edge from graph and use DFS.
My submission with some comments: 245285224
thanks
Anyone resolved the problem D with Segment Tree?
Find min and max in range and check they if they are equal then there is no possible pair else you can print the index of min and max values. My solution
Thanks! :)
Can anyone tell me why is this giving wrong answer (for problem F). 245356240
My idea here is, find the 2 nodes with minimum edge weight(say n1 & n2) and then do dfs from one of the node(n1) untill you reach another node(n2). In this way you will end up finding a cycle.
What is wrong in this??
There may not always exist a simple cycle including the minimum edge.
Consider this:
1
6 7
1 3 2
1 2 4
2 3 3
3 4 1
4 5 5
4 6 6
5 6 7
The lightest edge is "3 4 1". However, no cycle includes it.
Ahh Thanks
1927D - Найди различные! is required almost similar thought as 622C - Не равный на отрезке.
Не знал, что в Диве 3 встречается снм
Can someone explain Problem E in an easier way? I thought of switch alternately between largest evens and largest odds but that doesn't seem to work. UPD: I solved it. Used the intuition to increase the values at even indices and decrease at odd indices.
Excellent contest.
Is a very nice competition.The question is quite thought-provoking.I like it.
Can somebody please look into this submission of b and tell why I am getting TLE? Thank you. https://codeforces.com/contest/1927/submission/245142912
$$$\mathcal{O}(n^2)$$$ too bad for B
Thanks for the reply, I actually found out about the error(it was in my declaration of vector v); The complexity is not O(n^2), it has nested loops but it is accessing the indexes only once;
I am getting a memory limit exceeded error on test case 27 in code 245453024
For problem F, can anyone tell me how to solve it if it also asks to minimize the number of vertices in the found cycle? Thanks.
This is unsolvable within the problem constraints, as if you give the same weight to all edges, the problem turns into figuring out the shortest cycle in the graph .This is a well known problem and the fastest solution for it is $$$O(nm)$$$.
waiting for a rollback :(
Anyone knows how to solve DFS problems in Python? I seem to encounter runtime errors (I assume it's segmentation fault).
For problem F, I found an $$$O(m)$$$ algorithm. 1 DFS to find the minimum edge on a cycle and 1 DFS to get that cycle.
I do
sys.setrecursionlimit(10**6)but it will not pass in Python. The same algorithm in C++ passes, but I assume if recursion gets deep enough, even C++ will not be able to do it.Is it the case that for $$$n > 10^5$$$ I should not use DFS? I'm not sure if there's a pattern to iterative DFS (stackless) but I find it a bit hard to shuffle the moments when I'm leaving the node and which metadata to keep.
As a Python user, I have some advice for you. Recursive functions can be inefficient in Python, so it's best to avoid using them whenever possible. If you need to implement depth-first search (DFS), consider using a stack instead of recursion. Alternatively, you can explore other algorithms. For example, in this problem, you could use Union-Find (Disjoint Set Union, DSU) to find the minimum edge and Breadth-First Search (BFS) to detect cycles.
Thanks for the suggestion. The DFS works fine with CPython 3.10+ (not available on codeforces). I guess if I used union-find I'd have to write an iterative find, right, a recursive one can also break?
This change in Python made the DFS work: https://docs.python.org/3/whatsnew/3.11.html#inlined-python-function-calls
Is there an example of a correct way to think about DFS+stack. I think I would have to be careful to not push a node multiple times. If I need to do something when exiting the node (when all of the children are completely processed), then I need to not exit it twice. I also cannot pop immediately the node of the stack.
If graph is not a tree, then I have to keep track of which nodes are pushed to the stack and not push them again. But I also have to keep track of which nodes I visited.
To impliment path compression of union-find, recursion is enough. Pay attention to the depth of recursions. the depth of the union-find tree is small enough if you perform path compression each time you unite two elements. However, considering dfs on a linear graph, the depth is too large. It causes no problem if the depth is small (like $\le 10^3). In fact, I could get AC with recursive union-find even in Python3 (not PyPy).
Regarding the way of rewriting DFS as DFS+stack, I'll show you two solutions to the problem:
The dfs part of the cycle construction only differs, but they have the same result. (But rewriting is hard for me at least, I used bfs during the contest.)
Looking at your stack solution, if you want to support extra processing on node exit (for example, let's say you're calculating number of children), You would have to also keep track if you exited a node already (not to overcount children). I guess I'm on the right path there, but the +/- trick is useful.
I tried the stack solution for Problem F (with bfs for cycle):
https://codeforces.com/contest/1927/submission/245556453
But it says it takes too much memory.
Thanks again, I guess it's just memory heavy.
I am trying to solve 1927D - Найди различные! using MO's algorithm. But, getting TLE. plz help me!!!
you don't need mo's algo for that. use monotonic stack instead
thanks a lot. but, recently i am trying to solve MO's algo related problems. that's why i tried this using MO's. this is my submission.
Does anyone know if there are any traps in Test 19 of Problem F? It seems that the sorting of edges requires O(mlogm), and the DFS to find a path requires O(n), but I keep getting TLE. Or am I just too silly to see some stupid bugs 245508630? I would really appreciate some advice!
Found the mistakes. No problem now!
Why my DFS in F TLE in Test19 https://codeforces.com/contest/1927/submission/245777873
I mistakenly declared an adjacency matrix (n*n elements) instead of an adjacency list (n*0 elements), and therefore got an TLE. I am not familiar with Java, so I'm not sure whether you stumbled upon the same mistake. It seems that Test 19 may have a large n, so maybe you can check whether you declared the graph correctly or made some mistakes that give you an O(n^2) complexity.-
My Submission
1927D - Найди различные! 3 test cases have passed completely, 4 test case it is giving me wrong answer. Any suggestion how to fix that?
I've recently gained an AC verdict on problem G, and I've decided to share my O($$$n^2$$$) solution. The reason for this is that I found the other explanations (including the editorial) not as deep as I would have liked them to be. So here it goes:
Let $$$dp[i][j]$$$ be the minimum number of charges to use in order to paint all cells up until at least index $$$j$$$, with the restriction that we may only use charges up until index $$$i$$$ (both are inclusive).
As always in DP, let's assume the worst initially, and gradually improve on them later on, so set all values to $$$+\infty$$$. To paint all cells until index 0 ($$$j=0$$$), we don't need to use any charges, so let all $$$dp[i][0]=0$$$.
We will use two loops to fill our DP table: the outer loop will gradually allow the use of more and more charges, while in the inner loop we'll try to paint more and more cells using only the allowed charges, but at the same time, also trying to use the least possible of them.
In each iteration of the outer loop, we're allowing the use of 1 more charge compared to the previous iteration. So the natural thing to do is to try to improve on the previous results. For this, we'll see what we can do with the recently allowed charge at index $$$i$$$. We could either not use this charge at all, use it to the left, or use it to the right.
Not using this charge means $$$dp[i][j]=dp[i-1][j]$$$, using this charge to the left means $$$dp[i][j]=dp[i-1][i-A[i]]+1$$$ and using this charge to the right means $$$dp[i][i+A[i]-1]=dp[i-1][i-1]+1$$$. Don't forget to add the boundaries 0 and N, of course a few of these indices may exceed them! Naturally, it's possible for any of these subproblems that we've already found a more optimal solution, in these cases don't actually set them to these candidate values. Also, the case when we use the charge at index $$$i$$$ to the left isn't valid when $$$j > i$$$. Notice that when we use $$$i$$$ to the right, it has a constant $$$j$$$ value, so we don't need to put that into the inner loop. Also, because of the fact that we've only updated our DP table at edge cases of the possibilities the recently allowed charge offers, it's possible that we have a higher value at a lower $$$j$$$, so let's solve this issue using a loop after the first inner loop that fixes these values. Note that this doesn't increase our O($$$n^2$$$) time complexity.
So why does this work? Because we only use lower $$$i$$$s to compute the optimal solution for higher $$$i$$$s, and these lower $$$i$$$s are guaranteed to already be solved. Why is that? Because we never set a new value for a lower $$$i$$$.
Except I lied to you (I'm sorry), this does NOT work. We can see this solution failing for test case 11 in the example input. There is 1 more case to consider. That is, when we use 2 charges at indices $$$i$$$ and $$$j$$$ such that $$$j<i<j+A[j]$$$ and $$$i-A[i]+1<j$$$. In this case, using charge $$$i$$$ to the left and charge $$$j$$$ to the right may give us the optimal solution, but our algorithm skips these cases. The proof is left as an exercise for the reader. We can solve this by saying $$$dp[i][j+A[j]-1]=dp[j-1][i-A[i]]+2$$$. We aren't setting a lower $$$i$$$ here either, nor are we reading a higher $$$i$$$ solution, since $$$j-1<i$$$ (from the case description). So these requirements are still met.
And with that, we've solved the problem! I hope that this comment was helpful for anyone who wasn't able to come up with a solution for this problem on his/her own. Thanks for reading!
My submission for reference: 245501934
A
Problem-D can easily be solved by using next greater and next smaller element.
Claim : If in [l,r] we don't have all same elements then we could just pick the lth element and find its next strictly greater element or smaller as well . If that thing exists and is within r , then answer exists otherwise NOT .
TC : O(n) for precomputation and O(1) per query.
Hope it helps.
So I want to wonder that why the problem C couldn't accept this code?
k can be as large as 4e5, and ai and bi can be as large as 1e6, so the length of your ta ans tb is too short. You should set N to 1e6+5.
F can be solvable using bridges, find the smallest weight edge (u,v) which is not a bridge ,it will be the answer, and for simplicity the required path will be largest path between u,v (can be found using dfs).
B.following the string problem is getting tle can anyone get it in python
Anyone can tell me how can i optimize this code of D problem. It's showing MLE which is obvious but then how alternatively I can solve it with same approach?
Thanks in advance !!
Can someone please help me find the test case on which my code is failing.
It is failing test case 6 of problem G. code
Take a look at Ticket 17336 from CF Stress for a counter example.
Thanks!
Can anyone explain me the second paragraph of the solution of Problem D?
Can someone please explain to me why solution in java 245738199 is giving TLE whereas same solution in c++ (245745549) works
StringBuffer is OK. 248030776. Maybe problem it is.
Hi all,
I read the tutorial and got accepted on problem F, but I still have one question: What if we just choose the edge with the minimum weight and then find any cycle which contains that edge. Isn't that simpler? Do we still have to use DSU and stuff?
Thanks in advance.
Why my DFS in F TLE in Test19 https://codeforces.com/contest/1927/submission/245777873
Yeah I got the same problem https://codeforces.com/contest/1927/submission/245882846 For me its probably bc I used clone but idk how else you would do it
Thanks for Python solutions besides the great contest!
someone pls explain the solution to G in simple words
difficult to get around for me
Can anyone look into my submission for F? It's MLE in TC 7.
https://codeforces.com/contest/1927/submission/246026044
I am trying for the Problem G seems like I am stuck for this test case 1 1 4 1 3 2
Any Ideas why this gives the output as 2 the correct output is 3 though
alternate solution for F first remove all the bridges from the graph now every edge in graph has atleast one cycle so choose the one which has minimum weight and and get the cycle
I tried using binary search to find l, r for problem D.
Approach -> - storing start and end indices for all intervals for which values of array are equal. - then for each query using upper bound to check if given interval exists inside any interval with all equal values to return -1, -1 otherwise returning the appropriate indices.
Here is the code:-
To me issue seems to be where i am creating start_indices and end_indices vectors. If anyone can help it would be great. Thanks.
problem E different solution with explanation https://codeforces.com/contest/1927/submission/248029334