Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main(args: Array<String>) {
val T = readLine()!!.toInt()
for (t in 1..T) {
val (n, x) = readLine()!!.split(' ').map { it.toLong() }
println(x * 2)
}
}
```

1194B - Yet Another Crosses Problem

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int q;
cin >> q;
forn(_, q){
int n, m;
cin >> n >> m;
vector<string> s(n);
forn(i, n)
cin >> s[i];
vector<int> cntn(n), cntm(m);
forn(i, n) forn(j, m){
cntn[i] += (s[i][j] == '.');
cntm[j] += (s[i][j] == '.');
}
int ans = n + m;
forn(i, n) forn(j, m){
ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
}
cout << ans << "\n";
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
int q;
string s, t, p;
int cnt[30];
int main() {
cin >> q;
for(int iq = 0; iq < q; ++iq){
cin >> s >> t >> p;
memset(cnt, 0, sizeof cnt);
for(auto x : p)
++cnt[x - 'a'];
bool ok = true;
int is = 0, it = 0;
while(is < s.size()){
if(it == t.size()){
ok = false;
break;
}
if(s[is] == t[it]){
++is, ++it;
continue;
}
--cnt[t[it] - 'a'];
++it;
}
while(it < t.size()){
--cnt[t[it] - 'a'];
++it;
}
if(*min_element(cnt, cnt + 30) < 0)
ok = false;
if(ok) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include <bits/stdc++.h>
using namespace std;
int n, k;
inline bool read() {
if(!(cin >> n >> k))
return false;
return true;
}
void solve() {
bool win = true;
if(k % 3 == 0) {
int np = n % (k + 1);
if(np % 3 == 0 && np != k)
win = false;
} else {
int np = n % 3;
if(np == 0)
win = false;
}
puts(win ? "Alice" : "Bob");
}
int main(){
int T; cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 10009;
const int INF = 1000000009;
int n;
vector <pair<int, int> > vs[N], hs[N];
int f[N];
vector <int> d[N];
void upd(int pos, int x){
for(; pos < N; pos |= pos + 1)
f[pos] += x;
}
int get(int pos){
int res = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
res += f[pos];
return res;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
const int D = 5000;
int main() {
cin >> n;
for(int i = 0; i < n; ++i){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 += D, y1 += D, x2 += D, y2 += D;
if(y1 == y2)
hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) );
else
vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) );
}
long long res = 0;
for(int y = 0; y < N; ++y) for(auto s : hs[y]){
for(int i = 0; i < N; ++i) d[i].clear();
memset(f, 0, sizeof f);
int l = s.first, r = s.second;
for(int x = l; x <= r; ++x) for(auto s2 : vs[x])
if(s2.first <= y && s2.second > y) {
d[s2.second].push_back(x);
upd(x, 1);
}
for(int y2 = y + 1; y2 < N; ++y2){
for(auto s2 : hs[y2]){
int cur = get(s2.first, s2.second);
res += cur * (cur - 1) / 2;
}
for(auto x : d[y2]) upd(x, -1);
}
}
cout << res << endl;
return 0;
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int MOD = int(1e9) + 7;
inline int norm(int a) {
if(a >= MOD) a -= MOD;
if(a < 0) a += MOD;
return a;
}
inline int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
inline int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a) {
return binPow(a, MOD - 2);
}
int n;
li T;
vector<li> t;
inline bool read() {
if(!(cin >> n >> T))
return false;
t.resize(n);
fore(i, 0, n)
cin >> t[i];
return true;
}
vector<int> f, inf;
int C(int n, li k) {
if(k > n || k < 0)
return 0;
return mul(f[n], mul(inf[k], inf[n - k]));
}
inline void solve() {
f.resize(n + 5);
inf.resize(n + 5);
f[0] = inf[0] = 1;
fore(i, 1, sz(f)) {
f[i] = mul(i, f[i - 1]);
inf[i] = mul(inf[i - 1], inv(i));
}
int sumC = 1;
li bd = T;
int pw2 = 1, i2 = (MOD + 1) / 2;
vector<int> p(n + 1, 0);
fore(i, 0, n) {
pw2 = mul(pw2, i2);
sumC = norm(mul(2, sumC) - C(i, bd));
li need = t[i];
if(bd > i + 1) {
li sub = min(bd - i - 1, need);
bd -= sub, need -= sub;
}
li rem = min(bd + 1, need);
fore(k, 0, rem)
sumC = norm(sumC - C(i + 1, bd - k));
bd -= rem;
p[i] = mul(sumC, pw2);
}
int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD);
cout << ans << endl;
// cerr << mul(ans, binPow(2, n)) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

Idea: Vovuh

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int n;
int numPos[10], denPos[10];
int num, den;
const int MOD = 998244353;
struct halfState
{
int carry;
int mask;
bool comp;
halfState() {};
halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {};
};
bool operator <(const halfState& x, const halfState& y)
{
if(x.carry != y.carry) return x.carry < y.carry;
if(x.mask != y.mask) return x.mask < y.mask;
return x.comp < y.comp;
}
bool operator ==(const halfState& x, const halfState& y)
{
return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp;
}
bool operator !=(const halfState& x, const halfState& y)
{
return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp;
}
halfState go(const halfState& s, int pos, int digit, bool isNum)
{
int newDigit = digit * (isNum ? num : den) + s.carry;
int newCarry = newDigit / 10;
newDigit %= 10;
int newMask = s.mask;
int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]);
if(maskPos != -1) newMask |= (1 << maskPos);
bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp);
return halfState(newCarry, newMask, newComp);
}
struct state
{
halfState numState;
halfState denState;
state() {};
state(halfState numState, halfState denState) : numState(numState), denState(denState) {};
void norm()
{
if(numState.mask & denState.mask)
numState.mask = denState.mask = 1;
};
bool valid()
{
return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0);
};
};
bool operator <(const state& x, const state& y)
{
if(x.numState != y.numState) return x.numState < y.numState;
return x.denState < y.denState;
}
state go(const state& s, int pos, int digit)
{
halfState newNum = go(s.numState, pos, digit, true);
halfState denNum = go(s.denState, pos, digit, false);
state res(newNum, denNum);
res.norm();
return res;
}
int add(int x, int y)
{
return (x + y) % MOD;
}
int ans = 0;
void calcFixed(int x, int y)
{
num = x;
den = y;
for(int i = 0; i <= 9; i++)
numPos[i] = denPos[i] = -1;
int cnt = 0;
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
if(i * y == j * x)
{
numPos[i] = denPos[j] = cnt++;
}
vector<map<state, int> > dp(102);
dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1;
for(int i = 0; i <= 100; i++)
for(auto x : dp[i])
{
state curState = x.first;
int curCount = x.second;
for(int j = 0; j <= 9; j++)
{
state newState = go(curState, i, j);
dp[i + 1][newState] = add(dp[i + 1][newState], curCount);
}
}
for(auto x : dp[101])
{
state curState = x.first;
int curCount = x.second;
if(curState.valid())
ans = add(ans, curCount);
}
}
int main()
{
string s;
cin >> s;
int len = s.size();
reverse(s.begin(), s.end());
for(int i = 0; i < len; i++)
{
a[i] = s[i] - '0';
}
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
if(__gcd(i, j) == 1)
calcFixed(i, j);
cout << ans << endl;
}
```

Why does it say tutorial for E is unavailable. Was it not posted yet or is it just me?

It's available now

Thanks

Could anyone provide some classic mathematical resources for question Like D.Rather than by using generalized test cases,and finding cases.how to solve it mathematically.I was thinking of matrix exponentiation but I guess it would not work as we cannot represent Logical-OR operation mathematically.Please provide some Generalised solution for set{$$$a_1$$$,$$$a_2$$$..$$$a_n$$$}. Thank you any kind of help will be appreciated.

For game theory problems it is always better to write a program that generates the solution for a very small instance of the game. For example

My GeneratorIt prints the game state for random values of K for n<=20, after running this gen a couple of times, you'll get the pattern easily.

How u write the generator what is the idea behind it

That's kind of a secret ;)

After you know the pattern it usually is pretty easy to prove it. Particularly, you only need to prove it for the first two iterations of the period of the pattern (in this case of period k+1) since as you can only move at most k, then if the whole k+1 earlier elements of an element are the same as another one in the winning/losing table are the same, then both elements will have the same winning/losing position value.

Another solution for F:

Iterate over the number $$$m$$$ of crosswords that will be solved completely, and iterate over all feasible values $$$k$$$ for the number of crosswords that took one second longer. Then add

To the answer. This is trivially $O(n^2)$, but it's actually linear: If $$$s_i = t_1 + t_2 + \dots + t_i$$$ then the pair $$$(m, k)$$$ is only feasible if $$$s_m + k \le T \le s_{m + 1} + k$$$. If the first doesn't hold we don't have enough time to solve $$$m$$$ and if the second doesn't hold then we have enough time to solve $$$m + 1$$$.

So for each fixed $$$m$$$ we only consider $$$k$$$ in the interval $$$[T - s_{m + 1}, T - s_m]$$$, and because $$$s_i$$$ is strictly increasing this means that we will consider a certain $$$k$$$ for at most two values of $$$m$$$. There are $$$O(n)$$$ possible values of $$$k$$$ so we'll consider only $$$O(n)$$$ pairs $$$(m,k)$$$

One small detail: If $$$s_{m + 1} + k$$$ is equal to $$$T$$$ then we must divide the value for the pair $$$(m, k)$$$ by two, because we have to take one second longer on the $$$(m + 1)$$$-st crossword to not solve it.

how to compute m choose k in constant time?

Just pre compute the factorials and inverse factorials

thanks! i feel like an idiot for not noticing that

Precompute $$$x!$$$ and $$$\frac{1}{x!}$$$ $$$\bmod{10^9 + 7}$$$ for $$$x$$$ from $$$1$$$ to $$$n$$$ in linear time and use $$$\binom{m}{k} = \frac{m!}{m! (m - k)!}$$$

In editorial for F ,why is $$$P(i)$$$ not multipiled with i (=m ,as in your solution) , and why the sum starts from k=0 to k = m_i , it should not be from 0 .Please help.

Hello!

P(i) in the editorial is the probability that we solve ith crosswords completely (not the prob. that we solve i crosswords completely).

Hope this helps :)

In C For this test case ab acxb cax ab is not a substring of acxb. Then how the logic is correct. Someone please explain.

Small mistake in the editorial, it should be a subsequence rather than a substring

Can anybody pls tell for which input my code is giving WA?? https://codeforces.com/contest/1194/submission/57146778

The substring doesn't need to be consecutive letters

The first game problem I came across! Thanks for great problems and solutions ^^

As a nice soluton to E I would like to introduce you this Solution. This one works in $$$O(n^3)$$$ using bitsets, and solves a more general problem — find the number of cycles of length $$$4$$$ in a graph, which has $$$O(n)$$$ vertices and $$$O(n^2)$$$ edges. It gets AC due to a very low constant factor and works in just 300ms.

I was wrong.

NVM, I just used bipartite property to lower the constant of the solution.

Hi, could you please explain how come the O(n3) solution worked without getting TLE?

As I wrote it has a very low constant factor. First of all bitset gives us a speed up to 64 times. Also my solution is optimized so that the constant goes down by 8 times more (just some simple facts, like there are only $$$n(n-1)/2$$$ ordered pairs). This gives us a speed up to 512 times, and so we get that $$$\log_2 5000 \approx 13$$$ is actually more than $$$5000/512 \approx 10$$$. So with such limitations ($$$n \leqslant 5000$$$), $$$n^2log \geqslant n^3/512$$$.

Thanks.

appreciate the explanation, was also confused about not getting TLE.

bitset is magic.

Does your solution work without the pragmas?

Pragmas give a big boost, but i have a solution which AC without them. This solution uses hand made bitsets. But without #pragma GCC target("avx2") it passes in approximately 600ms. This pragma gives a boost up to 4 times, and I have a solution which passes in just 150ms.

Can someone please elaborate the explanation for problem B "Yet Another Crosses Problem"?

For every cross we can make, we must colour all the white cells in i-th row and j-th column. So, we can precalculate the number of black cells in each row and in each column. Let cntr[i] be the number of black cells in the i-th row and cntc[j] be the number of black cells in the j-th column. Now, we can only go through all the cells and check the number of cells we must colour if the chosen cell is the centre of our cross. Let the chosen cell be in i-th row and j-th column of the matrix. We can do it in O(1) time, like

(n-cntr[i])+(m-cntc[j])-(matrix[i][j]=='.'). Why this -(matrix[i][j]=='.')? Because if matrix[i][j]=='.', it was counted two times(in cntr[i] and in cntc[j]) , instead of one. Among the all possible answers, we need one with the smallest number of colouring cells. Finally, our time complexity isO(Q*NM).WoW brilliant man thanks for the beautiful explanation really appreciated.

Is there any general approach to tackle game theory problems such as D ? What approach do you use to solve problems like these?

I just painted in the paper situations(winning or losing positions) for different k and noticed regularity

Upto what sample size did you do this?

I think upto 5 and dividers of 3 (6, 9) were enough

If n would have been small the problem could have been easily solved by linear regression in O(n) instead of finding a pattern. Just maintain a boolean array arr to donate winning or losing at that index.

`arr[0] = false i.e. loose`

`arr[1]=true`

`arr[2]=true`

just output arr[n] now.

Call a game state 'losing' if first player loses if game starts from it, 'winning' otherwise. Game state without any possible moves is obviously 'losing'. You can then analyze a game with any fixed k manually on a paper: go through positions (length of the line in our case) and look at possible moves from it (if there is a move to a losing state, our is winning, otherwise, our is losing). This is a typical way to analyze determined games.

Doing that, you will notice, that without k-move, sequence of winning/losing states is like that: LWWLWWLWW... K-move, though, sometimes prevents state from being losing by providing one more move. So, easy to see, if k is not divided by 3, it changes nothing. If it is divided by 3, you can analyze how k-move changes the structure.

Isn't the complexity of solution given for E O(n3)?

Nope n*logn

Because you running around 5000 segments and for every one you make some operation that have complexity logn(n ~= 10000) -> result complexity n * logn

P.s. Correct me if I'm wrong(Yeap, I wrong)

I feel like its

`O((N^2)logN)`

because for each horizontal segment at height`y`

, you iterate over all the horizontal segments at a height greater than`y`

which is`N^2`

and a factor of`logN`

for using Fenwick tree query during every iteration.does anyone know a good source for game theory or how to be better at it

If by a good source you mean reading material then you can read it from here and here. I feel like there is not much to read. If you are looking for more questions (you can become better by solving them) then you can refer to this blog (you can find questions on other topics as well in this blog).

Good luck! I hope this helps :)

THANK YOU

Can someone explain the time complexity analysis of problem E editorial solution ?

The complexity is

`O((N^2)logN)`

, let's analyze it using the solution mentioned in the blog. We iterate from`y=0`

to`y=N-1`

and for each`y`

we iterate all the horizontal line at height`y`

, note that if the solution consisted of only these two loops then the complexity would have been`O(N)`

and not`O(N^2)`

because these two loops only iterate total number of horizontal lines which has an order of`N`

. Inside these loops, we find a loop that iterates from x-coordinate from`x=l`

to`x=r`

and for each`x`

we iterate all the vertical line having x-coordinate from`x=l`

to`x=r`

which has an order of`N`

and hence these two loops run in`O(N)`

, so complexity up to this step is`O(N^2)`

, one factor of`N`

for the outer two loops and another for the inner two loops. Now we come across a loop which runs from`y2=y+1`

to`y2=N`

and for each`y2`

we iterate all the horizontal lines at height`y2`

using similar logic used above these two loops run in the complexity of`O(N)`

but inside these loops, we use the query of Fenwick tree which consumes`O(logN)`

time hence the complexity of these two loops become`O(NlogN)`

, therefore the overall complexity is`O((N^2)(1+logN))`

which is`O((N^2)logN)`

.I hope this helps :)

Instead of

"Now we come across a loop which runs from y2=y+1 to y2=N and for each y2 we iterate all the horizontal lines at height y2 using (...)"

it should be

"Now we come across a loop which runs from y2=y+1 to y2=N and for each y2 we iterate all the horizontal lines at height y2 and all the vertical segments with their top end at height y2 using (...)".

What is learned is- In game theory questions like this after determining the base conditions what you need to is based on previously computed results, you need to make the current player move such that in next chance other player reaches in such position where if the current player was there it would have loosed. If no such position is possible then current cannot win.

Is that right?

Can someone please explain the second condition for a good vertical segment in problem E?

Well, it says that the vertical segment has its smaller y-coordinate below or at the same level as the y-coordinate of the horizontal segment. If we know that it also intersects a horizontal segment above our fixed horizontal segment, than we know that it intersects the fixed horizontal segment.

Can someone explain me why if $$$n = 3$$$ and $$$k = 4$$$ the winner is Bob? There are 3 cells between position of chip and 0-pos, so why Alice can't win?

Nobody can go below zero. And the rule is you can only take 1 or 2 or

exactlyK.It is

Nottake 1, or 2, or any number up to K.If n=3 and k=4

Alice can't take 4, she can only take 1 or 2, leaving either 1 or 2 for Bob.

Bob now can always take 1 or 2 either way Alice leaves it, therefore Bob always wins on his first turn.

thank you, got it.

Small solution for problem 1194C - From S To T ---> 57160243

Problem G: Can someone give intuition for $$$mask$$$ in dp's state? What does it mean?

If we want to check $$$\frac{1}{2}$$$ we check both $$$\frac{1}{2}, \frac{2}{4}, \frac{3}{6}, \frac{4}{8}$$$

and the respective mask would be $$$1«0, 1«1, 1«2, 1«3$$$

see how to init

numPosanddenPosin the author's code.Can anybody pls tell for which input my code is giving WA?? https://codeforces.com/contest/1194/submission/57146778

Can anyone explain the editorial in simpler words for E? Why are we decrementing x in tree? Thank You.

Because we are going from bottom to top with respect to the y coordinate and a vertical segment has just ended--i.e. we are at its top coordinate--so we remove it from our container because it won't intersect any of the following horizontal segments.

In the editorial of D, it is given that "the game is symmetric". What does it mean that the game is symmetric and how do we know that it is symmetric?

If a cell is winning 4 Alice, it's also winning 4 Bob.

did anybody solved D using DP ??

It would have been easier with DP if the constraints were not so large. At least I think so...

Hmm I too think the same

What is the maximum number of statement executions that will get accepted?

Like for problem B -> Time complexity is n*m per query -> Total time complexity = q*n*m.

q*n*m = (5 * 10 ^ 4) * (4 * 10 ^ 5) = 2 * 10^10 approximately.

Will this get accepted?

Other than constraints on n and m individually, it is also mentioned(in the problem constraints) that sum of (n*m) over all test cases is <=4e5. So it'll be fine.

I can not understand the 4 no solution. can anyone elaborate if you got the time? thanks in advance.

In Question-D, I am not able to understand why position 2k is winning (if k is multiple of 3)?

For a position to be winning, you must be able to go to atleast one losing position right?

Now, 2k-1 and 2k-2 are winning (since all positions not multiple of 3 are winning) and position k is also winning (as you can go to 0) so how is position 2k-1 winning as you can only go to these 3 mentioned positions-->2k-1, 2k-2 and k?

Also, the numbering is from — 0,1,2,3...k,k+1,k+2...2k,2k+1,2k+2... so, If I split it into cycles of k+1, then I will get:

0,1,2,3...k | k+1,k+2,k+3,..2k+1 | 2k+2, 2k+3,... There is not uniformity since the first element is increasing by 1. How are we using the cycle of length k+1?

Thank You