Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

This contest thought me not to abuse unordered_map again, nice contest

GOT MY FIRST +69

I'm getting a message that says You are not allowed to view the requested page when I try to access the codes

Thanks for the wonderful round! I successfully reach blue :)

why does it show "N/A" when I read others' code?

340571620 Can anyone tell me what's wrong with my code for D ??

Where is the editorial?

Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

x — the maximum right index such that [i..x] has exactly k distinct; y — the maximum right index such that [i..y−1] has at most k distinct.

Won't that end up with x and y being the same index? Since unique elements in [i..a] <= [i..a+1], so the maximum index with at most k distinct will have exactly k distinct elements (unless there's no such a which has at least k distinct elements in [i..a])

Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

The submission link in D redirects to that of E.

The submission link in E doesn't open.

Alternate sol for D
for each letter a and b we try out all possible prefix blocks and calculate
the cost of making this prefix and corresponding suffix for that letter

#include<bits/stdc++.h>
using namespace std; 

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int64_t res = 1e18;
    for (int t = 0; t < 2; t++) {
        int x = count(s.begin(), s.end(), 'a');
        vector<int64_t> pref(x + 1), suf(x + 1);
        int64_t cur = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') {
                cur += i - cnt;
                cnt += 1;
                pref[cnt] = cur;
            }
        }
        cur = 0; cnt = 0;
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') {
                cur += i - cnt;
                cnt += 1;
                suf[cnt] = cur;
            }
        }
        for (int i = 0; i <= x; i++) {
            res = min(res, pref[i] + suf[x - i]);
        }
        for (int i = 0; i < n; i++) {
            s[i] = s[i] == 'a' ? 'b' : 'a';
        }
    }
    cout << res << '\n';
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) {
        solve();
    }
}

still cant access code for E

For problem G, there is an $$$O(n \sqrt{n})$$$ approach, which didn't get mentioned in the tutorial.

For the occurence of a number, let's define a fixed bound value, say $$$B$$$.

Consider the number of $$$a_i$$$ which occurs not less than $$$B$$$ times, and we can say that it is not more than $$$\frac{n}{B}$$$, according to the pigeonhole principle.

Then, for a query interval $$$\left[l, r\right]$$$, define $$$g = \lfloor \frac{r - l + 1}{3} \rfloor$$$, and one can process it differently when $$$g \ge B$$$ or $$$g \lt B$$$.

• If $$$g \lt B$$$, then we do a bruteforce on the interval $$$[l, r]$$$ to calculate the answers. Obviously, the time complexity for this part is $$$O(B)$$$.
• If $$$g \ge B$$$, observing that the answers can only come from the numbers occur not less then $$$B$$$ times, we can iterate these numbers, and check if one can be included in the answers with a preprocessed counting array. The time complexity is $$$O(\frac{n}{B})$$$.

Generally, the time complexity is $$$O\left(\frac{n^2}{B} + q \left(B + \frac{n}{B}\right)\right)$$$. Applying the powerful A-G inequality, we can set $$$B = \sqrt{n}$$$ and obtain the optimal time complexity $$$O\left(\left(n + q\right) \sqrt{n}\right)$$$, which is sufficient for the time limit.

However, the pre-calculated counting array has a size of $$$O(\frac{n^2}{B})$$$, which is too large for the limit of 256MiB. One need to alter the value of $$$B$$$ to satisfy both the time and space limit.

Or, one can obtain the counting array while iterating the often-occuring numbers separately, since each of them contributes the answer indepentently. Then the space complexity would be $$$O(n)$$$. (idea: Noobish_Monk)

Accepted submission: 340653926. $$$O(n)$$$ space submission: 340710637.

P.S. I apologize for my poor English. ((

Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

Auto comment: topic has been updated by __rose (previous revision, new revision, compare).

In the editorial for E, shouldnt the word 'maximum' be replaced with minimum in the following statement:

"x — the maximum right index such that [i..x] has exactly k distinct;"

can anybody tell me whats wrong with my submission :

https://mirror.codeforces.com/contest/2149/submission/340460656

Can someone please tell me what's wrong with my code for E? 340636181 It passes all tests exceptthe last one

Can we solve G with sweep line + Misra-Gries + sparse table?

G can also be solved using extended boyer moore's algorithm with segment tree in O(NlogN).

__rose In solution F, you have taken the input cin >> d >> h; But according to the question it should be cin >> h >> d; As it said that health should be the first input then the distance d.

The merge operation for G is genius.

During the process of Misra-Gries algorithm ,if a key is excluded from the k-1 candidates, we can prove that every occurence of the key uniquely specifies k-1 occurences of other keys. Thus in the end, its frequency multiplying k can't outnumber n.

And it still make sense if you merge the infomation.

Hii can anyone help me here, Why is my solution to Problem C giving TLE on 7th test case Submission ID: 340421354

t = int(input())
for _ in range(t):
    n, k = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    if k == 0:
        print(a.count(0))
    else:
        curr = a.count(k)
        seta = set()
        for i in a:
            if i < k:
                seta.add(i)
        required = k
        available = len(seta)
        print(max(curr, required - available))

According to my understanding this is still O(n) or max O(nlogn) I'm all ears, It's been a while since i started CP again, maybe I'm missing something Thank you in advance

Can anyone explain this in question F editorial ?

For fixed m, to minimize the total cost we make the run lengths as equal as possible. Let
      a = ⌊d/s⌋, r=d mod s.
Then r runs have length a+1 and s−r runs have length a

I didn't understand the logic.

i have a problem:in D,i use int to store my ans,it's wrong.The answer code also use int but it's AC.why?I apologize for my poor English。

Is there any way Mo's Algorithm could be used to AC problem G?

I tried it to make it as efficient as possible, but it still TLEs: 340736003

Is it really high-risk to use randomized algorithms or non-deterministic algorithms (like problem G this time or using simulated annealing in some problems) in Codeforces competitions? I often hear statements like "randomized algorithms are easily hacked." So, what are the methods to hack mt19937 or rand? How can we make hacking randomized algorithms more difficult?

Editorial of F says —

Then r runs have length a+1 and s−r runs have length a

How to arrive at this conclusion ?

can someone tell me how to hack a unordered objects ... theory behind it

For D there is one more logic very similar to it which I wrote in contest I never thought that the issue would be declaring ans = INT_MAX will give me WA and couldnt think later on :(.

Check the code — 340845649 in contest and this only diff is setting ans = LLONG_MAX.

Ideally some questions are good saying that the answer might not fit in 32 bits it should have been provided here _/_.

A simpler and more readable implementation of Tutorial for E.

ans =0;
// left border
ll x;
// right borders
ll y =0;
ll z=0;	

loop(x, 0, n, 1) {
	while (y <= n && m1.size() < k) {
		if (y < n) m1[a[y]]++;
		++y;
	}

	while (z <= n && m2.size() <= k) {
		if (z  < n) m2[a[z]]++;
		++z;
	}

	ans += std::max(0LL, std::min(z - 2, x + r - 1) - std::max(x + l -1, y - 1) + 1);
	// [x..y) is the SMALLEST window with exactly k distinct characters  
	// [x..z - 1) is the LARGEST window with exactly k distinct characters
	// all the valid windows with x as left end and all the indices [y, y + 1, .., z - 1] as right end

	// advance the left pointer  
	if (--m1[a[x]] == 0) m1.erase(a[x]);
	if (--m2[a[x]] == 0) m2.erase(a[x]);
}

For 2149D - A and B I implemented it with O(n) solution.340468951

Notice, that in problem 2149G - Buratsuta 3 in the randomized solution author remaps all of the values to the segment $$$[ 0, 2 \cdot 10^5 - 1 ]$$$ in the preprocessing state and then stores all indices as the array of vectors, giving constant time access in query. This solution works in $$$\mathcal{O}(k\log{}n)$$$ per query in the worst case.

If you use the map of vectors to store all of the indices instead, the solution will not pass the TL, but will still have the $$$\mathcal{O}(k\log{}n)$$$ complexity per query, but with a larger constant factor. For example, the input with $$$n = 2 \cdot 10^5$$$ distinct numbers and $$$q = 2 \cdot 10^5$$$ queries with $$$l = 1$$$ and $$$r = n$$$ runs in 7s on average on my machine, when using the map of vectors, and will get TLE in online judge (see this 340925425 submission).

However, using the array of vectors or hashmap of vectors with custom hash runs for about 5.5s on my machine (on the above test) and will pass the TL (see this 340922007 submission, for example). Also, the author's solution with remapping to array of vectors runs in 2.5s on server, which is a second faster, then the hashmap of vectors solution. So, consider using these structures, if your solution doesn't pass TL.

Suppose we use exactly m rests. Then the d moves split into s=m+1 consecutive runs of moves between rests. If a run has length t, its health cost is the triangular number

T(t)=t(t+1)2 because the run's j-th move costs j health. For fixed m, to minimize the total cost we make the run lengths as equal as possible.

This is in the editorial for the F Question. Can someone explain how is minimizing the total cost related to the run lengths being equal?

What is the purpose of making so tight requirements for G - Buratsuta 3 problem (at least in randomized solution)? You forced to remap values of original inputs, because using map is too slow. Answer format require possibility of restoring original $$$a_i$$$ value. Just several steps, which doesn't make solution more interesting. Anti-hash tests is icing on the cake in this problem. It's not common, to see the authors want you optimize constants.

Nice idea thought.

Just an illustration, how long it took me, to come up with this optimization :)

I’m trying to understand the trade-offs between different containers in C++ for competitive programming.

Specifically, when should I prefer map, unordered_map, unordered_map with a custom hash, or just use a vector instead? I know that they have different complexities, memory usage, and collision risks, but I’d like to know some practical guidelines or common situations where one is better than the others. Any suggestions would be appreciated!

inequalityforces

It is still showing N/A for me for all the codes.

Hi, how does this condition C(m)≤h+m−1 satisfies that we don't have zero health in the intermediate steps before reaching the destination ?

Can somebody explain why it is SUM(pi — L + i) rather than SUM(pi-L)

Hello,

My solution 340473928 for problem 2149C has been marked as coinciding with several others. I would like to clarify that I did not share my code with anyone nor did I copy from others. I worked on the problem independently.

It is possible that the similarity occurred because the problem has a standard approach and many participants may have ended up with similar implementations. I also did not use any public code-sharing platform during the contest.

I kindly request you to review my case. I assure you that I respect the rules of Codeforces and will be careful in future contests to avoid any unintentional issues.

Thank you for your understanding.

— Xyra

Nice problemset, but i found it kind of bizarre that in G all of the arrays are sorted in the testcases, and the real problem doesn't say nothing about this. I think it would be nice to put at least one problem where the array is not sorted, so it would be clear that the array is not necessarily sorted in the problem

Can anyone please explain in problem D why we are subtracting i from every position value in p? Why calculate (p[i] — i) when i increments from 0 to positions.size()?

what is my mistake in the question 3 code ?

I am doing the same thing as the tutorial said , but mine is failing the 5 test case ,

solution : 340408663

For problem F:

why we can use s=m+1 and m belongs to [0,d] at the same time?

If m=d, s seems can be m rather than m+1.

h=1 d=2

(1)rest,h=2,p=0

(2)move,h=1,p=1

(3)rest,h=2,p=1

(4)move,h=1,p=2

Here m=d=2 and s=2

Emm…….It's really a big challenge for me to understand the English editorial or problem.Is there anyone have some good advice for me to improve my abilities about English reading?

x— the maximum right index such that [i..x] has exactly k distinct; y— the maximum right index such that [i..y−1] has at most k distinct.

i mean shouldn't x be the minimum right index such that [i...x] has exactly k distinct elements?? otherwise x and y-1 will be the same positions always which will yield wrong solution !!!!

At First i was unable to solve the problem Div3-E. Then i did this 2 problems from CSES and got hint.

1. Distinct Values Subarrays (Code)
2. Distinct Values Subarrays Exactly K(Code)

For anyone trying to solve Problem-E by his own, can try out these problems for hint.

#include<bits/stdc++.h>
#define ll long long int 
#define vi vector<ll>
#define vvi vector<vi> 
#define vvvi vector<vvi> 
#define pb push_back
using namespace std;

void solve()
{
   int n;
   cin>>n;
   string s;
   cin>>s;
   
   vector<int> a_pos, b_pos;
   for(int i=0;i<n;i++){
       if(s[i]=='a'){
           a_pos.push_back(i);
       }
       else{
           b_pos.push_back(i);
       }
   }
   int a_len = a_pos.size(), b_len = b_pos.size();
   
   if(a_len==0 or b_len==0){
       cout<<0<<endl;
       return;
   }
   int a_cost = 0, b_cost = 0;
   int a_med = a_pos[a_len/2], b_med = b_pos[b_len/2];
   
   for(int pos:a_pos){
       a_cost += abs(pos-a_med);
   }
   a_cost -= (a_len-1);
   
   for(int pos:b_pos){
       b_cost += abs(pos-b_med);
   }
   b_cost -= (b_len-1);
   
   cout<< min(a_cost,b_cost)<<endl;
}

int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

int t=1;

cin>>t;

while(t--)solve();


return 0;
}    
   
 

Can someone why this code for problem D is failing in test#2?

How did the randomized solution for G pass? I tried literally the same think just with K = 41 and it got TLE on test case 15, i submitted a bunch of other submissions but everything gave TLE around tc 15.

can anybody explain E to me in easier language?

I can't believe that problem G can be solved by randomized method! I solve it with Segment Tree + Binary search, the code of which is REALLY messy and hard to debug. What an intelligent solution it is!!

It's easy to get rid of the log in the randomized solution for G by simply processing queries offline: 361324634