Hello, Codeforces!

I'm glad to invite you to Round 791 which will start at May/14/2022 12:35 (Moscow time). **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.

**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

Mine is perfect dinner time

ME TOO(I finally don't have to take part in the contest at 22:35).

+1

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.

Guys, be careful. Unusual time

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

Good luck to you too.

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.

yeah I see. Thats why I was super confused at first, but the lack of official post on how ratings works on codeforces. I found a old post that explains div 3 but I could not find anything which provides all the information at one place.

The

unusual timestrikes 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.

Why the time has changed ? Not great time

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 !My First CF Contest! Woohoo!

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. :(

codeSegment tree has a much bigger constant than Fenwick tree

mine passed https://codeforces.com/contest/1679/submission/157170636

maybe you can use

`int`

instead of`long long`

and use

`scanf/printf`

instead of`cin/cout`

My binary index tree TLEed with bare cin/cout while it passed when I unsynchronized iostream with stdio, so maybe it's io's fault

You’ve made the ST too big. Much bigger than required.

Still got TLE. The array size should be 1e5. And st size should be 4e5. Am I right?

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 don't know about TLE but why you are modifying the FT every time?

let's say n number of rooks covering for the ith row! then you don't need to modify FT with -1 unless all the n rooks targeting that ith row are removed! In the same way, you need to modify FT with +1 only when no other rook was targeting that row previously.

And lastly, your type3 query should also be corrected accordingly otherwise WA (as stated by Restricted)

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.com/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

painHacking with a generator is quite simple. Just output the test case you want.

For example, a test generator for BSome 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 just`cout << 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.com/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

rfrom ourRowsset andcfrom ourColsset.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 tried something like that but there was something wrong and it TLEd on somewhere near the 40th case.

I got TLE first and then used fast I/O and it worked

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

Dis 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 detectionandLongest 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 leastkeyword. 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 than`val`

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 than`threshold`

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

Spoilerbitmask dp

?

SpoilerYes, 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

yea :p

Can anyone tell me why do i get TL in B

https://codeforces.com/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.com/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

AI 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

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

CNice problem, I think that it's the perfect difficulty for a div2 C.

DNice 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

Thanks a lot!

hint: keep timestamp of modifing for each item

Notice that if operation of type 2 is never carried out, then the sum would only change by x — arr[i]. Also set arr[i] = x.

If the operation of type 2 is carried out, sum for that round will be n*x. Set a boolean flag for all subsequent operations of type 1 will change.

After even a single operation of type 2, maintain a map that tracks the most recent entry value of the indices. Note that we don't need to track the unmodified indices, as they will be x only (where x represents most recent value of type 2 operation)

Lastly on every occurrence of type 2 operation, make sure that this map is cleared out.

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

The contest was very nice but the pretest cases for problem C were not strong enough and any simple brute-force (TLE) solution will pass it. Let's imagine there is a cheater who created a fake account and joined the contest and then he wrote a simple brute-force solution for it and then he lock his solution and read the solutions of others to submit it from his real account.

Can someone please explain why I am getting TLE in C? https://codeforces.com/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.com/contest/1679/submission/157171908

https://codeforces.com/contest/1679/submission/157173493

Just added comment. LOL Will report more cheaters out there.Sorry for bad english

I really don't know what these cheaters will gain from this sh!t. I think it will be better to ban any cheater forever.

here is an example

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!

Thank you very much

You talked about cheaters, do they exist in cf?

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.com/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

Thanks, I feel so dumb. These start times are killer for NA users.

Can anyone tell what's wrong with my submission? Passed the pretests but failed on Test 10. https://codeforces.com/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!

Can anyone tell me what's wrong with my submission? Passed the pretests but failed Test 22.

My Code...

Just insert one more element = n in your sets.

Thank you

Problem b guarantees 1≤ai≤109 but why 0 appears in test6

where can i get the editorial of this contest??

It will be published soon.

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

yeah, I understand Thank you so much.

ok, got it, Thank you

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 7141Why 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

me :)

it's a pity that you went into the negative, I hope that your rating will grow soon, or rather in the next DIV

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.

I am getting WA on test 2 but I can not find what is mistake. Please someone check it . https://codeforces.com/contest/1679/my

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

I'm screwed!

How to be better ?

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.

Got it thanks, realised the flaw in my approach now

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

You can keep track of how many free rows and cols are there in a certain range using BIT or Segment Tree (search operation logN). To handle the edge case of rook being placed in same row/col multiple times, I used a map to store number of rooks in a row and col. Then I only update the BIT when there are either 0 rooks in a row/col (means the row is free) or 1 rook (any more than this won't make the row unoccupied so only update it once).

Here's my submission

Thank you for problem B, it was tougher than regular div 2 B problems ( according to me ), took me 30mins to think.

THANKS A LOT

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

Nice Idea Thanks a lot. They should put this in the Tutorial Beside the Fenwick tree.

perhaps it can be solved using ordered set.

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:x, check if there is a segment that containsx-1andx+1, respectively. If a segment [l,x-1] exists, remove it and insert [l,x]. If a segment [x+1, r] exists, remove it and insert [x,r]. If both exist, remove both and insert [l,r]. If none of them exist, just insert [x,x]x, search for a segment [l,r] that containsx. Remove this segment, and insert [l,x-1] and [x+1, r], ifl!=xandx!=r, respectively.Every operation can be done in $$$\mathcal{O}(\log{n})$$$ time. Searching for segments around

xcan be done with`set::lower_bound`

or`set::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 includesx1, and see if that segment also includesx2.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

Problem A 157243966 Can anyone check is this solution is correct or not because in verdict it is showing In Queue.

great job never mind but u need better choice win better an do better code is life and a way to win so i will help if need job or help so win

First,it's rating.It's because they would like to practice since there is no div.1 for it

Can someone please explain why my solution from problem C is giving TLE. 157292933

Thanks

put fast io

here you go

Thanks

My video editorial: https://youtu.be/Qa9gabukKqg