Idea: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
t = int(input())
for _ in range(t):
a, b, c = map(int, input().split())
d1 = a - 1
d2 = abs(b - c) + c - 1
ans = 0
if d1 <= d2:
ans += 1
if d1 >= d2:
ans += 2
print(ans)
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
char get(int i) {
return 'a' + i - 1;
}
void solve() {
int n;
string s;
cin >> n >> s;
int i = n - 1;
string res;
while (i >= 0) {
if (s[i] != '0') {
res += get(s[i] - '0');
i--;
} else {
res += get(stoi(s.substr(i - 2, 2)));
i -= 3;
}
}
reverse(res.begin(), res.end());
cout << res << '\n';
}
int main() {
int t = 1;
cin >> t;
for (int it = 0; it < t; ++it) {
solve();
}
return 0;
}
```

Idea: MikeMirzayanov, Aris

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve() {
string s;
cin >> s;
int n = s.size();
map<char, vector<int>> let_to_ind;
for (int i = 0; i < n; ++i) {
let_to_ind[s[i]].push_back(i);
}
int direction = (s[0] < s[n - 1]) ? 1 : -1;
vector<int> ans;
for (char c = s[0]; c != s[n - 1] + direction; c += direction) {
for (auto now : let_to_ind[c]) {
ans.push_back(now);
}
}
int cost = 0;
for (int i = 1; i < ans.size(); i++)
cost += abs(s[ans[i]] - s[ans[i - 1]]);
cout << cost << " " << ans.size() << '\n';
for (auto now : ans) {
cout << now + 1 << " ";
}
cout << '\n';
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
```

1729D - Friends and the Restaurant

Idea: MikeMirzayanov, Aris, myav

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
int n;
cin >> n;
vector<ll>x(n), y(n);
vector<pair<ll, int>>dif(n);
for(auto &i : x) cin >> i;
for(auto &i: y) cin >> i;
for(int i = 0; i < n; i++){
dif[i].first = y[i] - x[i];
dif[i].second = i;
}
sort(dif.begin(), dif.end());
reverse(dif.begin(), dif.end());
int j = n - 1, cnt = 0;
for(int i = 0; i < n; i++){
while(j > i && dif[i].first + dif[j].first < 0) j--;
if(j <= i) break;
cnt++; j--;
}
cout << cnt << endl;
}
int main() {
int t;
cin >> t;
while(t--){
solve();
}
}
```

Idea: Gornak40, MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
long long ask(int a, int b) {
cout << "? " << a << ' ' << b << endl;
long long x; cin >> x;
return x;
}
long long solve() {
for (int i = 2; i <= 26; i++) {
long long x = ask(1, i);
long long y = ask(i, 1);
if (x == -1) return i-1;
if (x != y) return x + y;
}
assert(false);
}
int main() {
long long ans = solve();
cout << "! " << ans << endl;
}
```

1729F - Kirei and the Linear Function

Idea: Gornak40

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int, int> ipair;
const int MAXSZ = 200200;
const int INF = 2e9;
inline int add(int a, int b) {
return (a + b >= 9 ? a + b - 9 : a + b);
}
inline int sub(int a, int b) {
return (a < b ? a + 9 - b : a - b);
}
inline int mul(int a, int b) {
return a * b % 9;
}
int sz, n, m;
string s;
int ps[MAXSZ];
vector<int> D[9];
void build() {
sz = s.size();
for (int md = 0; md < 9; ++md)
D[md].clear();
for (int i = 0; i < sz; ++i)
ps[i + 1] = ps[i] + (s[i] - '0');
for (int i = 0; i + n <= sz; ++i)
D[(ps[i + n] - ps[i]) % 9].push_back(i);
}
ipair solve(int l, int r, int k) {
int x = (ps[r] - ps[l]) % 9;
ipair ans {INF, INF};
for (int a = 0; a < 9; ++a) {
int b = sub(k, mul(a, x));
if (D[a].empty() || D[b].empty()) continue;
if (a != b)
ans = min(ans, make_pair(D[a].front(), D[b].front()));
else if (D[a].size() >= 2)
ans = min(ans, make_pair(D[a].front(), D[a][1]));
}
if (ans == make_pair(INF, INF))
return {-2, -2};
return ans;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
int t; cin >> t;
while (t--) {
cin >> s >> n >> m;
build();
for (int i = 0; i < m; ++i) {
int l, r, k; cin >> l >> r >> k, --l;
auto [ans1, ans2] = solve(l, r, k);
cout << ++ans1 << ' ' << ++ans2 << endl;
}
}
}
```

Idea: DmitriyOwlet, MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<cstdio>
#include<cstring>
const int N=505;
const int Mod=1e9+7;
char s[N],t[N];
int n,m;
int f[N],g[N];
int p[N],tot;
inline void Init(){
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);
m=strlen(t+1);
tot=0;
for(int i=1;i+m-1<=n;i++){
bool flg=1;
for(int j=1;j<=m;j++)
if(s[i+j-1]!=t[j]) flg=0;
if(flg) p[++tot]=i;
}
return ;
}
inline int addv(int x,int y){
int s=x+y;
if(s>=Mod) s-=Mod;
return s;
}
inline int subv(int x,int y){
int s=x-y;
if(s<0) s+=Mod;
return s;
}
inline void add(int&x,int y){
x=addv(x,y);
return ;
}
inline void sub(int&x,int y){
x=subv(x,y);
return ;
}
inline void Solve(){
memset(f,0x3f,sizeof(f));
memset(g,0,sizeof(g));
p[0]=-N;
f[0]=0;
g[0]=1;
p[++tot]=n+m;
for(int i=0;i<tot;i++){
int j=i+1;
while(j<=tot&&p[j]<=p[i]+m-1) j++;
for(int k=j;p[j]+m-1>=p[k]&&k<=tot;k++){
if(f[i]+1<f[k]){
f[k]=f[i]+1;
g[k]=g[i];
}
else if(f[i]+1==f[k]) add(g[k],g[i]);
}
}
printf("%d %d\n",f[tot]-1,g[tot]);
return ;
}
int T;
int main(){
for(scanf("%d",&T);T;T--){
Init();
Solve();
}
return 0;
}
```

Can someone breif me the

logicorapproachof F??the value of v(l,r)%9 for anly l,r can be found using string hashing. Now for each l,r query we need to find v(L1,L1+w-1) and v(L2,L2+w-1) but since we need mod 9 hence in total there will be 9 possible valus for each thus in total we can 81 combinations now for each combination check if the condition given is true or not if it is then push the value {L1,L2} in a vector then return the smallest value in the vector.

Code with comments if u have any doubt do let me know.:)

Great solution, you can also use a tip which can make the code easier. For any number, if the sum of all digits is divisible by 9, then that number is divisible by 9. It works simillar if you want to calculate the remainder. For example: 1233: 1 + 2 + 3 + 3 = 9, and 1233 / 9 = 137. Therefore, you can do the operation using prefix sum. (This operation is also available when dividing by 3)

Nice will try it for sure.Thanks for sharing.

this is only true for 3 or 9?

Yes. For other single digits, there are other ways to check, but those methods are too inefficient to calculate.

finally!

can anyone explain the approach of G?? as here the logic was like brute the entire string(smaller one) with it's repetitions in the larger one , but how is the code checking the optimal removal part? also if there is any topic required as a prerequisite in Dp feel free to suggest.

Why isn't this blog put in the contest materials?

Problem E is like if u can't find an optimal solution, use brute force such that it does not give a TLE or go beyond the constraints. We can thereafter prove that our solution is correct at one point because all the other attempts failed and hence we have a higher Probability. So we are correct!

I have learned a new technique and wondered if probability can even be used like this. kudos to the problem setter.

+1. I use binary search ->TLE then tannery search still TLE. Still unable to get the intuition, but still, I find something new to learn. Can you explain the probability concept of the question? (Weak in maths)

learn about Randomization. here we the probability of getting different paths increases with number of queries. Let's say probability of getting same paths length is 1/2 in 1st attempt so probability of getting same path length again will be 1/2*1/2 = 1/4 and so on so in about 25 attempts it will be (1/2)^25 which is very low so if we do the operations many time the probability of getting different path is very high. It's close to 99.9999%.

Code for F is broken, likely because - is automatically converted to — and then to

`&mdash`

That is probably just some dumb html problem

In D, answer will be 0 and not -1 when no groups can be formed.

Good catch!

Can anyone suggest similar problems to E for practice

According to me, this type of problem is not that much productive to solve, instead understanding how probability played a major role in the solution is enough. You can try some interactive problems whose acceptance is completely in your control(not probability) and they are much fun, like this one1698D.

During the contest, at very start I thought to use binary search, but for the worst case number of query will be Log(10^18)base2, which is something 54-55, then it was obvious for me to try something else and after some tries I figured how to go for the solution, but to be honest, I was ready for a TLE or WA after I'd submitted the solution with probability (1-1/(2^25)), BCZ I'm not that lucky :)

This is a nice problem that uses probability like problem E 843B - Interactive LowerBound

1743D - Problem with Random Tests This is not an interactive problem. But its quite similar because of random testCases

For Problem C:

We don't need to iterate to find cost.

`cost = Math.abs(s[0] - s[n - 1])`

Very good contest i love all the problem specially E

There is a small error in E. The probability is slightly smaller than 1/2, since both paths have the same length when dist(x, y) = n/2-1. Which means fixing x and changing only y will give a better probability than changing x and y simultaneously (but still a little worse than 1-2^-25).

For problem E it was not

veryclear from the statement whether interactor assigns answers randomly for ordered pairs (a, b) or not. It could have assigned randomly for each unordered pair, but within same pair (a, b) and (b, a) would not have had 0.5 probability. If that was the case, we would need some other solution.I've managed to get AC with something like:

I don't have formal formulae with probabilities, but at each not skipped step of that algorithm we

alwayscontribute one to the answer in our statistic we're collecting, but may also contribute to some garbage values. My guess was that we contribute to garbage less. :)Can anyone please explain approach for G, I am able to find the minimum lenght greedily. Facing difficulties in finding the number.

Thank you in advance for helping

We can solve E using binary search. Ln(10^18) ~ 41 or 43 (don’t remember). Use request ? 1 mid, and if answer != -1 then l = mid, else r = mid

it would take log2(10e18) queries not Ln(10e18) which exceeds 50

Aaaa, i forgot that it log2, not loge. Then yes, incorrect solve

For problem C, I think there's no need to iterate and calculate the cost. It would be just absolute difference of FIRST and LAST letters.

Yes, but I think we have to iterate to find the path.

In problem D if no pairs could be formed the answer is obviously 0, not -1.

lazy_loop wrote this already.

Editorial of editorial of G please.

Notice that we need to maximise the size of the Final string , considering that size of character

`.`

is 0.Using KMP or String Hashing Algorithm or any other algorithm find out the indexes K, such that

`s[K-m+1.....K]=t[0....m]`

, where $$$m$$$ is the size of string $$$t$$$ and push them into vector named $$$ind$$$Now make a 2D DP , where

`DP[i][j]`

representing number of ways to make prefix of string $$$s$$$ of size $$$i$$$ equal to string of size $$$j$$$ , assuming that`.`

size is 0.Now if index $$$i$$$ does not lie in $$$ind$$$,

`DP[i][j]`

would be`dp[i-1][j-1]`

, i.e. we take the`i'th`

element of string $$$s$$$ and add it to the final string.Else we can take the sum of

`DP[K-m][j-(i-K)]`

such that`K>i-m`

and`K<=i`

, where K are the elements in vector $$$ind$$$.`K-m`

represents that all characters of`s[K-m+1.....K]='.'`

, and we substract`(i-K)`

from j because we have already taken all characters in`s[K+1.....i]`

Let me know if some part is unclear.

I came up with a 1D dp solution eventually. Your answer inspired me quite a lot, thank you.

If index i doesn't lie in the ind, shouldn't

`dp[i][j]`

be equal to`dp[i-1][j-1]`

, as dp denotes the number of ways?Yes , you are right .

Edited :)

can someone share their approach/code for prob. C in java? Mine's failing for some test cases, can't figure out why

I don't understand why is E rated 1800? In full honesty, the solution seems so ridiculously easy to come up with. After I thought about it during upsolving, I thought it was so simple that something had to be wrong. After checking the editorial, turns out, nothing was wrong. You really did just have to query pairs

`a b`

and`b a`

until you get two different responses.in problem D , why pair is used?

can anyone help why I am getting run time error on test 7 here in problem F

https://codeforces.com/contest/1729/submission/172335851

The number represented in string could be way larger than any build-in type. It's obvious that your convert function can only handle 32-bit integer. Btw I think convert string to integer is not the intention of this problem.

Ah thanks, misread the constraints, I thought l, r were such that the length doesn't exceed 8

In problem E, had it been 60 queries, then we could have find the size of graph by simply applying binary search, right?

yep

I would like to ask what is the function of this sentence (p[++tot]=n+m;) in the standard code given by the questioner of G question? thanks

Can someone give me a hint on problem D?

Thanks in advance.

It's more optimal to have groups consisting in only two people.

Thank you :)

What is the test case 3 of Problem C? I can't understand which case I have missed in my solution here. Is there any constraint in the sequence of path? Does the path have to match exactly as mentioned in the test cases?

Take a look at Ticket 16197 from

CF Stressfor a counter example.Double thanks for the reference to the awesome tool and also the failing test case. I had to use stable_sort() in my logic.

Code chhapne pe idleness limit exceeded nhi aayi, but same code khud krne se aagyi. (Translation: Copying code didn't give idleness limit exceeded, while writing the same code did. Submissions: https://codeforces.com/contest/1729/submission/173058013 https://codeforces.com/contest/1729/submission/173057953 ) Someone comment pls :(

how can we detect the minimum possible accurate number of guesses in problem E ?

please can someone explains the detailed solution for problem G, I can't understand tutorial.

https://codeforces.com/contest/1729/submission/174301987

can someone explain what's wrong with my code here?

Take a look at Ticket 16234 from

CF Stressfor a counter example.