I hope you enjoyed this round!

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

for each query.

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

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

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

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

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

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 here 157271735

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

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

Thanks

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

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

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

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.

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?

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?

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

Video Solution for Problem D.

Can anyone post the editorial for C in easy words?

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(

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

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)

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?

does it say "Unable to parse markup [type=CF_MATHJAX" just for me when the editorial button is clicked on problem C?

A wonderful contest with problems of different level, and they are expecially suitable for a Chinese like me to improve my skill for the coming competitions. The editorial is also up to standard.

Wtf????

this code(C. Rooks Defenders) can anybody help why my code is giving wrong answer on 23649th token?,please please https://mirror.codeforces.com/contest/1679/submission/158499479

Do you know any similar problems to the 1679B — Stone Age Problem?

If anyone is interested, problem C can be solved with sqrt decomposition. https://mirror.codeforces.com/contest/1679/submission/158598103 my submition

If someone wants Here is my Submission for Div2 D : Toss a coin to your graph

Can someone help to debug my solution for problem D.

getDepth function returns -3 if cycle is detected else returns it's depth.

very nice tutorial for F

why am i getting wa on tc 3 [46944th token] [my solution](https://mirror.codeforces.com/contest/1679/submission/176050133)

In Problem C, What am I doing wrong here?

Problem D is really nice. It is of fine difficulty for problem D, not extremely difficult implementation, and overall a really well-crafted problem.

What am i doing wrong here in problem B 278706517