Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for _ in range(int(input())):
l, r = map(int, input().split())
print(min(l, r, (l + r) // 3))
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for _ in range(int(input())):
n, x, m = map(int, input().split())
l, r = x, x
for _ in range(m):
L, R = map(int, input().split())
if max(l, L) <= min(r, R):
l = min(l, L)
r = max(r, R)
print(r - l + 1)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int> > a(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
vector<vector<int> > cnt(n + m - 1, vector<int>(2));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cnt[i + j][a[i][j]]++;
int ans = 0;
for(int i = 0; i <= n + m - 2; i++)
{
int j = n + m - 2 - i;
if(i <= j) continue;
ans += min(cnt[i][0] + cnt[j][0], cnt[i][1] + cnt[j][1]);
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() }
val minDiv = IntArray(1e7.toInt() + 2) { it }
for (i in 2 until minDiv.size) {
if (minDiv[i] != i)
continue
for (j in i until minDiv.size step i)
minDiv[j] = minOf(minDiv[j], i)
}
fun getPrimeDivisors(v: Int): ArrayList<Int> {
val ans = ArrayList<Int>()
var curVal = v
while (curVal != 1) {
if (ans.isEmpty() || ans.last() != minDiv[curVal])
ans.add(minDiv[curVal])
curVal /= minDiv[curVal]
}
return ans
}
val d1 = IntArray(n)
val d2 = IntArray(n)
for (id in a.indices) {
val list = getPrimeDivisors(a[id])
if (list.size < 2) {
d1[id] = -1
d2[id] = -1
} else {
d1[id] = list[0]
list.removeAt(0)
d2[id] = list.reduce { s, t -> s * t }
}
}
println(d1.joinToString(" "))
println(d2.joinToString(" "))
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int MOD = 998244353;
int mul(int a, int b) {
return (a * 1LL * b) % MOD;
}
int n, m;
int a[N], b[N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int i = 0; i < m; ++i) scanf("%d", b + i);
reverse(a, a + n);
reverse(b, b + m);
a[n] = -1;
int mn = a[0];
int pos = 0;
while (pos < n && mn > b[0]) {
++pos;
mn = min(mn, a[pos]);
}
if (pos == n || mn < b[0]) {
puts("0");
return 0;
}
assert(mn == b[0]);
int res = 1;
int ib = 0;
while (true) {
assert(mn == b[ib]);
if (ib == m - 1){
if(*min_element(a + pos, a + n) != b[ib]) {
puts("0");
return 0;
}
break;
}
bool f = true;
int npos = pos;
while (npos < n && mn != b[ib + 1]) {
++npos;
mn = min(mn, a[npos]);
if (f && mn < b[ib]){
f = false;
res = mul(res, npos - pos);
}
}
if (npos == n || mn != b[ib + 1]) {
puts("0");
return 0;
}
++ib;
pos = npos;
}
printf("%d\n", res);
return 0;
}
```

Idea: Neon

**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;
const long long INF = 1e18;
const int MOD = 1000'000'007;
const int inv2 = (MOD + 1) / 2;
struct edge{
int v, u, w;
};
struct frac{
long long x, y;
frac(long long a, long long b){
if (b < 0) a = -a, b = -b;
x = a, y = b;
}
};
bool operator <=(const frac &a, const frac &b){
return a.x * b.y <= a.y * b.x;
}
struct line{
long long m, c;
frac intersectX(const line &l) { return frac(c - l.c, l.m - m); }
};
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int calc(int a1, int d, int n){
assert(n >= 0);
return mul(mul(n, inv2), add(mul(2, a1), mul(add(n, -1), d)));
}
int main() {
int n, m;
long long q;
scanf("%d%d%lld", &n, &m, &q);
vector<edge> e(m);
vector<int> hv(n);
forn(i, m){
scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
--e[i].v, --e[i].u;
hv[e[i].v] = max(hv[e[i].v], e[i].w);
hv[e[i].u] = max(hv[e[i].u], e[i].w);
}
int ans = 0;
vector<long long> d(n, -INF), nd(n);
d[0] = 0;
forn(val, m){
long long mx = 0;
forn(i, n)
mx = max(mx, d[i]);
if (val)
ans = add(ans, mx % MOD);
nd = d;
forn(i, m){
nd[e[i].v] = max(nd[e[i].v], d[e[i].u] + e[i].w);
nd[e[i].u] = max(nd[e[i].u], d[e[i].v] + e[i].w);
}
d = nd;
}
vector<line> fin;
forn(i, n) fin.push_back({hv[i], d[i]});
sort(fin.begin(), fin.end(), [](const line &a, const line &b){
if (a.m != b.m)
return a.m < b.m;
return a.c > b.c;
});
fin.resize(unique(fin.begin(), fin.end(), [](const line &a, const line &b){
return a.m == b.m;
}) - fin.begin());
vector<line> ch;
for (auto cur : fin){
while (ch.size() >= 2 && cur.intersectX(ch.back()) <= ch.back().intersectX(ch[int(ch.size()) - 2]))
ch.pop_back();
ch.push_back(cur);
}
long long prv = 0;
q -= m;
forn(i, int(ch.size()) - 1){
frac f = ch[i].intersectX(ch[i + 1]);
if (f.x < 0) continue;
long long lst = min(q, f.x / f.y);
if (lst < prv) continue;
ans = add(ans, calc((ch[i].c + ch[i].m * prv) % MOD, ch[i].m % MOD, lst - prv + 1));
prv = lst + 1;
}
ans = add(ans, calc((ch.back().c + ch.back().m * prv) % MOD, ch.back().m % MOD, q - prv + 1));
printf("%d\n", ans);
return 0;
}
```

Idea: Neon

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
const int INF = 1e9;
const int N = 10010;
int n, m;
string s, t;
int dp[N][N];
int nxt[N];
int main() {
cin >> s >> t;
n = sz(s), m = sz(t);
forn(i, n) if (s[i] != '.') {
int bal = 0;
nxt[i] = -1;
fore(j, i, n) {
if (s[j] == '.') --bal;
else ++bal;
if (bal == 0) {
nxt[i] = j;
break;
}
}
}
forn(i, n + 1) forn(j, m + 1)
dp[i][j] = INF;
dp[0][0] = 0;
forn(i, n) forn(j, m + 1) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
if (j < m && s[i] == t[j])
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
if (s[i] != '.' && nxt[i] != -1)
dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]);
}
cout << dp[n][m] << endl;
}
```

I realized in hacking phase that for E I accidentally read in $$$a$$$ and $$$b$$$ both with lengths $$$n$$$ (see my 83457987).

I thought I would segfault in system testing but I was still accepted. Can someone explain from first principles why this is? I guess it's ok to cin out of bounds as long as you don't use the memory afterwards?

getting tle on case 46 for E on this......Can anyone tell why? upd: solved

Hey awoo there is some problem with font of code of f because of comma in mod

and e too

Fixed both, thanks

Can some one please explain me how to do the Linear Integer programming, here in Problem A, they are checking just the corner points of the graph drawn & deciding on the answer,and yes it is quite true when x1,x2 are real numbers, but here the constraint is x1,x2 are integers>=0, so how to approach this problem. please help me with the proof.

Video Tutorial for Problem A,B,C,D

In problem B, would you please tell me elaborately that what does it mean ak=1 in the end.

why it cannot be greater than (a+b)/3 in problem A.

this comment is deleted because of negative feed back

Just for simple realisation :

We need three objects in total to make anything(2 of first and 1 of second kind and vice versa). Now if each object need 3 material then you can create at max (a+b)/3 objects

got it now :)

In Problem A, With 8 diamonds and 7 sticks, I can only earn four emeralds. Why is the expected answer 5?

8 diamonds + 4 sticks = 4 emeralds (zero diamonds left, 3 sticks left) OR

6 sticks + 3 diamonds and 2 diamonds + 1 stick = 4 emeralds (3 diamonds left, 0 sticks left)

I asked this as a separate comment but moving it here for visibility.

You can make 3 swords by 6 diamonds + 3 sticks. After that, there are 2 diamonds and 4 sticks left for 2 shovels => 5 emeralds

Notice that we the answer actually asks how many times we can subtract 3 from (a+b). Obviously the answer is

`(a+b)/3`

. But for some restriction on the type of objects we had to go for`min(a,b,(a+b)/3)`

. There is another way. Suppose we take`X`

diamonds and`2X`

sticks to build`X`

shovel. And we take`Y`

sticks and`2Y`

diamonds to build`Y`

sword.`Total number of used items = 2X + X + 2Y +Y = 3X +3Y`

. So,`(a+b) - (3X+3Y) = 0`

, why right hand side = 0 ? Because if we want to maximize the answer, number of items left will be zero. Solving for`X+Y`

gives`(a+b)/3`

.This can be added to editorial itself.

lets assume we will be able to make x shovels and y swords. 1. 2*x+y<=a 2. x+2*y<=b

adding above equations we will get 3x+3y<=(a+b)

hence (x+y)<=(a+b)/3

thank you for the proof

Ah, finally the editorial is out now.

We can do D in this way too -

1 ) Make prime sieve (sieve of Eratosthenes) to check a no. is prime or not

2 ) Convert given array to set

3 ) Now if a value in set is prime then store (-1,-1) else do brute force to check each valid pair of the divisor.

It passes better than SPF algo (in my case)

Here is link : My_Solution

btw the algo is good ..btt your submission is completely messyy !

Nice approach to avoid duplicate numbers. For most numbers brute force works fast enough. Or may be test cases are weak. But I am not sure because some sophisticate time complexity analysis is needed.

can i get solution for problem D in c++??

You can refer this 83534816

hey i like your solution. its nice

I you click the contest page you see these numbers right of the problems. Clicking them will show you a list of that problems submissions.

This could be A-hard version :) 478-C Table decorations

Hey awoo, I enjoyed the contest, interesting questions! I was wondering why you chose to put F and G in this contest: aren't they better suited for a div 1?

Bro, this round is called an "Educational Round" right? So it seems reasonable that there will be some problems with advanced techniques at the high end of the problemset.

getting tle on case 46 for E on this......Can anyone tell why?

AbhishekAg your solution uses an unordered map, change it to an ordered map (normal map) and it will pass. Check this : https://codeforces.com/blog/entry/62393

One more thing I must say is that I have observed you have commented the same thing you commented here atleast 3 times as an sudden, out of nowhere reply to various comment threads here, such spamming is really inappropriate and irritating! Create a new comment if you need to.

Please don't do this.

Sorry for spamming, I thought I could delete all comments once I get a reply......but it seems that cannot be done.....I keep it in mind from next time... Also.....can you please explain why changing to map got accepted?

Check the link I shared, its basic idea is that on average unordered map has O(1) operations, which is OK if inputs are random, but it turns out, if someone wants, they can generate an adversarial test case to cause an O(n^2) blowup on it.

thanks...

Alternative for D, My solution for D is little bit different https://codeforces.com/contest/1366/submission/83482692 It uses the observation that if (d1 and d2) solution exist for a number A such that gcd(d1+d2,A) =1.Then it will definitely exist in the form of d1 = x, d2 = A/x where x is some divisor of number A.

bt how is it happening?? cant ovserb this.can u help me observing this?? thanks in advance.

i came up with same thing but can't prove

Construction for A: let $$$K = \min(A, B, \frac{A + B}{3})$$$. Each of the $$$K$$$ items crafted needs at least one stick and at least one diamond. Set those sticks and diamonds aside; it's possible since $$$K \leq A$$$ and $$$K \leq B$$$. Each item then needs one additional resource of either type. We have $$$A + B - 2K$$$ resources remaining. It follows from $$$K \leq \frac{A+B}{3}$$$ that $$$A + B - 2K \geq K$$$.

getting tle on case 46 for E on this......Can anyone tell why? upd : solved

Can someone explain the time complexity of Problem D?

Let

Abe max Number which is 10^{7}andnis size of array -To precompute SPF (smallest prime factor ) Time complexity is O(AloglogA)

Now for each value we can answer in O(logA)

As there are n values => O(nlogA)

Total = AloglogA + nlogA

How is the complexity of SPF nloglogn ?

Complexity of sieve of eratosthenes is

`O(nloglogn)`

You can solve Problem D in O(n+A).

This code spend 389ms to solve Problem D without any fast I/O.

To precompute some number's smallest prime factor, using The sieve of Euler, time complexity is O(A).

But it is not necessary to divided by smallest prime factor one by one, which using O(log(A)).

You can precompute number

xhas how many smallest prime factor at the same time.put your code in spoiler or provide link.

Can u please explain how the complexity of your sieve ( which is euler sieve ,I don't know about this please if some tutorial then give ) is O(A) ?

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler's_sieve

Can anybody explain a little on why are we traversing the arrays in reverse order helps?

Video Explanation for D Two Divisors

Proof for A:

It is evident, as the tutorial mentions, that it cannot be greater than min(A,B,(A+B)/3), as you said. This does not imply that we can always achieve one of these optimal cases! For the first two, it's easy to see that if A>2*B, then it is optimal to pair each B with 2 A's and we have A's to spare. WLOG for B>2*A.

For the other case, we can take 2 of the one with greater quantity and pair it with 1 of lesser quantity. It is easily observed that this will reduce max(A,B) by 1 more than it reduces min(A,B), so we will always be bringing the values A and B closer together, except when they are equal, in that case we create a difference of one. By the above two observations, this process ends either when one of the piles are 0, in which case the other must be 1, or when both piles are 1. This corresponds to cases (A+B)%3=1 and (A+B)%3=2 respectively.

Hence we complete the proof that not only is the optimal less than the 3 constraints, but there exists a way to achieve these 3 constraints.

liked the problems a lot, thank u!

Please help! In C, why do we check if i <= j?

For Problem D U can refer This :

As we have to find the smallest prime factor (for each number a[i]) first & then we need to check is there another prime factor is present or not So how we will do that ??

U just keep dividing by the spf !

You can refer this solution 83571466

Happy To help !Let's say the count array is of length 7, odd length

Now what we equate b/w is:

Notice that, equating between cnt[3] and cnt[3]

case (i == j)i.e, when both pointers meet at mid is unnecessary and so is, any index > 3case (i > j)as we will be repeating the process(think).Case (i == j) won't happen for even length count array.

Thanks for your explanation! I got it now :)

Can anyone help me find the complexity of my solution https://codeforces.com/contest/1366/submission/83570373

it's

Nlog(log(N))where N = mx (in your code).Please someone explain problem B.

https://codeforces.com/blog/entry/78735?#comment-642117

Can anyone explain the proof of how to choose

d1andd2effectively inProblem D? The editorial version is not that clear to me.Simple Approach

For an $$$even$$$ number, answer will be $$$($$$ $$$2$$$, Product of remaining odd prime factors $$$)$$$

For an $$$odd$$$ number, answer will be $$$($$$ $$$1st$$$ Smallest prime factor, $$$2nd$$$ Smallest Prime factor $$$)$$$

And obviously, first, you need to check whether alteast $$$2$$$ distinct prime factors for a number exists or not. if not answer will be $$$($$$ $$$-1$$$, $$$-1$$$ $$$)$$$

ProofFor an $$$odd$$$ number,

Consider an example $$$ai$$$ = $$$105$$$ $$$( 3 * 5 * 7 )$$$. Ans is $$$(3, 5)$$$.

$$$3$$$ is $$$1st$$$ smallest prime factor and $$$5$$$ is $$$2nd$$$ smallest prime factor of $$$105$$$.

Let $$$x = d1 + d2 = 3 + 5 = 8$$$.

$$$g = gcd(x, 105)$$$ and obviously $$$g$$$ can't be $$$3$$$ or $$$5$$$. So $$$g$$$ should be greater than $$$5$$$, which is not possible. (why? Let $$$x' = g * e$$$ , $$$e$$$ is even number, $$$e$$$ must be aleast $$$2$$$. You can see $$$x' > x$$$ if $$$g > 5$$$, which is not possible.So $$$g$$$ has to be $$$1$$$.

For an $$$even$$$ number,

Consider an example $$$ai$$$ = $$$210$$$ $$$( 2 * 3 * 5 * 7 )$$$. Ans is $$$(2, 105)$$$.

$$$105 = 3 * 5 * 7$$$ (Product of remaining odd prime factors).

You can see $$$d1 = 2$$$ and $$$d2 = 105$$$, now forget about $$$d1$$$ and ask a question from yourself. What is the minimum $$$y$$$, I should add to $$$d2$$$ such that $$$g = gcd(d2 + y, ai) > 1$$$. And you will find you need to add smallest prime odd factor, for this case it is $$$3$$$ but we are adding just $$$2$$$ ($$$d1 = 2$$$, hence the answer).

For the code for problem G proiveded in the editorial, can anyone please explain why the following transition is skipped:-

`dp[i+1][j-1]=max(dp[i+1][j-1],dp[i][j])`

, where the ith character of the first string is a`'.'`

.I am not able to convince myself why this transition is redundant.

Yeah, so the transition look like this:

TAKE character because it will be in *final string

DONT TAKE character because it won't be in *final string, delete it

DONT TAKE character because it won't be in *final string, but we must destroy it with some character '.'

*final string I am talk about is string t we should get from s after applying function f.

The transition you are talking about cannot ever happen, because if we took some character with transition 1. , by definition it will be in final string so it shouldn't be destroyed.

A : 519C - A and B and Team Training

Once again problem A took more than 30 minutes to solve. Lol... but the solution was of one line

Anyone please help me to figure out why I am getting TLE on test case 47 , in problem E.Please help me. https://codeforces.com/contest/1366/submission/83590296

Try map instead of unordered_map.

But unordered_map is faster than map?

No , unordered_map will take linear time in worst case.

for more details refer this

Ohk, I got that , can you tell me when unordered_map gives us answer in O(1) with surety , and when it can take linear time?

Sorry but I don't know that much deep.

How, would i know where to use map or where to use unordered_map?

Times you need to pay to insert or read in map is O(logn),while on unorederd_map maybe O(1) in average but in O(n) in some test data. So if you are sure that time for you is enough to use map, just use it.

The principle of unordered_map is hash. Maybe you need to learn about this, for the random test data it cost O(1) to insert, but sometimes it will cost O(n) to insert.

Yes,I know about hashing and collisions but it was also taught that inbuilt hash function is very good and chances of getting O(n) complexity in unordered_map is very less , how would I identify by looking the constraints in the question that unordered_map will give linear time in this case?Plz help

You can write hash by yourself and get the module randlomly because the moudle in unordered_map is a const number (I guess), and in C++ you may write "int mod=rand()" or in any other ways. In this way you may make sure that the cost is O(1) because the test data don't know what you moudle is because it's created randomly. But if it is possible I think you'd better use map because it is more convenient.

Ohk,thanks for your help:)

In problem F, it is given that there are no loops in graph but in custom input i am getting loops in my graph. Anyone please explain?

Why i am getting TLE for D.

i think it's complexity is same as described in editorial?

https://codeforces.com/contest/1366/submission/83593262

you are applying factorization every time you are taking an input,the whole point of storing the minimum prime using seive is to not do the thing which you are doing and get it done in less time so your code takes O(sqrt(n)/log(sqrt(n))*log(n))) every time and we once applied seive we can get it's prime factorization in O(log(n)) time

Not Sure about Complexity you described.I thought it's log(ai).Can u provide some source that prove your Comlexity(O(sqrt(n)/log(sqrt(n))*log(n))))!!

TIA

https://codeforces.com/blog/entry/7262

I have a conceptual doubt in problem D.

Let's say our number N has its prime factors p1,p2,p3,p4.

if we choose d1=p1 and d2=p2.p3.p4 ,then IS it NOT possible that x=p1.p3(let) can produce (d1+d2)modx=0 ?

since d1modx!=0 and also d2modx!=0.

d1 = p1 and d2 = p2 p3 p4

d2 makes it so d1 can never be p1 mod x = 0

but also d1 makes it so d2 can never be p2 mod x = 0. think about it this way, think about d2 as a multiple of p2. a multiple of p2 + p1 can never be mod x = 0. repeat for all prime factors and yeah

your comment encouraged me to pick up pen and paper and disprove myself wrong by writing just 2-3 lines using basic arithmetic modulo.

so thanks a lot :)

Problem E is very interesting. Can someone please help me figure out the best possible solution for problem E if condition b[i] < b[i+1] was not in place.

Getting wrong answer in the 2nd testcase of C. Can someone please help me find the mistake? Here's the link to my solution: 83472337

1

5 2

1 0

0 1

1 1

0 1

1 1

try this testcase ...

Got it, Thanks!!

https://codeforces.com/contest/1366/submission/83607595

can anyone help me ??what's wrong in my implementation of problem D?

How can A be done with binary search? The problem is tagged binary search, so i was wondering if anyone had any alternative approach using it?

Can Someone explain the problem statement of B.I am not able to get what we have to find.Also Please explain the solution too.(Not able to understand the editorial). Thanks in advance.

We have been provided with an array all elements are equal to zero except 1, and we need to find the number of elements which can end up equal to 1 after swapping . Now for the queries if the given interval is overlapping with even one element equal to 1 the all the elements in that interval in can end up as 1. So till the last query we can calculate all the elements which can be turned 1. Here is my solution B

Genuine Explaination Bro.Thanks for it.I Just did some paperwork then i got AC.

how can the concept of binary search be applied in the first question? Can anyone help me with that.

A similar problem to 1366A - Shovels and Swords

Yeah

How to solve C ? Can somebody explain the intuition in simpler terms ?

In Problem A, With 8 diamonds and 7 sticks, I can only earn four emeralds. Why is the expected answer 5?

4 pairs of diamonds + 4 sticks = 4 emeralds (zero diamonds left, 3 sticks left) OR

3 pairs of sticks + 3 diamonds and 1 pair of diamonds+stick = 4 emeralds (3 diamonds left, 0 sticks left)

3 pairs of diamonds + 3 sticks and 2 pairs of sticks + 2 diamonds gets you 5 emeralds

Can any one tell me why am i getting tle in my soln for D [https://codeforces.com/contest/1366/submission/84870746] I am trying everything but nothing is working .

Hi BledDest I am getting TLE for problem D. Below is code snippet :

What was the intended purpose of

`lst < prv`

in the model solution for F? I removed this check and the code is still accepted.How to solve A using Binary Search? Someone help please.

Problem C) is nice <3 <3 ! thank you for creating it

how do you find (a+b)/3 in 'A' problem???