Is that Russian of problems?

Found this: https://codeforces.com/blog/entry/91134

Wait till LTDT hears this lmao

how many announcements would you like to do?

(authors): YES

meme king indeed!! getting meme ideas mid contest

live-streaming? More like live-embarrasing-himself

Petition to make all CF rounds unrated cause someone cheats anyways.

So if I perform bad in a contest, I can just go live stream and the contest will become unrated?

Though his livestream is very informative.

I was thinking of binary lifting too... but how do you find which ancestor node to start taking gold from?

I did it using binary lifting. Essentially for each query, I lifted to the farthest ancestor with gold>0 and kept doing it until I reach the required gold. Since a node gets lifted to only once, complexity would be O(QlogQ). AC in 1.6s

I feel you, also got my AC 8 minutes after the contest, since I didn't manage the binary lifting in time :( (So yes, binary lifting worked for me)

which line you were confused in ?

I don't agree, I found of the 2 custom definitions (unstable, beautiful) quite precise.

In fact I got quite annoyed at the announcements, e.g. 'Strings "0" and "1" are unstable.', well this follows from the definition since there are no adjacent characters...

The authors made more than enough announcements imo, let's not play blame-game after each contest. :')

I was seeing like basically it was something that trees was getting split, as we can avoid the one that had already become zero, but was having no clue on how to pass the information of this least non-zero ancestor easily to its subtree child. I thought going with dsu, but again processing was to be done in online way, so got no way :(

It was pretty easy. You just need to iterate over two cases 10101... and 01010.... Then just remove overcounted blocks of ????....

I managed to do it using 2d DP, there's a special case for question marks though

string S;
ll DP[200010][2];
 
void solve() {  
    DP[0][0] = DP[0][1] = 0;
    read(S); S = " " + S;
 
    ll ans = 0;
    for (int i = 1; i < S.size(); i++) {
        if (S[i] == '?') {
            DP[i][0] = DP[i - 1][1] + 1;
            DP[i][1] = DP[i - 1][0] + 1;
        }
        else if (S[i] == '0') {
            DP[i][0] = DP[i - 1][1] + 1;
            DP[i][1] = 0;
        }
        else if (S[i] == '1') {
            DP[i][0] = 0;
            DP[i][1] = DP[i - 1][0] + 1;
        }
    }
 
    /*
    for (int i = 1; i < S.size(); i++)
        print(DP[i][0], ' ');
    printl("");
    for (int i = 1; i < S.size(); i++)
        print(DP[i][1], ' ');
    printl("");
    */
 
    ll cur = 0; 
    for (int i = 1; i < S.size(); i++) {
        if (S[i] == '?') 
            cur++;
        else 
            ans -= cur * (cur + 1) / 2, cur = 0;
        ans += DP[i][0] + DP[i][1];
        DP[i][0] = DP[i][1] = 0;
    }
    ans -= cur * (cur + 1) / 2;
    assert(ans > 0);
 
    printl(ans);
}
 
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int ___reps___ = 1;
    read(___reps___); 
    for (int ___cur___ = 1; ___cur___ <= ___reps___; ___cur___++) {
        // print("Case #", ___cur___, ": ");
        solve();
    }
}

I used two pointers lol. Just have two arrays, one for the occurrences of each character for odd indices and the other for even indices. Whenever you move along the string you can change the arrays accordingly and check whether it can be made unstable.

There's no way string concatenation can be O(1)

appending one character at end of string is O(1) in C++.

That is correct. I passed with this approach.

Yes, and for update just go traversing through all its parents that will be O(k).

Yes, the complexity of each update would always be O(k) since the depth of the tree is k.

Yeah bro. At first time i was also confused of how to implement it but then i realized: you should try Segment Tree. Hihi nice problem =)

Hint: you should bruteforce substring which you want to sort

Try this case:-

0??0

In 48th line, you use i < imp.size() - 1. Here, size() returns unsigned int. If imp.size() == 0, then 0 - 1 = 4294967295 (unsigned int). That's why you got TLE.

Addition: In C++17(64 bits), size() returns signed int.

because it is not englishforces, it's codeforces.....

Although point 2 didn't affect most people with experience, you also could have just written "every" instead of "some".

I bombarded 2 clarifications after first announcement.
So here is what happened with me -
I understood that "any" means "every" here. I wrote a correct soln. Passed sample. Just before I was going to press that damm submit button first announcement came.

In the chaos, I completely forgot that I was supposed to count unstable string only. For 2 mins I was like this problem asks to count stable string. I was like this announcement explicitly say "0" or "1" shouldn't be counted as valid answers contrary to what Vacuous truth.

I spend the next few minutes refreshing the problem statement in the hope of change in the sample output. Later ended up sending the first clarification because if I don't 1 length strings there is no way I can produce the expected sample output for a given sample.

It took me some time to realise that the initial version I assumed was correct and I should just press that submit button.

Feedback / How the statement would have been better -
Unstable string definition could have been avoided. You could have just said that a string is beautiful if it consists of alternative '0' and '1' characters. Some examples of beautiful strings are ......

Now we have a string s which consists of '0', '1' and '?'. Count the number of substrings that can be made beautiful by replacing '?' with '0' or '1'. <Insert something about you should independently replace '?' for each substring.>

12 hours hacking phase then 12 hours until system start testing :P so nearly 24 hours

here It was totally implementation based i agree. But Interesting for me because it was the first of its kind i ever tried

Here you go 118435824, I tried to implement it as nicely as I could but it may not be good enough as I have not been coding for sometime now.

118438203

(Submission : 118424181) I created a structure for the match. Then kept a 2d vector of matches, where I stored all n phases of the tournament.

the main problem i was having was was in update function, whether to update left child or right child. i used in time out time concept since the build function is basically a dfs. everything else was pretty much segment trees. but it took me 70 fucking minutes to come up with.

I only know a $$$O((\sum len)\sqrt{\sum len})$$$.

Try to solve the case when $$$n\leq 500$$$,and $$$len\leq 500$$$.

For Problem F first we observe:

• if two strings are equal, this adds 0 to the sum

• if two strings have equal prefix and suffix and the different part ist sorted in one of them, then it adds 1 to the sum

• if they cannot be transformed into each other, because they have different amount of letters, then they add 1337 to the sum

• else they add 2 to the sum, since we can just sort both of them

We seperate the strings into groups, corresponding to the amount of letters they have. All pairs between different groups add 1337 to the sum. So we only regard pairs in the same group. Now we distinguish two cases:

1. We have many short strings.

2. We have a few very long strings.

For case 2 we can simply check all strings pairwise, whether they are same or have the same prefix/suffix and the different part is sorted in one of them or not, to add either 0 or 1 or 2 corresponding to the observations. This is $$$O(n^2 \cdot len)$$$

For case 1 we do it the other way round. First we sort all strings, so we can binary search on them. Now we iterate all strings $$$O(n)$$$. We iterate over each subsegment of the string $$$O(len^2)$$$. We sort $$$O(len \cdot log(len))$$$ each subsegment and binary search whether the corresponding partly sorted string exists $$$O(log(n))$$$ in the group. If it doesn't exist, we add 2 to the sum. This additions need to be divided by 2 in the end, since we check each pair twice. We need to take care to not count one pair more than twice. e.g. look at abcdefg and abedcfg. We could sort the second string from index 1 to index 7 and would obtain the first string. But we could also sort it from Index 2 to Index 6 and would also obtain the first string. To exclude this, we only count, if sorting [l,r] changes the letters at position l and r. This will be $$$O(n \cdot log(n) \cdot len^3 \cdot log(len))$$$

I did check n<len^2 to decide whether to take approach 1 or approach 2. It passed with 400ms for me. Edit: I changed it now to n<6800. Got hacked once and then I did a series of checks to find the ideal cutoff. It is 6800 for my algo.

Also note: all strings are pairwise different. The Problem doesn't mention this directly, it is only mentioned in "Input". That took me writing some ugly code and more cases till I noticed that.

Does somebody have a more general solution, which doesn't need to distinguish between those two cases? I did try analyzing some dependencies between strings and maybe find regularities or trying to construct some sort of graph or dp over the string to count, but I didn't manage that.

lol I missed E on Atcoder abc 198 because I misread the statement and had a 9 instead of a 10 for the max number of unique characters. Passed 2 minutes after contest ended but ¯\_(ツ)_/¯

Same to me also

You can use a map to store the index corresponding to the game number while making the tree. This will help you with unnecessary mathematical relations.

I think D looks more like a binary heap (eg the one used for priority_queue) than a segment tree

Overflow. I had the same problem, the answer to input with 20000 '?'s doesn't fit in an int

Hi 1000 cyans.

.size() for vector is O(1). Check complexity in cppreference

Change for(i=0;i<odd.size()-1;i++) to for(i=0;i<odd.size();i++) and see magic. .size() is unsigned 64 bit integer type. When its 0 subtracting -1 for it makes it 2^64-1.

Just run cout<<a.size()-1<<endl; on an empty vector a once.

if vector.size()>0then your both code will work fine.but if vector.size()==0 then vector.size()-1 will give an unexpected huge value,thats why your 2nd code gave TLE.It's not about time complexity :)