Идея: adedalic
Разбор
Tutorial is loading...
Решение (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 - Очередная задача про кресты
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (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;
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (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;
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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;
}
1194E - Посчитайте четырехугольники
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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;
}
1194F - Эксперт по кроссвордам
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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;
}
1194G - Очередная мемная задача
Идея: vovuh
Разбор
Tutorial is loading...
Решение (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
It 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
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 is O(Q*NM).
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 heighty
, you iterate over all the horizontal segments at a height greater thany
which isN^2
and a factor oflogN
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 fromy=0
toy=N-1
and for eachy
we iterate all the horizontal line at heighty
, note that if the solution consisted of only these two loops then the complexity would have beenO(N)
and notO(N^2)
because these two loops only iterate total number of horizontal lines which has an order ofN
. Inside these loops, we find a loop that iterates from x-coordinate fromx=l
tox=r
and for eachx
we iterate all the vertical line having x-coordinate fromx=l
tox=r
which has an order ofN
and hence these two loops run inO(N)
, so complexity up to this step isO(N^2)
, one factor ofN
for the outer two loops and another for the inner two loops. Now we come across a loop which runs fromy2=y+1
toy2=N
and for eachy2
we iterate all the horizontal lines at heighty2
using similar logic used above these two loops run in the complexity ofO(N)
but inside these loops, we use the query of Fenwick tree which consumesO(logN)
time hence the complexity of these two loops becomeO(NlogN)
, therefore the overall complexity isO((N^2)(1+logN))
which isO((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 exactly K.
It is Not take 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.
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 numPos and denPos in the author's code.
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...
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.
My solution uses dp having "only" 4 dimensions. Firstly we can assume x <= y and keep track only of whether $$$ay \leq n$$$ because if it is, then $$$ax \leq n$$$ as well. Second instead of keeping track of which interesting digits were used we will pass extra parameters to function calculating dp denoting digits allowed to appear in $$$ax$$$ and $$$ay$$$ respectively. To extract the answer from this modified dp we will use inclusion exclusion principle. Let $$$U$$$ denote set of all fractions in valid range $$$X_i$$$ denote set of fractions whose nominator contains digit $$$i$$$ and $$$Y_i$$$ set of fractions whose denominator contains digit $$$i$$$.
Suppose $$$x = 1, y = 2$$$ We are interested in $$$(X_1\cap Y_2)\cup(X_2\cap Y_4)\cup(X_3\cap Y_6)\cup(X_4\cap Y_8)$$$.
Using inclusion-exclusion principle we can expand its cardinality to: $$$|X_1\cap Y_2| + |X_2\cap Y_4| + |X_3\cap Y_6| + |X_4\cap Y_8| - |X_1\cap Y_2 \cap X_2\cap Y_4| - \ldots - |X_1\cap Y_2 \cap X_2\cap Y_4 \cap X_3\cap Y_6 \cap X_4\cap Y_8|$$$
Let's see how we can calculate on particular set: $$$|X_1\cap Y_2 \cap X_2\cap Y_4| = |U| - |\overline{X_1}\cup\overline{Y_2}\cup\overline{X_2}\cup\overline{Y_4}|$$$, and again use inclusion-exclusion principle since intersection of some of those sets is exactly set of fractions not containing any of given digits, which we can calculate using our DP. At first it seems we will call this function lots of times, but first we can improve it in other way. First for each set of forbidden digits in numerator and denominator calculate sum of coefficients with which the result of this dp will be added to the answer and run the function only if it is nonzero. It turns out this sum is: $$$1$$$ if both forbidden sets are empty, $$$(-1)^\text{number of forbidden digits + number of pairs}$$$ if from each pair at least one digit is forbidden, and $$$0$$$ otherwise, which means we will run dp only $$$1 + 3^{4}$$$ (or in general $$$1 + 3^k$$$ where $$$k$$$ is number of pairs) times.
62745786
E solution using pbds 91306062