include &lt;bits/stdc++.h&gt;

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

3 years ago, # |

+35

I hope you enjoyed this round!

→ Reply

Hamroz_JONN

3 years ago, # ^ |

← Rev. 4 →

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

Thanks

→ Reply

Greensip

3 years ago, # |

← Rev. 2 →

+65

I 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

$$$\sum_{str \in sub_{t_i}(s)} f(str)$$$

for each query.

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

→ Reply

LXH-cat

3 years ago, # |

E good problem,but didn't solve.qwq

→ Reply

Sai_t

3 years ago, # |

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

→ Reply

bruhify

3 years ago, # ^ |

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

→ Reply

Sai_t

3 years ago, # ^ |

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

→ Reply

harshitsoora

3 years ago, # ^ |

← Rev. 2 →

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

→ Reply

eroinevs

3 years ago, # ^ |

← Rev. 3 →

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);
By default, it is set (true);
By turning it off(false), you avoid synchronization with C;
Read more here: https://www.geeksforgeeks.org/fast-io-for-competitive-programming/
Or here:https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

→ Reply

harshrajivjain10

6 months ago, # ^ |

what would be the problem with cin and cout?

→ Reply

weakestOsuPlayer_244

3 years ago, # ^ |

Might be your segtree since mine runs under 300 ms.

→ Reply

Sai_t

3 years ago, # ^ |

I will improve my segment tree. thx!

→ Reply

nicolasalba

3 years ago, # ^ |

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

→ Reply

weakestOsuPlayer_244

3 years ago, # ^ |

+12

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

😄

→ Reply

Saucemaster102

2 years ago, # ^ |

Hey sorry to disturb, but I too used segment tree but with rangeSum, here is my submission can you please tell me why would it give me WA on tc 3

→ Reply

HarshaNP

2 years ago, # ^ |

Hey. Even i tried range sum approach using segment tree. But I'm getting WA on test 3.. Can u tell how you corrected it and got AC.

→ Reply

variety-jones

2 years ago, # ^ |

Take a look at Ticket 16173 from CF Stress for a counter example.

→ Reply

HarshaNP

2 years ago, # ^ |

thank you

→ Reply

mridul_meerut

3 years ago, # |

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

→ Reply

Thomas_Michael_Shelby

3 years ago, # ^ |

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.

→ Reply

Gravitino

3 years ago, # |

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

→ Reply

nicolasalba

3 years ago, # |

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://mirror.codeforces.com/contest/1679/submission/157262319

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

→ Reply

shadow9236

3 years ago, # ^ |

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

→ Reply

Pawan402

3 years ago, # |

can someone tell me why my C got FST

→ Reply

swarup_312

3 years ago, # |

Problem C :

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

Click here 157271735

→ Reply

shadow9236

3 years ago, # ^ |

You 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

→ Reply

walidGeuttala

3 years ago, # ^ |

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.

int n, q;

int lowbit(int x) {
    return (x&-x);
}

void upd(int idx, int v, vii &ff) {
    for(;idx<=n; idx+=lowbit(idx)) ff[idx].f += v;
}

int sum(int idx, vii &ff) {
    int ans = 0;
    for(;idx; idx-=lowbit(idx)) ans += ff[idx].f;
    return ans;
}

void solve() {    
    cin >>n >>q;
    int t, x, y, x1, y1;
    vii f1(n+1, MP(0, 0)), f2(n+1, MP(0, 0));
    while(q--) {
        cin >>t>>x>>y;
        if(t == 1) {
            f1[x].s++;
            f2[y].s++;
            if(f1[x].f == 0) upd(x, 1, f1);
            if(f2[y].f == 0) upd(y, 1, f2);
        }else if(t == 2) {
            f1[x].s--;
            f2[y].s--;
            if(f1[x].s == 0) upd(x, -1, f1);
            if(f2[y].s == 0) upd(y, -1, f2);
        }else {
            cin>>x1>>y1;
            int ans1 = sum(x1, f1) - sum(x-1, f1);
            int ans2 = sum(y1, f2) - sum(y-1, f2);
            if(ans1 == x1-x+1 || ans2 == y1-y+1) cout<<"yes\n";
            else cout<<"no\n";
        }
    }
}

→ Reply

LastDance_NotLastOfMe

3 years ago, # ^ |

if(t == 1) {
        f1[x].s++;
        f2[y].s++;
        if(f1[x].s == 1) upd(x, 1, f1);
        if(f2[y].s == 1) upd(y, 1, f2);
    }

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

→ Reply

walidGeuttala

3 years ago, # ^ |

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

→ Reply

Jogesh

3 years ago, # |

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

→ Reply

3 years ago, # ^ |

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

→ Reply

aryannkhanna07

3 years ago, # |

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

Thanks

→ Reply

3 years ago, # ^ |

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

→ Reply

magleb

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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

→ Reply

vaal

3 years ago, # |

RMQ using segment tree

struct SegTree {

// 1 indexed
int size;
vi arr;
void init(int n){
    size=1;
    while(size<n) size*=2;
    /* first init everything to 0 and then update arr to the initial array in question. idk if this 
       will work for range max queries */
    arr.assign(2*size, 0);
}
void update(int i, int v, int x, int lx, int rx) {
    if(rx-lx==1) {
        arr[x] = v;
        return;
    }
    int m=(lx+rx)/2;
    if(i<m) update(i,v,2*x+1,lx,m);
    else update(i,v,2*x+2,m,rx);

    // change here fr range max queries
    arr[x]=min(arr[2*x+1],arr[2*x+2]);
}
void update(int i, int v) { update(i, v, 0, 0, size); }

// [b, e)
int query(int l,int r, int x, int lx, int rx) {
    // change here to llongmin fr range max queries
    if(lx>=r||l>=rx) return LLONG_MAX;

    if(lx>=l&&rx<=r) return arr[x];
    int m=(lx+rx)/2;
    int s1=query(l, r, 2*x+1, lx, m);
    int s2=query(l, r, 2*x+2, m, rx);

    // change here fr range max queries
    return min(s1,s2);
}
int query(int l, int r) { return query(l, r, 0, 0, size); }

};

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?

→ Reply

azad241

3 years ago, # |

← Rev. 2 →

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

→ Reply

3 years ago, # ^ |

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

→ Reply

vitosevskich

3 years ago, # |

← Rev. 2 →

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

→ Reply

variety-jones

3 years ago, # ^ |

Failing testcase: Ticket 7208

→ Reply

nikich340

3 years ago, # |

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.

→ Reply

CHY_YASIR

3 years ago, # |

← Rev. 2 →

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?

→ Reply

3 years ago, # ^ |

Here are some problems which are quite similar to problem D from this round:

EDU 128 C

EDU 126 C

→ Reply

zym

2 years ago, # ^ |

He meant the dp problem, not the binary search problem

→ Reply

hitesh21

3 years ago, # |

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?

→ Reply

Skeef79

3 years ago, # ^ |

loop is an edge that connects a vertex to itself

→ Reply

hitesh21

3 years ago, # ^ |

oh ok now i understand. Thanks!

→ Reply

rakreeritris

3 years ago, # |

-11

how does this code works for B

include <bits/stdc++.h>

define ll long long

using namespace std;

int main() {

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

endif

ll n, p, q, sum = 0, temp = 0;
map<ll, ll> mp;
cin >> n >> q;
for (ll i = 0; i < n; i++)
{
    cin >> p;
    mp[i] = p;
    sum += p;
}
while (q--)
{
    ll pos, x, t;
    cin >> t;
    if (t == 1)
    {
        cin >> pos >> x;
        pos--;
        if (mp.find(pos) == mp.end())
        {
            sum = sum - temp + x;
            mp[pos] = x;
        }
        else
        {
            sum = sum - mp[pos] + x;
            mp[pos] = x;
        }
    }
    else
    {
        cin >> x;
        mp.clear();
        temp = x;
        sum = temp * n;
    }
    cout << sum << endl;
}

} 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

→ Reply

3 years ago, # ^ |

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

→ Reply

rakreeritris

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

← Rev. 2 →

$$$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: :/

→ Reply

sankooru14

9 months ago, # ^ |

Hey, why did you use map instead of unordered_map?

→ Reply

epsilon_573

3 years ago, # |

Video Solution for Problem D.

→ Reply

DeathCoder_Ji

3 years ago, # |

Can anyone post the editorial for C in easy words?

→ Reply

lis05

3 years ago, # ^ |

← Rev. 2 →

-6

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.

→ Reply

dhruv7888

3 years ago, # ^ |

← Rev. 2 →

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 .

→ Reply

steveonalex

2 years ago, # ^ |

This can be solved by using Square Decomposition too. Strangely enough, I've seen Segment Tree solutions which ran slower than my solution (These have almost the same optimization as mine), despite Seg tree has the complexity of O(N log N), and Square Decom has the complexity of O(N sqrt N). 165773252

→ Reply

ilgizarka

3 years ago, # |

← Rev. 2 →

Thanks for interesting problems!) In problem C I have the solution that has TL3 (https://mirror.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://mirror.codeforces.com/contest/1679/submission/157589989) works correctly. That's kinda sad when something like this happens(

→ Reply

f.nasim

3 years ago, # |

For problem C, I used a square root decomposition data structure to pre-calculate query results (number of rooks in ranges of rows/columns).
The solution seems to be fast enough as it has passed so many cases.
My solution (https://mirror.codeforces.com/contest/1679/submission/157520096) produces wrong answer on test 35.
Can anybody provide some insight on what might be wrong with my solution?

→ Reply

variety-jones

3 years ago, # ^ |

← Rev. 2 →

Failing testcase: Ticket 7271

→ Reply

f.nasim

3 years ago, # ^ |

Thanks. Have found the error. Problem solved.

→ Reply

amogh17009

3 years ago, # |

Hi, Could someone please help me out? Am not able to understand why https://mirror.codeforces.com/contest/1679/submission/157598442 throws TLE in test 7.

Approach: 1. Binary search over possible answer 2. for a potential solution x, build graph with only edges where both vertices are valid (a[node] <= x) O(m) 3. Dfs to check for cycle- 2 times dfs (To compute tin, tout for nodes and then to check) O(m+n) 4. If not cycle dfs to get the longest path O(m+n)

Complexity is be O(m+n)*log(MAX)

→ Reply

3 years ago, # |

For problem C, if using C++, what data structure is used to store freeRows? If we use vector, insert an element in order will need O(n) time complexity? If we use set or list, we cannot do binary search for query type 3?

→ Reply

3 years ago, # ^ |

Seems we should just use "set"? But I got TLE: https://mirror.codeforces.com/contest/1679/submission/157773752

I see most acceptable solution uses BIT. Any acceptable solution uses the algorithm described in the tutorial?

→ Reply

Bisquito

3 years ago, # ^ |

Check this

→ Reply

2 years ago, # ^ |

Thanks! But it is interesting that it is TLE now with the same implementation.

→ Reply

Andalus

2 years ago, # ^ |

The issue is not due to set (which is very fast), but because your I/O (cin, cout) is too slow (due to syncing with stdio). In particular, the input may have a very large number of values, so the syncing delay causes TLE.

For fast I/O with cin and cout, you should add the following two lines to the start of your main function (or anywhere before the first use of cin/cout): ios_base::sync_with_stdio(false); cin.tie(NULL); Note that if you do this, then you shouldn't use scanf/printf alongside cin/cout, since they are not synchronized (e.g., a later scanf would read the same data that an earlier cin already read). This is fine if you don't use scanf/printf anyway.

Yes, I know your comment is two months old, but I noticed that even your latest submissions continue to use cin/cout without disabling the synchronization, so I advise you to add those two lines to your template before you encounter another TLE in the future due to I/O syncing delays.

→ Reply