Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
def solve():
n = int(input())
s1 = input()
s2 = input()
bad = False
for i in range(n):
bad |= s1[i] == '1' and s2[i] == '1'
if bad:
print('NO')
else:
print('YES')
t = int(input())
for i in range(t):
solve()
```

Idea: fcspartakm

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
t = int(input())
for i in range(t):
n = int(input())
a = [[] for i in range(n)]
for j in range(n):
a[j] = list(map(int, input().split()))
ans = False
for j in range(5):
for k in range(5):
if k != j:
cnt1 = 0
cnt2 = 0
cntno = 0
for z in range(n):
if a[z][j] == 1:
cnt1 += 1
if a[z][k] == 1:
cnt2 += 1
if a[z][j] == 0 and a[z][k] == 0:
cntno += 1
if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:
ans = True
if ans:
print('YES')
else:
print('NO')
```

Idea: fcspartakm

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<int> a(n);
map<int, int> cnt;
for (auto &x : a) {
scanf("%d", &x);
cnt[x] += 1;
}
long long sum = accumulate(a.begin(), a.end(), 0LL);
if ((2 * sum) % n != 0) {
puts("0");
continue;
}
long long need = (2 * sum) / n;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int a1 = a[i];
int a2 = need - a1;
if (cnt.count(a2)) ans += cnt[a2];
if (a1 == a2) ans -= 1;
}
printf("%lld\n", ans / 2);
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n), ca(n + 1), cb(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
ca[a[i]]++; cb[b[i]]++;
}
long long ans = n * 1LL * (n - 1) * (n - 2) / 6;
for (int i = 0; i < n; ++i)
ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1);
cout << ans << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
vector<vector<int>> a(n, vector<int>(m, 1));
long long ans = 0;
forn(x, n) forn(y, m){
if (x == 0){
for (int k = 1;; ++k){
int nx = x + k / 2;
int ny = y + (k + 1) / 2;
if (nx == n || ny == m) break;
ans += k;
}
}
if (y == 0){
for (int k = 1;; ++k){
int nx = x + (k + 1) / 2;
int ny = y + k / 2;
if (nx == n || ny == m) break;
ans += k;
}
}
}
ans += n * m;
forn(i, q){
int x, y;
scanf("%d%d", &x, &y);
--x, --y;
forn(c, 2){
int l = 1, r = 1;
while (true){
int nx = x + (l + c) / 2;
int ny = y + (l + !c) / 2;
if (nx == n || ny == m || a[nx][ny] == 0) break;
++l;
}
while (true){
int nx = x - (r + !c) / 2;
int ny = y - (r + c) / 2;
if (nx < 0 || ny < 0 || a[nx][ny] == 0) break;
++r;
}
if (a[x][y] == 0){
ans += l * r;
}
else{
ans -= l * r;
}
}
ans += a[x][y];
a[x][y] ^= 1;
ans -= a[x][y];
printf("%lld\n", ans);
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const int N = 20;
const int M = (1 << N);
struct BracketSeqn
{
int balance;
int lowestBalance;
vector<int> queryAns;
pair<int, bool> go(int x, bool f)
{
if(f)
return make_pair(0, true);
else
return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0);
}
BracketSeqn() {};
BracketSeqn(string s)
{
vector<int> bal;
int cur = 0;
int n = s.size();
for(auto x : s)
{
if(x == '(')
cur++;
else
cur--;
bal.push_back(cur);
}
balance = bal.back();
lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
vector<vector<int>> negPos(-lowestBalance + 1);
for(int i = 0; i < n; i++)
{
if(bal[i] > 0) continue;
negPos[-bal[i]].push_back(i);
}
queryAns.resize(-lowestBalance + 1);
for(int i = 0; i < queryAns.size(); i++)
{
int lastPos = int(1e9);
if(i != -lowestBalance)
lastPos = negPos[i + 1][0];
queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin();
}
};
};
int dp[M][2];
char buf[M];
int total_bal[M];
int main()
{
int n;
scanf("%d", &n);
vector<BracketSeqn> bs;
for(int i = 0; i < n; i++)
{
scanf("%s", buf);
string s = buf;
bs.push_back(BracketSeqn(s));
}
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
if(i & (1 << j))
total_bal[i] += bs[j].balance;
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < 2; j++)
dp[i][j] = -int(1e9);
dp[0][0] = 0;
for(int i = 0; i < (1 << n); i++)
for(int f = 0; f < 2; f++)
{
if(dp[i][f] < 0) continue;
for(int k = 0; k < n; k++)
{
if(i & (1 << k)) continue;
pair<int, bool> res = bs[k].go(total_bal[i], f);
dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
}
}
printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
}
```

1598G - The Sum of Good Numbers

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD[] = { 597804841, 618557587, 998244353 };
const int N = 500 * 1000 + 13;
const int K = 3;
using hs = array<int, K>;
int add(int x, int y, int mod) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
return x;
}
int mul(int x, int y, int mod) {
return x * 1LL * y % mod;
}
hs get(const int& x) {
hs c;
forn(i, K) c[i] = x;
return c;
}
hs operator +(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = add(a[i], b[i], MOD[i]);
return c;
}
hs operator -(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = add(a[i], -b[i], MOD[i]);
return c;
}
hs operator *(const hs& a, const hs& b) {
hs c;
forn(i, K) c[i] = mul(a[i], b[i], MOD[i]);
return c;
}
int n, m;
string s, sx;
hs sum[N], pw[N];
hs get(int l, int r) {
return sum[r] - sum[l] * pw[r - l];
}
vector<int> zfunction(const string& s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r) z[i] = min(z[i - l], r - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s >> sx;
n = s.size();
m = sx.size();
pw[0] = get(1);
forn(i, N - 1) pw[i + 1] = pw[i] * get(10);
sum[0] = get(0);
forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0');
hs x = get(0);
forn(i, m) x = x * get(10) + get(sx[i] - '0');
if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) {
if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) {
cout << i + 1 << ' ' << i + m - 1 << '\n';
cout << i + m << ' ' << i + 2 * (m - 1) << '\n';
return 0;
}
}
auto z = zfunction(sx + "#" + s);
for (int i = 0; i + m <= n; ++i) {
int lcp = z[m + i + 1];
for (int len = m - lcp - 1; len <= m - lcp; ++len) {
if (len < 1) continue;
if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) {
cout << i + 1 << ' ' << i + m << '\n';
cout << i + m + 1 << ' ' << i + m + len << '\n';
return 0;
}
if (i >= len && get(i - len, i) + get(i, i + m) == x) {
cout << i - len + 1 << ' ' << i << '\n';
cout << i + 1 << ' ' << i + m << '\n';
return 0;
}
}
}
assert(false);
}
```

The easiest solution for C(in my opinion): 131432277

P.S. sum * (n-2) = (sum — a[i] — a[j]) * n => we can find for every a[i] all a[j] in O(n log n) using binary search

If you simplify that equation, you would get (a[i] + a[j]) = (2 * sum) / n, so basically this is just a 2-sum problem where the target value is (2 * sum) / n,

Yep, u r right (:

Can you please check my soln. I have used 2-sum approach but it is giving me WA on test 2. 131563369

++

I also tried the same way and getting wa on 78th in 2tc..MoonKnight. can you pls tell me why it's wa.

solution: 131653903

I havent looked at the correctness of your algorithm but

`ans = ans + c * d;`

line has int overflow for sure.XD. Thanks, for mentioning this. now, after using it long it still showing wa on that tc. Can you please tell me why is it so?

Changing

`ans = ans + c * d;`

to`ans = 1LL*ans + c * d;`

doesn't fixes anything.`ans`

is already`long long int`

. Over flow is in multiplication of`c*d`

, change this to`ans = ans + c*1LL*d`

.Also

`ll val = (n * (n - 1)) / 2;`

has int overflow. Just having`val`

of type`long long int`

doesn't do anything.`n`

and`n-1`

are still of`int`

type. Change this to`n*1LL*(n-1)/2`

.Also, next time just uses C++ 64 bit and

`long long`

everywhere.Also,

`if (st.size() == 1)`

is incorrect fix. You will still get WA onSpoilerThanks.

Got my mistake.

also you are using a unordered_map here which is giving TLE in test case 13, so better use map only . you can read this article (its quite cool)

https://codeforces.com/blog/entry/62393?#comment-464775

OR... You can use ur own hash function (:

sorry i forgot that x is a good number :-_

Video Editorial of E (Staircases)

IDk why but my solution for C gives TLE on Test 17 even though it's the exact same solution as the tester's : https://codeforces.com/contest/1598/submission/131542518

Don't know why, but using unordered_map gives TLE in this question I have the same problem... use map instead this will solve problem.

Maybe because you're using

unordered_map?Link to Another CF Blog.

Thnxx a lot!!

Yep, i fixed ur solution: 131548931

P.S. check this: https://codeforces.com/blog/entry/62393

Why using unordered_map gives TLE in this question... searching elements using hash map should be faster than the map which takes log(n) time to search instead.

131514464

Also I don't get it... how by adding just these

2 lineswhich where on a blog,`mp.reserve(1024);`

`mp.max_load_factor(0.25);`

solves the problem of TLE and my soln gets accepted.

131524838

Then I tried a

custom hashfunction rather than the built-in hash function. Which also gotaccepted. Also the same solution getsacceptedinpython using dictionarieswhich also uses hashmap.Does this mean that the C++ built-in hash function is not good ?

131520347

I tried to find but didn't get some concrete answers when to use map or unordered_map ?

Or using custom hash is better not ?

Please if anyone can help it in.

Yeah, you should use custom hash!

Fixed solution: 131549476

Check this: https://codeforces.com/blog/entry/62393

There are many hacks on unordered_map and I suppose we should avoid using it in Codeforces contests. Here a blog written by neal showing how it works.

It's just because c++'s hash function is deterministic so people can hack on this.

`max_load_factor()`

basically increase the number of buckets which will break the malicious hacks.As you mentioned that solution with python dictionary got accepted and Thallium54 suggessted in reply that c++'s hash function is deterministic, so I searched for python's and found this here, python uses a hash function which is deterministic within a single run.

Also the custom hash function which you are using in c++ solution is also deterministic within a single run.

Note to self: ALWAYS use custom hash function when dealing with unordered map no matter how unnecesary in a codeforces contest

The funny thing in this contest is sjcsjc 's template had custom_hash but still he got hacked for using c++ default hash. 131404435 After that he dropped from 4th rank to 87th rank among rated users.

I am a noob.

He is a noob.

only changes the test that's required to hack the solution, it doesn't make it unhackable.

They seemed to be difficult during the contest,but now,I think them is not really tricky.Why I have feelings like this?How can I deal with it?

Nice solution for D!

I suppose that the time complexity of F should be $$$O(n2^n + A\log A)$$$ instead of $$$O(2^n + A\log A)$$$. (:

Could someone tell me if there are some mistakes?

Can you tell me what is A in this time complexity? I understand where $$$N$$$ and $$$2^N$$$ comes from but I just can't find anything related to $$$A$$$.

You are right, it's $$$n\cdot 2^n$$$ instead of $$$2^n$$$.

Any other solution for problem D?

In Problem D, I don't understand why the only bad triples are (xa,ya),(xb,ya),(xa,by). Isn't there a possibility of having three same topics, such (1, 1), (1, 2), (1, 3)? I've been looking at the explanation for so long but still can't figure it out :(

but their difficulties are different so they aren't bad triples.

The problem statement says

"at least one of the conditions are met"Ah, now I get it. I really appreciate your reply. Thanks!!!

SpoilerThis comment was deleted because it was unnecessary

For D, can someone explain to me why there can't be a triple of the form [(Xa, Ya) , (Xb , Yb) , (Xa, Yb)] ? EDIT: I figured it out, it's actually the same thing except that the third pair is the central one, instead of the first.

Yes, correct. I had the same doubt.

For 1598C:

No, you don't have to use map in such a hacky way (or in another word, full of patches).

131572801

======================================

Instead of keeping a map of all elements, we keep a map for number of

first i items ([0, i-1])So the core logic can be much more easier:

in C#:

or in C++:

i tried to add photo for my comment but the comment become empty any one can help me

In

problem Dcan anyone please explain why we won't be overcounting in the editorial solution?Because he told you in the problem statement that the problems are distinct

problems and diff. are unique pair, no overlap when multiplication as in editorial

Regarding problem D, I have a question, and I want a simple answer The first is where the values in this equation (n — 1) * (n — 2) / 6 come from. I know it's about knowing the number of ways to choose, but I don't know where the division by six came from and why we subtracted it from one and two

You can have an overview of basic combinatorics. It is like NC3,that means you have to select any three out of N so when we apply this , it becomes N!/(3!*(N-3)!) , you can expand N! as N*(N-1)*(N-2)*(N-3)*(N-4)... and so on, you can see that (N-3)! which is in denominator will cancel the numerator from (N-3)*(N-4)*(N-5)........., and that last you will be left with (N*(N-1)*(N-2))/3! and 3!=3*2*1=6, so at last it becomes N*(N-1)*(N-2)/6.

Alternative solution for 1598D - Training Session. I did see restriction that all problems pairs of parameters are different, but I had no idea how to use this fact. My solution doesn't rely on this fact at all. Solution turned out to be much harder so I wasted a lot of time to implement it during round.

Here is main idea. Think of how to calculate all triples with different topics.

There is easy waySort all problems by their topics in non-decreasing order. You should pick three problems in strictly increasing order. Now you can group them by topics. To count all triples you can fix topic of second problem in increasing order, and count how many ways you can pick problem with this fixed topic, task with topic below, and task with topic above. All problems before the fixed group will have topic below, so their number is just zero-based index of first problem within the fixed group. All problems after the fixed group will have topic above, so their number is

nminus zero-based index of last problem within the fixed group minus one. And number of problems with the fixed topic is just length of fixed group. Multiply those and get all triples.Apply the same idea to problem's difficulties. We count something twice. What to do?

WellI don't know. I did try to think in this way, but there are too many of possible situations. So I dropped this idea. Instead, think in other way. Suppose instead we calculated all triples with different

difficulties. What are we missing after it?We missingTriples with different topics but some of difficulties coincide. I'll stress out:

topicsshoulddiffer, but difficultiescoincide.IdeaLet's forget for a moment about different topics. Focus on difficulties. Try list the cases.

Idea about which cases do we need to listBecause of different topics, we still want to use groups of fixed topic. Think of what fixed topic would be. First or second or third.

CasesI tried to fix second topic (middle one). Here is what I've got. Look at them, mark them by their property. Focus on those we should include as they wasn't yet counted.

Cases detailedI put letter v as a check mark sign of triple we do need to include.

How to count them?

Cases even more detailedNotice some of them just has same first and last difficulty. I'll put mark =

How to count other v that we still missing?

Cases even more detailed than beforeNotice we left with those which coincide first and second difficulty, I'll mark them

l, and second and third, I'll mark themr.Now we counted 2 2 2 three times, we should subtract it twice. I claim we can use this strategy to count all triples we need.

SolutionCount all triples with different difficulties using simple method described in the beginning. Then, sort problems by topics, group them by their topic. Solve for fixed topic. And within fixed topic we will iterate over problems. Let's say problem we iterate has difficulty

d. I'll list how to calc things that related to corresponding marks:lis just number of tasks with difficultydbefore the fixed group multiplied by number of problems after the group.ris just number of tasks with difficultydafter the fixed group multiplied by number of problems before group.=is sum of squares for each diffivultyvthe number of problems with difficultyvbefore the fixed group multiplied by the number of problems with difficultyvafter the fixed group.dbefore and after the fixed group.We will maintain this using associative arrays

left[d]andright[d](map in C++ or dict in Python) which will maintain how many problems with difficultydbefore and after the fixed group correspondingly. And we will maintain integerswhich will store sum of multiplication. Solwill useleft[d],rwill useright[d], and=is justs. To count 2 2 2 we just subtract twiceleft[d]multiplied byright[d]. Time complexity is $$$O(n \log n)$$$.In my code

sis namedsums.C++ 131451686

Python 131455867

Detailed description how to implement 1598E - Staircases in $$$O((n + m + q) \log (n+m))$$$ time and space.

SolutionSimilar to editorial, define base staircases. The only trick I need to describe is how easily to index all stuff. Because we will have $$$O(n+m)$$$ base staircases, and we need to be able pick the one we need to operate at that moment. Idea is to store within staircase indexes of blocked cells in

setin C++, then we can use lower_bound method to find next blocked cell or previous blocked cell when we need. Requirement for indexing is simple: we need their indices go one after another, so that length of empty cells would be next blocked cell minus previous blocked cell minus one. We don't actually have any other requirement for single staircase, because we'll use trick to initially install blocked blocks around whole table. So far as our new / old blocked cell is located between those indexes of blocked cells outside of table — we're fine.And here is neat idea to index within single staircase. Notice that no matter which base staircase we choose it will have exactly two cells on each row (not taking into account restriction to being inside of table). Let's say left one of those cell is 0, and right one is 1. Now, it's easy to see, that index of left cell $$$= row * 2$$$ and index of right cell $$$= row * 2 + 1$$$ will satisfy all our requirements. All cells within staircase will go one after another, and we have very easy formulas for left cells and right cells. You can think of it like formula for apartment numbers if there are exactly 2 apartments on each floor.

Now, we need to make indices for our base staircases. We also don't need particular starting point, all we need that they also go one after another. Notice that each base staircase can be uniquely defined by set of their left cells within rows. Also note: they form a diagonal. There is easy way to index diagonal, just $$$x - y$$$, here $$$x$$$ is row number. And this is exactly what we need.

Notice, when we block cell, in one base staircase we block left one, and in other base staircase we block right one. And the one which we block right cell is next base staircase. Next diagonal (and base staircase) would be $$$x - y + 1$$$. So, each time we block cell we can implement it as block index $$$2*x$$$ in staircase $$$x - y$$$ and block index $$$2*x + 1$$$ in staircase $$$x - y + 1$$$. You could use indices of staircases $$$x - y - 1$$$ and $$$x - y$$$ correspondingly, this only change index of starting base staircase. Blocking cell removal implemented similarly. Also, checking is there already blocking cell can be also done like this.

All we left to do is to figure out how many stairs there are initially after installing all blocking cells around the table. To do that, we can just walk over all base staircases, and find those with at least two blocking cells (there shouldn't be any with 3 or more blocking cells), and count number of staircases within as usual.

131469659

for que B https://codeforces.com/contest/1598/submission/131729850 can u check this once i don't which test i am missing so pls

if(r>=n/2&&q>=n/2&&s==0)

{

cout<<"YES"<<endl;

y=1; break;//you forget a break here

}

ok thanks bro

A slightly different solution of 1598F - RBS.

SolutionThis solution will work in $$$O(n\cdot2^n + A)$$$ where $$$A$$$ is total length of brackets sequences.

Notice, that for any fixed mask of used brackets sequences, there is fixed balance. Because balance is sum, and no matter how do you rearrange sequence, it will still have same balance in the end.

Notice, that for any prefix of used backets sequences, if there is better arrangement for this set of brackets sequence, you can change into it, and get better result. Thus any prefix should be optimal for corresponding mask.

Thus we have idea of following dp[mask] — number of RBS prefixes in best arrangement of sequences from bit mask

mask. But idea is slightly different. Let's say dp[mask] is this thingif and only ifit still potentially may have more RBS prefixes, otherwiseNonein Python or minus infinity in C++ or Python as well.In this case, any potential answer is either dp[mask] as is, or dp[mask] + single sequence of brackets after which we can't have any more RBS prefixes.

Suppose we somehow maintain total balance for mask: it could be additional dp for balance of masks, or precalc, or other approaches. Then, when we append sequence to current mask, we need to somehow find out how many times we reach 0 balance to count additional RBS and also we need to find out do we reach negative balance at any moment. To do that, it's pretty straightforward. Just precalc balance of each sequence, and minimum, and how many times it reach minimum. To count how many times we reach 0 we use number of times we reach minimum. Because, if we reach 0 when it's not minimum, then we will have negative balance and won't update dp[] because we don't store sequences which failed to continue. So when we reach 0 it should be minimum within this sequence of brackets. Also this shows us how to check does it fail for continuation.

Now, tricky part. In the way above we can get maximum over dp[mask], but there are also cases when best answer is some dp[mask] + sequence of brackets after which we won't have any additional RBS prefixes. For this case we already know what balance of mask of sequences. Let's call this balance of mask

b. We only need to know how many additional RBS prefixes we will get when we add single sequence of brackets. And, this is just how many times balance of this single sequence reach-b, because at that point mask has balanceb, so to reach 0 it should add-b. But it could fail to be RBS before reaching 0, for example, fourth time. So, we actually need to know how many times this single sequence of brackets reach balance-bbefore reaching balance which is-b-1(less by one). And this quantity we can precalculate in linear time of $$$A$$$, in other words, in linear time of total length of brackets sequences. Just make array for each sequence, and in its indexbstore how many times balance reach-bbefore reaching-b-1. Balance never grows more than length of brackets sequence, so total space of this precalculation is total length of brackets sequences $$$O(A)$$$.So, for each sequence of brackets we precalculate: how many times it reach balance

-bbefore reaching-b-1. Also, for each mask we maintain or precalculate total balance of sequence within mask. And write dp[mask] = maximum RBS prefixes for some arrangement of mask which still may have additional RBS-prefixes. Otherwise None in Python or minus infinity in C++ or Python as well. Then, answer is either maximum dp[mask] or some dp[mask] + sequence of brackets after which we won't have any additional RBS prefixes.131544153

in problem C why i am getting tle.. Pls tell[problem:1598C] https://codeforces.com/contest/1598/submission/131512968

This is due to the use of unordered_map instead of map. Try map and you will get AC.

even , i used unordered map earlier it also gave me tle but when i am using map it is not giving tle . can anyone explain why is it so ? please.

132438878 can anybody help me with this I'm getting tle even though the time complexity of my son is same as that of the solution :)

^in problem c

This may upset you, but unordered_map uses more time than normal map. Confer to this link web : https://codeforces.com/blog/entry/62393?#comment-464775

thnx man

133831334 i use python yo solve this que .. when i tested my code on my computer it gave correct ans for the given example .. but when i submit .. it says runtime error everytime . someone plz help me

My solution for F fails at test 32. Can someone please look at the submission and point out the error?

I would be happy to explain what my code does if it is not clear. Thanks.

A Dp approach to problem E in $$$O(NM + Q*min(N,M))$$$

SolutionLets calculate the number of staircases of both types at $$$cell (i,j)$$$ using Dynamic Programming

$$$L[i][j] =$$$ number of staircases starting at $$$cell (i,j)$$$ of type $$$1$$$

$$$D[i][j] =$$$ number of staircases starting at $$$cell (i,j)$$$ of type $$$2$$$

Notice that at $$$cell (i,j)$$$, all staircases of type $$$1$$$, lead to all staircases of type $$$2$$$ in $$$cell(i,j+1)$$$

Also note that at $$$cell (i,j)$$$, all staircases of type $$$2$$$, lead to all staircases of type $$$1$$$ in $$$cell(i+1,j)$$$

This leads to the recurrence formula:

$$$L[i][j] = 1+D[i][j+1], D[i][j] = 1+L[i+1][j]$$$ (if $$$cell (i,j)$$$ is free)

$$$L[i][j] = D[i][j] = 0$$$ (if $$$cell (i,j)$$$ is blocked)

The total number of staircases = sum of all $$$L[i][j]$$$ and $$$D[i][j]$$$ minus count of all free $$$1*1$$$ cells.

This is so because both types of staircases are $$$1*1$$$ squares so we have to subtract due to overcounting.

As for queries, we can just update $$$cell (i,j)$$$ to new status and recalculate all dp values but this is too slow since there are $$$N*M$$$ values to update.

You can observe that if one cell is updated, not all dp values change. The only dp values that change are the ones that can reach $$$cell (i,j)$$$ through a valid staircase of either type. The number of such cells is at most $$$min(n,m)*2$$$ for either staircase type. So all we need to do is update only those cells, which is $$$O(min(n,m))$$$ per query. To do that, we can update current cell then run a dfs from current cell to all cells that can be visited either by going up or down and update the dp values for those cells. The sum of all $$$L[i][j]$$$ and $$$D[i][j]$$$ can be stored in a sum variable and updated accordingly. The same thing can be done for the number of free cells.

Time Complexity: $$$O(NM + Q*min(N,M))$$$

code

Good job bro!

https://codeforces.com/problemset/submission/1598/141426355 Can someone help , why my code gave TLE on testcase 11 of problem C

fixed

In C, I used unordered_map and it gave me TLE in test case 19th. I tried map and it gave me AC. Can somebody explain why?

In the groups question, is it possible for the same student to attend lectures in both groups?

For problem D, is there anyway to find the number of triples that are different both in topic and in difficulty?

I am not able to get why TLE using Java in Question C,even though my Time Complexity is O(n)....152782475