Fenwick appraoch for 1234D : Solution

Implementation similar to: CodeMonk Problem

Awesome contest by the way! :D

My solution to E: https://codeforces.net/contest/1234/submission/61676673

Just consider how the distance of each pair in the array changes in permutations.

Let the smaller number in the pair be m and the other be n;

The distance increases by m-1 when i=m because m goes to the front and the distance increases 2m-n when i=n because n goes to the front and m shifts 1 backwards. For i from m+1 to n-1 the distance simply decreases 1 because one of the number between them goes to the front.

I hope my explanation makes sense as English is not my first language:D

Weak Example in F makes me WA on 5........ I want strong example QAQ (sorry to my poor English :D

How can we do C with dfs?

It is obvious that because of dynamic programming we need to remove at most one bit from our mask to cover all possible submasks that can update our answer. What is this means ？

I did the testing for F and found out few Test Cases. Surprisingly the WA code when ran on custom innovation, It gives same answer as that or correct code, But when it's executed locally or on some other online Compiler(other CP sites like codechef), the WA program fails on following Test Cases.

Though If anyone finds the reason behind the behaviour of WA code in Custom Innovation, do let me know. I'm quite curious about this.

My code for problem C. https://codeforces.net/contest/1234/submission/61656247 Can anyone help me with that? I considered that the number of 3,4,5,6 type pipes should be odd and if a pipe is of 3,4,5,6 type in one row,it should be of the same type in the corresponding index of the other row.

I also applied segment tree approach 61686336. But it's giving TLE. Can anyone please tell me where I went wrong?

I used approach of tutorial D. Can someone please explain why lower_bound(s[i].begin(), s[i].end(), l) is getting TLE but same solution with s[i].lower_bound(l) instead, not?

• TLE solution: https://codeforces.net/contest/1234/submission/61687000
• AC solution: https://codeforces.net/contest/1234/submission/61686913

Only difference is way of using lower_bound.

Why does ceil(double(sum)/n) give a wrong answer on but (sum+n-1)/n doesn't.

can someone help in finding issue in this code https://codeforces.net/contest/1234/submission/61661254. it's failing on 1 test case on codeforces compiler. but locally it passes

Решение в $$$E$$$ ломается, потому что в пересчёте длин предполагается, что второй элемент будет оставаться на месте, что не верно в случае $$$x_i = x_{i + 1}$$$.

D можно решить с помощью дерева Фенвика/ отрезков + использовать что-то похожее на префиксные суммы. Сделаем несколько наблюдений: 1). Если мы меняем конкретный символ, то значение префиксных сумм(количество элементов на префиксе) на подотрезке с pos до конца строки уменьшится на 1.

2). Для нахождения ответа на 2 запрос следует проверить, что на подотрезке с r по l-1 был хотя бы один символ (то есть значение префикс.сум[r]-префикс.сум[l-1] было больше 0)

3). Чтобы хранить значение префиксных сумм всех 26 букв английского алфавита, будем использовать двухмерный мас сив (при этом не только префиксные суммы, но и дерево отрезков/Фенвика)

4). Обновляли значение конкретных символов на подотрезке — (в Фенвике/ДО добавлял и в случае,если меняли на данный символ, вычитали, когда меняли данный элемент) — префикс.сум[r]-префикс.сум[l-1]+(значение в дереве[r]-значение в дереве[l-1]) (на подотрезке с pos до длины строки вычитали на 1 в случае уничтожения(изменения) данного элемента, прибавляли на 1 в случае изменения на данный элемент)

Теперь осталось реализовать ДО/Фенвик и использовать данные наблюдения.

Well. I have a deterministic solution for F. vovuh I don't know where your solution will break. But intuition is not coming. My approach:

dp[mask][len] will store maximum starting index for all the submask of mask with length len. then we can simply find the answer for it's complement for all length. link to my solution:

61694665

Damn slow python... Got TL with Segment Tree

Very Nice Explanations and Clear Editorials.

I wonder why I got TLE in pronlem D when using Segment Tree......(61656622)

(sorry for my poor English x(

My solution got tle in D in system testing and the same solution is accepted on submitting after System testing

https://codeforces.net/contest/1234/submission/61710080

https://codeforces.net/contest/1234/submission/61641496

I think this is not as simple as before

After the contest I tried to write B2 with STL deque,but when I use unordered_map it got TLE but map got AC.In my previous conciousness map should be slower than unordered_map,what's wrong with unordered_map in B2?
The unoredered_map version TLE:61711501
The map version AC:61711675

SquareRoot Decomposition approach for D: 61667541

Need help in this. https://ide.codingblocks.com/s/137727 for problem D this solution is getting WA for test case 2 https://ide.codingblocks.com/s/137726 I just switched line 91 and 92 got AC for all the test cases. Why am i getting this. I created 26 sum query segment trees and for every alphabet if the sum of segment is greater than 0 then there is that distinct character in it and I increased the answer for that query. Why does swapping two line get me WA?

For B2:

Changing from unordered map to map gave AC. The unordered map is faster than the map then why did I get TLE?

Thanks.

I dont think prob E is a 2000-difficulty problem, just like a 1700 or 1800 problems in a div2 contest. I also saw a quite easy task in another div3 before that had 1900-difficulty. I feel weird when there are a lots overrating problems in div3, so I wonder how ppl rate difficulty for problems

Anyone can explain why using std::set gets AC but gp_hash_table (policy based data structures)(https://codeforces.net/blog/entry/60737) gets TLE? I'm very confused.

AC: 61716953

TLE on test 20: 61712878

I used a segment tree for problem D. I tried the segment tree that had unordered_map(61658230),set(61650912) and map(61656330) as elements of its nodes but all three showed TLE. Can anybody help me figure out where is the mistake in my code.

As C have only 2 input strings, I zipped them, and used regex with eval, analyzing pairs of symbols (columns). An alternative to if-else blocks. Perl code 61668008 (or shorter without zip: 61669016)

Alternate approach for E, any two consecutive elements of the array x and y contribute abs(x-y) to all f(pi(n)) where i is less than min(x,y) or when i is greater than max(x,y). x and y contribute abs(x-y) -1 to all f(pi(n)) when i lies between x and y.

Using a Segment tree with lazy propagation we can do the above contributions/range updates for all pairs of consecutive elements. Answers will be the ranges i,i for i: 1 to n

Here is the code : https://codeforces.net/contest/1234/submission/61666909

In problem E, I have this stupid question which I cannot figure it out on my own -_- .

In the code provided above:

for (int i = 1; i < n; ++i) {
		res[i] = res[0] - cnt[i];
		for (auto j : adj[i]) {
			res[i] -= abs(i - j);
			res[i] += j + (j < i);
		}
	}

So why res[i] += j + (j < i) here. I thought when we move the element i to position 1 then the cost should be res[i] = j-1 + (j < i), shouldn't it?

Thanks in advance <3

Problem D: I implemented editorial's solution in JAVA. For that I had to use TreeSet for lowerbound() function. Here's my JAVA code: 61727406

Can somebody explain me problem F's soln? Sorry but i am unable to understand the editorial?

Need DP idea of Problem C.

can anybody explain, what does this mean ?

"Let dp[mask] be the maximum number of ones in some mask that is presented in the given string and it is the submask of mask" , here what does the submask of mask mean?

Didn't understood the tutorial of E could someone pls elaborate on making prefix arrays.

Problem A can also be solved using binary search :: Solution : https://codeforces.net/contest/1234/submission/61633785

【Problem E】 I did not understand what tutorial says. please tell me what cnt[min(x[j],x[j+1])+1] and cnt[max(x[j],x[j+1])] stands for.

Has someone solved D with a segment tree with bitmasks, or am I alone dumb?

F. Yet Another Substring Reverse ( with explanation )

Check out my solution for more detailed explanation : 61824886

Умные люди можете объяснить почему это так: "...нам нет смысла рассматривать такие пары xj и xj+1, что xj=xj+1...". Ответы: "Так написано в разборе" не принимаются)

what is __builtin_popcount??? i don't know it

F is beautiful problem

I have a question about pipe. In the context we could reasonably assume that the we are searching in 0th pipe and 1st pipe. If we encounter 3,4,5,6, we will make cur = !cur or cur ^= 1 The logic is simple, but when I tried to use an array of dimension 2 x n, the test 2 is always failed. Then I switched to string array dimension of 2, by the same algorithm, my answer was accepted. What is the difference?

I guess I find a counter test case you mentioned in Tutorial-1234F.

#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
using namespace std;
const int N = 1e6;
int main()
{
  std::srand(std::time(nullptr));
  int i = 0;
  for(; i < 19; ++i) {
    cout << (char)('a'+(i%19));
  }
  for(; i < N-2; ++i) {
    cout << (char)('a'+(rand()%19));
  }
  cout << "aat" << endl;
}

The answer should be 20, but may got 19 when using WA?-solution. counter test case like this

Problem A should had to be explained more clearly and easily with notes

Did Problem E, With segment tree lazy propagation Solution 88938957. For detailed explanation comment below.

I loved the question D..

D can be solved in a very straightforward way with Segment Tree and bitmasks. Each node should contain a bitmask detailing which letters are present in it's subtree. During calculation, nodes can be combined using bitwise OR, and the final result can be read with __builtin_popcount().

i solved problem F using SOS dp. it is my first problem where i used SOS dp when solveing problem randomly.