Author: iakovlev.zakhar

Preparation: DishonoredRighteous

Editorial: DishonoredRighteous

**Editorial**

Author: Kon567889

Preparation: Kon567889

Editorial: DishonoredRighteous and Kon567889

**Editorial**

Author: Kon567889

Preparation: Kon567889

Editorial: DishonoredRighteous and Kon567889

**Editorial**

1679D - Toss a Coin to Your Graph...

Author: Kon567889

Preparation: Masha237

Editorial: DishonoredRighteous

**Editorial**

Preparation: andr1y and welleyth

Editorial: andr1y and welleyth

**Editorial**

1679F - Formalism for Formalism

Author: iura

Preparation: iura

Editorial: DishonoredRighteous

**Editorial**

I hope you enjoyed this round!

Can anyone please tell, whats wrong with this solution ? https://codeforces.com/contest/1679/submission/157267162 WA on test 5

Thanks

Failing testcase: Ticket 7177I believe that E would be much easier to understand with a formal definition.

Let $$$k$$$ be the number of '?' in $$$s$$$. For a given string $$$t$$$ with unique characters, let $$$sub_t(s)$$$ be the set of all $$$|t|^k$$$ ways to substitute a character from $$$t$$$ in each '?' in $$$s$$$. Let $$$f(s)$$$ be the number of pairs $$$1 \le i \le j \le n$$$ such that the string $$$s[i : j]$$$ is a palindrome, where $$$s[i : j]$$$ is the substring of $$$s$$$ from $$$s[i]$$$ to $$$s[j]$$$. Given $$$q$$$ queries of string $$$t_i$$$, compute and print

for each query.

It removes a lot of ambiguity from the statement, and is easier to understand.

** function of existence of the answer relatively to the minimum value of the maximum in the path is monotonous.**

can anyone please provide me an example of this

E good problem,but didn't solve.qwq

It seems that segment tree solution is acceptable for C but much slower. I don't know if it is because segment tree itself is so slow? Or is segment tree theoretically acceptable for this problem?(the time limit of 1000ms is a bit short for segment tree solution)

My submissions: TLE 157157377 157159053 AC 157166835

Pretty sure it's just cin/cout throwing a hissy fit. My submission used scanf/printf and passed without any compiler optimizations at 343ms. 157161379

yeah I noticed that I ACed after ios::sync_with_stdio(false)

This happened the same to me. Are there any reasons behind using it? I never ever used ios::sync_with_stdio(false), what does it do anyway?

I used this stack overflow link but it wasn't clear much

In a nutshell: Sets whether the standard C++ streams are synchronized to the standard C streams after each input/output operation.

It is often recommended to use scanf/printf instead of cin/cout for fast input and output. However, you can still use cin/cout and achieve the same speed as scanf/printf by including the following in your main() function: ios_base::sync_with_stdio(false);

Thanks it was informative

Always use scanf and put, i solved with Fenwick tree and without scanf i got TLE

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

Might be your segtree since mine runs under 300 ms.

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

I will improve my segment tree. thx!

Thank you for sharing your implementation :D, I could improve my segment tree. JIC is here: https://codeforces.com/contest/1679/submission/157264397

Actually it's pashka's segment tree from his segment tree EDU tutorial

😄

I like this round very much. Thanks for all of the people who organized this round.

In first question i am unable to understand that how in case of minimization of buses the answer is n/6...please explain

Since n cannot be odd, n should be even. Also n cannot be equal to 2. So n should be from the set {4,6,8,10.....}. Which means when divided by 6 the remainder will be either 0 or 2 or 4. Let x = n/6 and r be the remainder. If r is 0, you have all busses with 6 wheels, answer is x. If r = 4 you have x busses with 6 wheels and left with 4 wheels. So you can add a bus with 4 wheels, final answer becomes x+1. If r = 2, you have x busses with 6 wheels and note that x >= 1. You can remove a bus with 6 wheels and add 2 busses of 4 wheels. Answer again become x-1+(2) = x+1. So simply put it will be the ceil of n/6.

N is the number of wheels, when we want to minimize the number of buses we will want the max buses to be with 6 wheels as that will reduce the number of buses. Now n is even, there can be 3 cases: 1- when n % 6 == 0: then the answer will be n/6. 2- when n%6 == 2: then if we have n/6 buses with 6 wheels, two wheels will be left, so we will get n/6 — 1 buses with 6 wheels, and 2 buses with 4 wheels(as now we have 2 + 6 wheels left) that makes n/6 + 1 i.e. ceil of n/6. 3- when n%6 == 4: then we will have n/6 buses with 6 wheels and 1 bus with 4 wheels, total n/6 + 1 i.e. ceil of n/6.

Jai BajrangBali.

thankyou @vineetwidhani01 i got it now Jai Bajrang bali

Can I ask that in Div2C, how we can use binary search to check whether that sub rectangle will be attacked by the rock?

Imagine you have a sorted set of rows and columns that do not have any rooks on them.

Let's say, given n = 10, the the set for the rows is : 1 2 3 4 10

the the set for columns is : 2 3 6

You've got a query : 3 5 4 9 7

To answer the query what you have to do is to find the first element in the set of rows that is equal or greater than 5 and find the first element in the set of columns that is equal or greater than 4.

You can use binary search to find them in log(n) time.

lower_bound(5) = 10 lower_bound(4) = 6

So, that means you must have rooks on rows from 5 to 9, and on columns from 4 to 5. As we have every row from query covered by at least one rook, the answer is "Yes".

ok I understand, thank you too much

In problem C, why this submission is WA and the other one is AC if they are pretty similar, I literally copy my previous segment tree methods into a struct with a few improvements. I couldn't find the bug :'(

WA: https://codeforces.com/contest/1679/submission/157262319

AC: https://codeforces.com/contest/1679/submission/157264397

Read my comment posted below https://codeforces.com/blog/entry/102859?#comment-912796

can someone tell me why my C got FST

Problem C:can someone tell me on which test case my code fails it give me WA on test 3 [27284th token]

Click here157271735You can have more than one rook in a row/column. Since you are using your boolean array as an indicator of whether there is a rook in a particular row/column or not, you need to set/unset only when there is a new rook in that row/column or the current rook removed was the only rook of that row/column

ohh Man That's great Count also matter Number of rook on the same row or columns could be more than one i want to make boolean value false when count of rook is zero on particular row and column Thanks for the clarification

Problem C :Hi, can any one tell me what I'm doing wrong, I'm trying to solve the problem using BIT where the first pointer is 0 if no rock in line|column and 1 meaning at least a rock in the line|column, and the second one is the number of counts of rocks in that line|column , plz help me I toke more then 4 hours not finding the mistake.

i think it's clear since you have to add 1 if the counter is 1 (was 0), or add -1 if the counter is 0 (was 1).

I got it, Thanks my friend for helping me ^_^.

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossiblecounter examplefor your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your

submissionandticket(s).Can someone please tell me what is wrong with my code for the problem C. https://codeforces.com/contest/1679/submission/157259885

You have not considered the case for multiple rooks in row/column

Can someone please explain why my submission for C is giving TLE. 157292933

Thanks

use fast input output I got AC with your code, Time Limit is too tight

Do you have information about where I can find the solution of fast IO for c++?

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Add these 2 lines in your main Function, you can read more about it Stack Overflow

TASK C TL, test 3

Thank you. May I ask you to look quickly for submission, please? https://codeforces.com/contest/1679/submission/157302795

Oh, god. I remember that lower_bound should be called like a method of the set.

Thanks

RMQ using segment treestruct SegTree {

};

I don't know what to arr.assign()(is it also 0?) for range max queries. I hope the rest of the changes are correct for range max queries. Can anyone help me with it please?

Why this submission gets time limit. Can any one explain? I just run loop of O(n+q). Problem: B My submission link 157195608

This is O(n + n*q) as you are making a new vector in each query!!

Okay, thanks for making me understand.

Which test case I am missing in problem B? 157192323. I am getting WA on test 2 with message: wrong answer 58999th numbers differ — expected: '32583263977149', found: '32583727669172'.

Failing testcase: Ticket 7208Can somebody show me the problem C solved like is told in editorial please? I tried different methods except tree metods , and have time limit at 41 test case.

I liked problem B.I mean I could not solve it on my own, but the editorial solution was pretty smart (for me at least)

My logic to A solution started from:

initial equation: $$$4 \cdot x + 6 \cdot y = n$$$

a note: $$$4 \cdot 3 = 6 \cdot 2$$$, so we can replace an equation with $$$4 \cdot x + 4 \cdot 3 \cdot y = n$$$ (if $$$y$$$ is even) or $$$4 \cdot x + 4 \cdot 3 \cdot y + 6 = n$$$ (if $$$y$$$ is odd).

We can check if $$$y$$$ is even, what possible when $$$n$$$ mod 4 = 0, and if $$$y$$$ is odd, what is possible when $$$(n - 6)$$$ mod 4 = 0. Otherwise (and in case with $$$n = 2$$$) there is no answer.

Someone please help with problem A, I just can't understand it no matter how many times I've read the editorial

the author said for

Problem D:`it's a well-known classical problem.`

Can anyone suggest some similar problems or the classical one that the author is talking about?Here are some problems which are quite similar to problem D from this round:

EDU 128 C

EDU 126 C

In problem-4 it is mentioned that, It's guaranteed that graph doesn't contain loops and multi-edges. I want to know what is meant by loop? Is it different from cycle?

loop is an edge that connects a vertex to itself

oh ok now i understand. Thanks!

how does this code works for B

## include <bits/stdc++.h>

## define ll long long

using namespace std;

int main() {

## ifndef ONLINE_JUDGE

## endif

} The time complexity is o(n+n*q) n and q is 2*10^5 so how is it able to work .The clear function takes o(n) time and if we just replace clear function with a for loop with makes the element of the array equal to x it shows TLE . Pls somebody who knows or implemented the same kind solution help me to understand ?? sorry for my pathetic english xd

Yes, clearing the map takes $$$O(N)$$$, but it isn't $$$O(N+NQ)$$$, because sum of all sizes of map can be at most Q (at most 1 element can be added to map during each iteration). That is why this solution works in $$$O(N+QlogQ)$$$.

how is log(q) coming I can't get it. suppose after initialising the array the first query is of type 2 then u have to remove the array by mp.clear() similarly if all query is of type 2 then would"nt it take n*q ??

$$$QlogQ$$$ appears from calling map, because every call of map is made in $$$O(logSZ)$$$, where $$$SZ$$$ is size of the map.

Let's suppose, you have 2 elements in array, then you cleared it, added another 4 elements, and cleared it again. The first clearing method was done in 2 operations, and second was done in 4 operations. So, if we write down sizes of map before each clearing, let it be $$$sz_1, sz_2, ... , sz_k$$$. It easy to see that $$$\sum_{i=1}^ksz_i \le Q$$$. So all clearing operations take at most $$$O(Q)$$$.

PS: I actually don't know, is clearing is done in $$$O(SZ)$$$ or in $$$O(SZlogSZ)$$$ :thinking: :/

Video Solution for Problem D.

Can anyone post the editorial for C in easy words?

If there is a query box with width W and height H, then to cover each cell there must be at least one rook in each row in the box, or at least one rook in each column in the box. So, if there is a row and a column in the box which don't have a rook in them, then there is a cell that is not covered. Otherwise, all cells are covered.

We can do two(one for columns, one for rows) Segment Trees with checking, if there is a zero in the segment. If we add rook, we add +1 to the column and row in the trees. If we remove rook, than we add -1.

If you don't know segment tree, you can also solve it by just using set ( one for column and one for row ) , let the set store the rows for which cnt[i]=0 , so if we remove a rook with {x,y} , we can add x back to row set if we have 0 rook in x row , and if we add a rook to set , we can erase x from row set , same goes for column set .

https://codeforces.com/contest/1679/submission/157366338 can anybody tell me why this code is is giving WA For problem C

Failing testcase: Ticket 7260thanks

can someone explain me their segment tree approach for B

Please can anyone tell me what's wrong with this solution: https://codeforces.com/contest/1679/submission/157426825 ?

I have written the code for Problem B. It's getting accepted but I am confused of why this solution is working under time limit. Can somebody help me with this? here is the submmison.

Thanks for interesting problems!) In problem C I have the solution that has TL3 (https://codeforces.com/contest/1679/submission/157589950) without writing the "ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);" line at the beginnig of programm. But the same solution with the "ios" line (https://codeforces.com/contest/1679/submission/157589989) works correctly. That's kinda sad when something like this happens(