Hello, Codeforces!
I'm glad to invite you to Round 791 which will start at 14.05.2022 12:35 (Московское время). Please notice the unusual time.
There will be 6 problems in the round. Round is based on Team Olympiad in Lipetsk which is being held for the seventh time. Problems were proposed and prepared by iakovlev.zakhar, Kon567889, iura, andr1y, Masha237, welleyth and me. I would like to thank Aleks5d and KAN for CF round coordination and testers: Um_nik, 353cerega, errorgorn, Stepavly, divanik, nnv-nick, 4qqqq, to be continued...
Of course, I'd like to thank all Codeforces team for Codeforces and Polygon beautiful platforms!
I also would like to thank golikovnik, egneeS, dshindov and Inessa Shuykova (Lipetsk teams' coach) for preparing other Olympiad problems that haven't been taken for this round.
Thanks to NEAR for supporting this round, details can be found in this post.
Note that if you are an official participant of the Olympiad, you are not allowed to participate in this round.
Scoring distribution will be announced later.
Wish you good luck and high rating!
UPD.1 Scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$.
UPD.2 Congratulations to winners!
Official participants:
Unofficial participants:
UPD.3 Editorial is available here.
Team based round... interesting, will participate.
is there team participation?
I don't think so
Users rated >= 2100 can't seem to register for the round?
fixed
fixed
I like when contests are at this time. (5:35 AM, Saturday for me) It forces me to not sleep in and be a lazy bum
hopeforces
Will the problems be a different style than regular rounds?
Nope
i see olympiad i upvote (unless its russian, then i just comment)
It's a Russian olympiad. You didn't upvote?
CF 791 -> ABC 251 -> Code Jam Round 2
No clashes with 20-25 mins break each. Sweet. Thanks for the unusual time :)
In addition, there is a Leetcode contest at the usual time of codeforces rounds.
Is it only me, or does everyone feel that contest at an unusual time has less participation than the usual time contest? Hence have less probability for the rating to increase. I know we should not give contest for rating, but still...
This round will be hard. Good luck everybody!!!
Hard like the most of unusual time contests but the standing will be much greater then other rounds so rating will also increase more then other contests. Point to think! And Wishing good luck to you all
How to know if a contest is unrated for me, I am new to the cf and could not find any official post on this info yet ?
For gray users all the rounds (expect Div.1, because you can't register for it + some rounds like april fools contest) are rated.
thanks for the info! does that mean div 3 users can participate up to div 2 rounds and also not to div 4 rounds as well?
See, as a grey coders can give div, 2, 3, 4, and all of these are rated for them. I think you are trying to think of these contests in terms of CodeChef contest, those two are pretty different.
The unusual time strikes back.
Why so unusual time? anyone any idea
There is olympiad in this time, round based on it. The unusual time is to avoid cheating
Oh got that
There's also a codejam round on the usual time.
Please add the contest link in the blog.
If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking
First,it's rating.It's because they would like to practice since there is no div.1 for it.
"i_am_completely_useless for being completely useless." -- Sakura :))xD
Nice quote...
Thanks!
Nice bro!
Thanks!
Thank you for the unusual time!
excited for this contest, go go go !
Unfortunately, I need classes at that time, so I can't participate in this contest.
QueryForces
Pretests in C must be extremely weak
edge cases ?
first q/2 queries of type 1 having x = i , y = i for i 1 to q/2
Then next q/2 queries of type 3 having x1 = 1 , y1 = 1 , x2 = n , y2 = n .
If somebody checked type 3 queries linearly from x1 to x2 , or y1 to y2 then Complexity will be O(Q*N) and there are many such accepted solutions
waiting for contest finish to get solution for problem E
saw your dp solution of c question , edu round :) love u bro
Thanks:)
You can find contribution of each subarray.
Let us focus on some subarray $$$s$$$. There exists a mask $$$m$$$ for $$$s$$$ such that $$$s$$$ will contribute to the answer iif mask of query is supermask of $$$m$$$.
$$$m$$$ gets fixed because we have the restriction that if $$$s[l] != ?$$$ and $$$s[r]=?$$$, $$$s[r]=s[l]$$$ ($$$r=|s|-l+1$$$).
Now for subarray $$$s$$$ to contribute $$$1$$$ to the answer, some $$$?$$$ get fixed and rest $$$?$$$ are flexible. Suppose we have $$$freq$$$ flexible $$$?$$$. Finally $$$s$$$ will be contribute $$$1$$$ to answer in $$$|t|^{freq}$$$ arrays.
There are $$$2^{17}$$$ masks, and len $$$|t|$$$ is up to 17, and also we need to sum up all summasks foreach mask.
All my tries did run like more than a minute...how to do that right?
Say mask of query is $$$q$$$.
Now you need to check contribution of all masks $$$m$$$ such that $$$q&m=m$$$. You can traverse over all submasks in $$$O(3^x)$$$ operations(here $$$x=17$$$).
Suppose we have a $$$dp$$$ array, such that mask $$$x$$$ will contribute $$$dp[x][i]$$$ to the answer, if $$$q&x=x$$$ and $$$__builtin_popcount(q)=i$$$. So you calculate this $$$dp$$$ while traversing all subarrays(fixing middle position and moving sideways).
You can precompute answer for all masks.
My submission
oh thanks! I forgot about this trick to iterate over submasks
actually you can solve it in $$$O(2^{17}\times 17^2)$$$ by using SOS dp or fast walsh transform.The solution is similar to yours.
My submission
Why Segment tree solution is giving TLE in C. :(
Segment tree has a much bigger constant than Fenwick tree
mine passed https://codeforces.net/contest/1679/submission/157170636
maybe you can use
int
instead oflong long
and use
scanf/printf
instead ofcin/cout
You’ve made the ST too big. Much bigger than required.
you don't have
you shouldn't use 'build' initially all values are 0
Why do you use long longs?
Used a single loop in Problem-B, still exceeded the time limit, is it me or python at fault here?
sum()
uses loop internallyThanks to iura for setting F! I really enjoyed solving it during testing. Here is my alternate solution to F that works for much larger constraints.
Let $$$S_i$$$ be sets containing all representatives of all arrays $$$a$$$ of size $$$i$$$ and $$$C_i$$$ be the set of cliques of size $$$i$$$. When we talk about clique, we are talking about cliques on the graph where we draw the edges as $$$(u_i,v_i)$$$. Also when we talk about arrays, we will basically refer to its equivalence class, so treat $$$a$$$ as the representative.
Take some array $$$a$$$ and let $$$s_a$$$ be the possible values of the first element of $$$a$$$ after some operations. Note that it is necessary that $$$s_a$$$ is a clique because otherwise, we are not able to swap all values in $$$s_a$$$ to the start of $$$a$$$.
Let us suppose that we know $$$S_j$$$ for all $$$j<i$$$ and now we want to find $$$S_i$$$. For all arrays $$$a \in S_{i-x}$$$ and $$$c \in C_{x}$$$,put $$$(c,a)$$$ into $$$T_{x}$$$. That is, we want to think about arrays $$$a \in S_i$$$ as the concatenation of some clique and another array. Unimportant remark: $$$c \subseteq s_{c+a}$$$.
However, the problem with this is that are multiple ways to make a certain array. As a simplest example, consider when we can swap $$$(1,2)$$$ only. To make array $$$[1,2,3]$$$, we can split it into $$$([1,2],[3])$$$, $$$([1],[2,3])$$$ and $$$([2],[1,3])$$$. Of course, we do not want to double count.
Let us consider some $$$a' \in S_i$$$ where $$$k=|s_a|$$$. There are $$$2^k-1$$$ combinations of $$$c+a$$$ that produces $$$a'$$$. Every subset $$$c$$$ of $$$s_a$$$ corresponds to a $$$(c,a)$$$ tuple, and there are obviously $$$\binom{k}{x}$$$ such subsets with $$$|c|=x$$$, so $$$\binom{k}{x}$$$ tuples in $$$T_x$$$ corresponds to array $$$a'$$$.
One can see that $$$|S_i|=|T_1|-|T_2|+|T_3|-\ldots$$$ by looking at the individual term of some $$$a' \in S$$$ and noticing when only considering tuples that correspond to $$$a'$$$, we have $$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \ldots =1$$$ on the right hand side. Note that by definition, $$$|T_x|=|S_{i-x}| \cdot |C_x|$$$.
Let the number of digits be $$$d$$$. If we let $$$ans_i$$$ be the answer for length $$$i$$$, we have the explicit recurrence $$$ans_i=\begin{cases} 0,& \text{if } i < 0 \\ 1, & \text{if } i=0 \\ \sum\limits_{j=1}^d ans_{i-j} (-1)^{j-1}|C_ j| & \text{if } i>0\end{cases}$$$.
We can find all $$$|C_j|$$$ in $$$O(2^d)$$$ by brute force. To do this, we check if some mask $$$bm$$$ is a clique in $$$O(1)$$$ by taking an arbitrary bit $$$b$$$ from $$$bm$$$, checking if $$$bm \oplus b$$$ is a clique and that $$$b$$$ is connected to everything in $$$bm \oplus b$$$. Since we can solve linear recurrence in $$$O(d \log d \log n)$$$, we have total complexity of $$$O(2^d+d \log d \log n)$$$ but it probably does not matter what algorithm we use to solve the linear recurrence since there is no way it is going to dwarf the $$$2^d$$$ term.
Can we find all terms of $$$|C_j|$$$ faster than $$$O(2^d)$$$?
Code: 157227780
segment tree forces
Which tasks required segment trees? I only looked at A, B, C and D and none of them required it (or anything similar like Fenwick)
B and C were doable using segment trees
My solution to C tle'd using Fenwick tree any suggestions ?
++ I used segment tree my solution got tle'd too. I don't know where did I go wrong . :(
You should use int instead of long long whenever you can. Also it'll be good to use the fast I/O:
Finally if it doesn't work, use a fenwick tree as it's constant factor is way better than a segment tree's
You can refer my submission: 157174605
Hey winterfire can you check my submission and let me know what you think ? submission
This solution would get WA even if it didn't TLE. Despite that, you need to use fast I/O. Try adding this:
ios_base::sync_with_stdio(false); cin.tie(0);
Oh lord thanks Restricted I am using this template from a long time never noticed fast i/o wasn't included that's why I was wondering my submission for B took 1.5 sec but is just simple operations..
Happens to the best of us :)
I did it using segment trees. Create two seg trees for handling rows and cols. If a rook is placed/removed at cell x, y then update the xth row and yth col. For query of type 3, if the bitwise AND of rows x1 to x2 > 0 or cols y1 to y2 > 0 then answer exists.
Mine passed in 290ms 157157585
I'll try to see why your sol TLE'd
your solution is wrong
Consider a case with a 5x5 grid
If I query on the whole grid, the answer should be No but your code will output Yes because you shouldn't add 1 everytime you place a rook. See my explanations here for more details:
Thanks bestial I got it its wrong , I think TLE is because of fast i/o but if you see any other issue with BIT implementation let me know
It seems ok but for more safety I would add ++index b efore computing any answer for queries (this is because the bit trick you use doesn't work for 0). Adding the ++index would allow you to use the BIT like it's 0-indexed if you want. You only need to make sure that you allocate extra memory but you already did that :)
yes ofc you can use segment trees as arrays
however actually B can be solved in $$$O(n+q)$$$ without using segment tree
Maybe B and C.
n = 2 should have been in the samples in A :(
Btw, I wonder how many people solved B using segment tree
I use segment tree with lazy propagation.
You can do it in an easier way.
You want to perform three types of queries
set all the elements to x
change the value of an element
compute the sum of the array
If you don't have the "set all the elements to x" queries, you can just compute the sum at the beginning and when you change the value of an element you know how the sum will change.
The only problem is that if you performed a "set all the elements" query, the value of the element might not be the one you stored in the array.
To handle this, notice that the latest query will give the value of the element.
So you just keep track of the time when the set query was applied and when the change query of each element was applied.
Code: 157146130
There is an easier way. Just store all changed indices since query 2 and clear them after query 2. https://codeforces.net/contest/1679/submission/157150450
If there are a lot of queries of type 2, wont this get TLEd as you would be clearing the set each time?
but then you are going to clear a set of small size.
Ohhh I see
At most for any query 1 you will perform it twice, once while adding it and once while clearing it. So this is still O(q)
157185820 I have almost done the same, but i guess missed some edge cases. Could you point out what is wrong, please?
use long long.
Thank you for clarify!
Overkill. Could be easily solved in O(n + q) via storing the last occurrence of updating the whole array and the last occurrence of updating an index for each index.
I tried to hack C with 2e5 queries and it said input cannot exceed 256kB, what T_T
You can use a data generator.
Will learn how to use that before the next contest, till then pain
Hacking with a generator is quite simple. Just output the test case you want.
Some things to note are: Don't output any extra spaces or blank lines (e.g. after arrays), and the test case should always end with an endl character (e.g.
cout << n << '\n';
instead of justcout << n;
). Basically you should follow test standard practices strictly.it was helpful,thanks a lot ;)
how to solve c ? some one pls tell me your approach :* (i've tried to do it with brute force by making maps in the last 10 min I was knowing that it gonna get me tle :D ) so how can we solve it:*
If you have at least one rock in a row set the row's value to 1. If you you have at least one rock in a column set the column's value to one. Now you wanna know if the sum of the columns in [x1,x2] is exatly x2-x1+1 or if the sum of the rows in [y1,y2] is exactly y2-y1+1. This can be easily done with a segment tree
hey bro just need a favor from you basically you are a specialist you might be having a good idea about cp so can you tell me after seeing my profile and rating that should I learn segment tree or not cause some of my seniors were saying to me that to learn segment tree your rating should be at least 1500 or something but from last few contest I'm seeing that there is one question of segment tree between a,b,c and you might remember that div4 contest which just held few days ago in it also h2 problem was solved using segment tree so can u suggest me,that when should I learn about it or i should wait for few months :*
I don't see why not. It's not that hard of a concept and it makes you understand some other CP concepts better. At least know what it does and how to use it.
You should learn to use ordered set. Today's C and div4's H2 could be easily done with ordered set.
but in java there is nothing as ordered set:* can u suggest any alternative:D
I don't think there is any alternative in java. You have to use fenwick or segment trees.
Think of a way to maintain the empty rows/cols, after that when they ask you to check the subrectangle try to find if there is a row and a col that is empty and satisfy this condition: x1 <= row <= x2 && y1 <= col <= y2, if you found such a row and a column then the answer is no otherwise the answer is yes
I solved it using sets and binary search
but how who can we find it with bs:* can u elaborate
Here's my solution https://codeforces.net/contest/1679/submission/157198959
The idea is to keep track of the empty rows and empty cols, initially everything is empty so we will insert into our rows and cols the numbers from 1 to n;
Rows = [1,2,3,...n] Cols = [1,2,3,...n]
Now anytime we insert a rock to some (r,c) that means the row is no longer empty and the col is no longer empty, so we will remove r from our Rows set and c from our Cols set.
Now, how can we know that this row/col is empty? we can keep track of the rocks count in each row and col, once the count for a row/col becomes 0, this means we need to insert it into the corresponding set.
Take a look at my solution, and hopefully, you will understand what I mean.
I used Ordered Set to solve C.
When a rook is inserted on (r, c) notice that it covers all cells on row r and col c
Let's store for each row if it's already covered by a rook Do the same for columns
Now the subrectangle queries ask if for each cell, either their row or their col is covered
A subrectangle query consider a range of rows and cols
What happens if a column is not covered ? Basically you need all the rows to be covered for the cells of this column to be covered
(same argument in reverse)
This way we show that the answer is "Yes" iff all the rows or all the cols are covered
Let's say we put a 1 when a row is covered
We just need to range sum over the range of rows and make sure the sum is equal to the length of the range
Same for cols
To handle rooks removal, we count for each row the number of rooks covering it
When this count reaches 1, we add one in our segtree/bit
When it reaches 0, we add -1
Code: 157157585
How to solve D? My idea is to go through the nodes in increasing order and activate them one by one. Once I activate them I want to know if a strongly connected compononeted is activated, this means that I am done regardless of what K is. This is easy to do. The hard part was knowing whether a path that is K long in is created. How do you do it?
The idea for D is fairly simple (and a good learning exercise if you aren't familiar with the "trick"). You just need to combine 3 independent pieces: Binary Search on answer, Cycle detection and Longest path in DAG.
Since we are asked to minimize the maximum value of some quantity, it's natural to think in terms of binary search. However, this can be a trap if the function is not monotonic. To work around it, a clever way to define the predicate is to use the at least keyword. Instead of asking whether an answer with value
val
exists, we askWith this keyword, it's fairly obvious that existence of at least
val
implies the existence of at least all value less thanval
as well.To verify a predicate, you can ignore all vertices with value
> val
while performing a DFS. (You might've seen this in problems asking you to find the maximum value less thanthreshold
on a path between 2 vertices in a tree). After ignoring these vertices, if the resulting graph contains a cycle, it means you can travel it infinitely many times. If not, it is a DAG. Then, you just need to find the longest path on this DAG and verify if it's at least $$$k - 1$$$.Note that you can do all of this in a single DFS (and without explicitly creating the new graph).
Code
Of course you do binary search how did I miss it. Eeh, I feel so dumb haha. Thanks a lot!
You don't need to feel dumb, it happens not to be able to solve a problem!
What you should learn from this is that problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)
You can find some similar problems on usaco guide:
Wormhole Sort
MooTube
That's so nice of you to say thank you! I will definitely be checking the problems you suggested later.
Nice explanation. You made it look so simple. Thanks.
damn I only knew binary search
Amazing idea!!!
thanks a lot
Binary search for the answer. And for each check, we could search for cycle or a longest chain in the new DAG, which we needn't really create a new graph but just judge the number on each vertex
What exactly D asks for?
Given a directed graph, find paths such that there are K vertices in it. Choose a path such that the maximum value of the vertex is the minimum possible. Output this value.
We can use binary search to find the answer.
When we are checking if there exists a path of length k with nodes whose values are less than or equal to 'x'(current binary search value), we consider the subgraph 'C' formed by the nodes whose values are less than or equal to 'x'. Now we have two cases. 1. There is a cycle in this subgraph C, the answer is true for this x in this case. 2. There is no cycle => subgraph is a DAG. Find max path length using DP and check if the max path length is >= k. The answer is true for this x if that is the case.
Steps 1, 2 are of O(n) complexity each. We do them for a total of O(log(max(a[i]))). Therefore total complexity is O(n*log(max(a[i]))). code.
Unfortunately Got TLE on pretest 10 using the same approach
What was the approach for problem A ?
The max number of cars is calcualted using the maximum number of 4 wheel cars. The min number of cars is calculated using the maximum number of 6 wheel cars. We need to consider some edgecases, like odd numbers.
E was nice construction problem, I like it.
But whole contest was spoiled by unclear problem statements, except A there was not a single one I clearly understood. Had to decipher and guess the meaning of all texts, annoying.
isn't E
bitmask dp
?
Yes, it's SOS DP
me about to solve A in 6 mins.
1st error (Not considering the edge case of n == 2) be like: "I will make you pay"
2nd error (forgetting to return after printing -1) be like: "LMAO NOOB"
And that's how 'A' ruined my LIFE :)
me too :( let's be more patient
Can anyone tell me why do i get TL in B
https://codeforces.net/contest/1679/submission/157177370 ?
I guess
tot = b[1] * n
is $$$O(n)$$$It is just a multiplication of two integers.
Sorry for the previous nonsense reply, I just read too fast and thought you were creating a list. I got your code accepted by reading the whole input at the start.
Great. Is it fine though, that such optimizations are needed for code to be accepted. Or it is a problem of a contest?
I agree this should not be needed. But I had a look at some of the accepted Python solutions and it seems they write at the start
input = sys.stdin.readline
which I guess is way faster. Using that your code also gets accepted, so you should write that and keep reading input as you did, which is not a big deal.Yeah this is frustrating. It's only a single linear loop. https://codeforces.net/contest/1679/submission/157146581
I also tried the standard Python 3, it just barely passes the pretest but of course it is TLE again on the system test
thanks for the early end round,that i could see RNG's exciting game:(
This was a super cool round with nice algorithmic problems ! Congrats to the authors :D
Here is my advice about each problem
I think it's ok as a div2 A, I don't have much advice about wether a div2 A should require a little bit of maths or not
This is a really cute problem if you try to solve it in linear. Sadly it can be bashed with a lazy segtree which makes the problem solvable by template copy paste. I don't know if it's possible to make a lazy segtree TLE without hurting the linear solutions AC rate...
Nice problem, I think that it's the perfect difficulty for a div2 C.
Nice problem too. It might be a little bit standard though but as long as it's not copy paste I think it's fine.
I didn't solve E/F so I don't really have an advice but they both look interesting
how to solve d?
Problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)
So let's binary search over the maximum node you will walk on (I don't explain why you can binary search here but you can try to prove it as an exercise)
Now we need to check if it's possible to find a path of length k (in terms of nodes) using only nodes with value <= MX
Let's build a new graph. It'll be the same graph as the original one but only with nodes having value <= MX. We now want to find a path of length at least k. Notice that if the graph has a cycle, we can just keep moving in the cycle and get a path of length at least k. If the graph doesn't have any cycle, it's a directed acyclic graph and you can use dp to compute the longest path in it.
Code: 157170838
Since I am poor in English, can anyone explain what is the difference between loops and cycles? Why "loop" is equal to "self-loop" instead of "cycle" in D?
I didn't solve it but I tried solving it by considering a "loop" to be equivalent to a "cycle". Is it not the case?
loop is an edge which starts in vertex v and leads to vertex v too, in other words, loop is a cycle which contains single vertex
In the author's opinion, probably, "loop" is equivalent to "self-loop", or you can't even pass sample tests.
The common wording at least on codeforces is that a loop is a self-loop, a edge that starts and end at same vertex, so a cycle of length 1.
And a cycle is a circular path containing more than one vertex.
Thanks.
(https://en.wikipedia.org/wiki/Loop_(graph_theory))
(https://en.wikipedia.org/wiki/Cycle_(graph_theory))
just check out these links, it's not codeforces-related terms but common ones
Can anyone please explain a solution for Problem B? (without using segment trees)
Yes! You can read about it right here
hint: keep timestamp of modifing for each item
Someone really wrote seg tree there?)
Me who can't be bothered to think of a linear solution... I'm a simple man, I find any passable solution, I type it up
Store the initial sum in s.No need to store the array.Maintain a map instead of all the type1 changes made to the array after the recent type2 operation.Maintain a variable l initialized to 0, to store the x value of the last type2 operation.So everytime you get a "1 i x" just look into the map if some change was registered at pos i by "m.count(i)", if it's not zero then update s as s+=x-m[i], else if no change was registered the cell contains the last type2 change hence s+=x-l.Now when you encounter type2 operation clear the map and update the variable l to the new x and the sum s to n*l. Link to my not so legible code
Can someone please explain why I am getting TLE in C? https://codeforces.net/contest/1679/submission/157197783 I am using hashing to figure out when to add/delete row/column in sortedset(made using Fenwick Tree). And to find out if the whole sub-rectangle is there, I just subtract indexes with lower_bounds of x1,x2 in row sortedset and y1,y2 in column sortedset and compare it with difference of x1,x2 and y1,y2. It should be O(nlogn) but sadly it's giving TLE:(
Testcase 41 is on fire
it got me too :(
Mine just pass..
so many fst on problem C and D..
Several stupid mistakes on A and D led to the terrible penality and the rapid descent of rank.
MikeMirzayanov https://codeforces.net/contest/1679/submission/157171908
https://codeforces.net/contest/1679/submission/157173493
Just added comment. LOL Will report more cheaters out there.Sorry for bad english
Sad to get FST on E :(
(my solution isn't the best solution so it got TLE on test 10.)
.
Problem E
Can any one explain why in input
2 ?? 1 ab
10 palindrome substring
(a, b, aa, bb, a, b which other?)
To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
Can anyone tell me what's wrong with my code for Problem C. I was expecting a TLE but got a WA on the 27284th token!
It's in Go, but easy to understand. Uses 2 bool arrays for x and y and just loops over x1->x2 && y1->y2.
https://codeforces.net/contest/1679/submission/157188079
If I add two rooks on same row and then remove one of them, in that case your code is considering that there is no rook on that row. Because of this
You should store frequency of rooks on particular row and col to resolve this
Can anyone tell what's wrong with my submission? Passed the pretests but failed on Test 10. https://codeforces.net/contest/1679/submission/157152675
This test case will fail in your code:
Silly mistake! Got it Thanks.
write x<n instead of x<=n in the Fenwick tree and got fst on C. What a pity!
Problem b guarantees 1≤ai≤109 but why 0 appears in test6
Can anyone tell me why I got runtime error? my submissions
your code get an out of bound error when i == n (a[n] will out of bound).
you should let your vector resize to n + 1.
but I declare the structure Fenwick x(n + 1), y(n + 1) way.
In your Fenwick n = n + 1 at the same time.
In this for loop, the n is 1 larger than the n your input. So a[n] will out of bound even if you declare the structure Fenwick x(n + 1000), y(n + 1000).
i also got runtime, when i initialize with n+1 i get RE when initialize with n+2 it passes and when i initialize with n+3 it again gives RE. i couldnt understand why edit: it gets accepted in c++20
Can anyone please find a test case where this code (157177615) fails. I have tried to come up with a failing test case but have had no success.
Failing testcase: Ticket 7141
Why the system is testing again ?
What happened, why is task B being retested?
Thx the contest.Become Master at last!
who else had a rounding error in problem A haha
Thanks for the Problems . It was a pretty balanced round
我小号第一次进前一千!!!
Can someone see my solution for C I find nothing time consuming here. Can any minor changes make it acceptable.
Aren't you iterating over rows and columns for each query though?
I mean you have those two loops in your code:
Thank you! Can you also please suggest other efficient ways to do it with same logic(like checking if all any one of columns or rows are filled) if possible. Or is there any other logic for this
fenwick tree or segment tree to check sum or minimum in the range.
I've done this problem the same way as you (logic wise). You can look at my submission.
However, I used C++'s set and its 'lower_bound' function. I guess you can find something similar in python :)
Maybe there is even some simpler way to solve it but I can't think of anything.
can someone tell me how to solve D plz
Binary search the answer, then you need to judge if there is a cycle or a path with a length of at least k containing vertices with number <= answer. You can do toposort or dfs. My submission
Imao the limit on C has been too tight. Whether solution is accepted or not is up to constants and the judging machine. These two submits differ only in a tab (begining of main), however only one gets ACC: 157217055 157214568
(Played with it after the round so there might be some diffrence but the point remains anyway.)
you are returning a string level by level in segment tree, which could be much slower. Change it to an enum and it will finish in ~300ms.
Thx a lot.
Can someone please help me figure out what went wrong with my solution on problem C?
What i was doing is: - store how many free rows/cols we have upto a certain row lets say r and c (using 2 BITs)
You need to consider the case where two rokes are in one row. After removing one of them the other one is still on that row.
How to check if all rows and column in that submatrix is attacking by rook in log(n) time,beacuse it will take o(n) time
public class C {
// Can anyone help me figure out the test case, where this solution would fail?
Put it in spoiler and don't spam?
Can someone tell me why my solution of Problem C is giving WA on Test Case 3?
And even if it passed test case 3 it will get TLE for sure! Your solution is O(n^2) and the constraint is 2*10^5 Make sure to learn the Fenwick tree first to solve this problem
It can be solved with c++ set
Please explain this solution in c++ set.
For rows:
store in set every value that is not covered by any rook.
initially this set is obv full.
to know whether there exists a row between x1 and x2 that is not covered you make use of set.lower_bound()
if lower_bound(x1) is set.end() or its value is > x2 then all cells between x1 and x2 must be covered
same for columns
For some reason I couldn't come up with using segment tree for C, instead I used a complicated data structure that contains every consecutive segments. I believe it is useful for some specific problems, but it was an overkill for this problem. It is implemented with a
set<pair<int, int>>
where each pair represents the endpoints of each segment. Each operation is implemented in these ways:Every operation can be done in $$$\mathcal{O}(\log{n})$$$ time. Searching for segments around x can be done with
set::lower_bound
orset::upper_bound
and decrementing the iterator if needed.AC code: 157170732
Forgot to mention the part that checks the answer. For a query [x1, x2], we just need to find a segment that includes x1, and see if that segment also includes x2.
Looks like a weakened version of Chtholly Tree (or to use a more accurate description, maintenance of connected color segments).
Can someone suggest similar problem like D
see this
Can someone please explain why my solution from problem C is giving TLE. 157292933
Thanks
put fast io
here you go
My video editorial: https://youtu.be/Qa9gabukKqg
With 1 minute and 30 seconds left in the competition, tourist got to the first place by a hack. Cool!
Should not ratings be updated again for this contest? At contests page I got 894 place but at official standings 883 place.
Check out your own