Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
for (int i = 1; i < int(s.size()); ++i) {
if (s[i] < s[i - 1]) {
cout << "YES" << endl;
cout << i << " " << i + 1 << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
1155B - Игра с телефонным номером
Разбор
Tutorial is loading...
Решение (Roms)
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
cin >> n >> s;
int cnt1 = (n - 11) / 2;
int cnt2 = cnt1;
string res = "";
for(int i = 0; i < n; ++i){
if(s[i] == '8'){
if(cnt1 > 0) --cnt1;
else res += s[i];
}
else{
if(cnt2 > 0) --cnt2;
else res += s[i];
}
}
if(res[0] == '8') cout << "YES\n";
else cout << "NO\n";
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<long long> x(n), p(m);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
for (int i = 0; i < m; ++i) {
cin >> p[i];
}
long long g = x[1] - x[0];
for (int i = 2; i < n; ++i) {
g = __gcd(g, x[i] - x[i - 1]);
}
for (int i = 0; i < m; ++i) {
if (g % p[i] == 0) {
cout << "YES" << endl;
cout << x[0] << " " << i + 1 << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
typedef long long li;
const int N = 300 * 1000 + 13;
const li INF64 = 1e18;
int n, x;
int a[N];
li dp[N][3][3];
int main() {
scanf("%d%d", &n, &x);
forn(i, n) scanf("%d", &a[i]);
forn(i, n + 1) forn(j, 3) forn(k, 3)
dp[i][j][k] = -INF64;
dp[0][0][0] = 0;
forn(i, n + 1) forn(j, 3) forn(k, 3){
if (k < 2)
dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]);
if (j < 2)
dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
if (i < n)
dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1));
}
printf("%lld\n", dp[n][2][2]);
}
Разбор
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 long double ld;
typedef pair<int, int> pt;
const int MOD = 1000 * 1000 + 3;
int norm(int a) {
while(a >= MOD) a -= MOD;
while(a < 0) a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
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;
}
int inv(int a) {
return binPow(a, MOD - 2);
}
int k = 10;
vector<int> f;
int main() {
f.resize(k + 1);
fore(i, 0, sz(f)) {
cout << "? " << i << endl;
cout.flush();
cin >> f[i];
}
vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1));
fore(i, 0, sz(mat)) {
mat[i][0] = 1;
mat[i][sz(f)] = f[i];
fore(j, 1, sz(mat[i]) - 1)
mat[i][j] = mul(mat[i][j - 1], i);
}
/*
fore(i, 0, sz(mat)) {
fore(j, 0, sz(mat[i]))
cerr << mat[i][j] << " ";
cerr << endl;
}
*/
fore(j, 0, sz(mat)) {
int nid = -1;
fore(i, j, sz(mat)) {
if(mat[i][j] != 0) {
nid = i;
break;
}
}
if(nid == -1)
continue;
swap(mat[j], mat[nid]);
fore(i, 0, sz(mat)) {
if(i == j) continue;
int cf = mul(mat[i][j], inv(mat[j][j]));
fore(cj, j, sz(mat[i]))
mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj]));
}
}
vector<int> a(sz(f), 0);
fore(i, 0, sz(a)) {
if(mat[i][i] == 0)
continue;
a[i] = mul(mat[i][sz(a)], inv(mat[i][i]));
}
fore(x0, 0, MOD) {
int val = 0;
for(int i = sz(a) - 1; i >= 0; i--)
val = norm(mul(val, x0) + a[i]);
if(val == 0) {
cout << "! " << x0 << endl;
return 0;
}
}
cout << "! -1" << endl;
return 0;
}
1155F - Олигополия на доставку
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
const int INF = int(1e9);
int dp[1 << N];
int par[1 << N];
int last[1 << N];
pair<int, int> last_pair[1 << N];
int dp2[N][N][1 << N];
int lastv[N][N][1 << N];
vector<int> bits[1 << N];
int n;
int m;
vector<int> g[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < (1 << n); i++)
dp[i] = INF;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int z = 0; z < (1 << n); z++)
dp2[i][j][z] = INF;
for(int i = 0; i < n; i++)
for(auto x : g[i])
{
dp2[i][x][0] = 1;
lastv[i][x][0] = i;
}
for(int mask = 0; mask < (1 << n); mask++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF))
continue;
for(auto z : g[j])
{
if(mask & (1 << z)) continue;
if(z == lastv[i][j][mask]) continue;
int nmask = mask ^ (1 << j);
if(dp2[i][z][nmask] == INF)
{
dp2[i][z][nmask] = 1;
lastv[i][z][nmask] = j;
}
}
}
for(int mask = 0; mask < (1 << n); mask++)
for(int j = 0; j < n; j++)
if(mask & (1 << j))
bits[mask].push_back(j);
dp[1] = 0;
for(int mask = 0; mask < (1 << n); mask++)
for(int addmask = mask; addmask; addmask = (addmask - 1) & mask)
{
int lastmask = mask ^ addmask;
int cnt = __builtin_popcount(addmask) + 1;
if(dp[lastmask] + cnt >= dp[mask])
continue;
bool f = false;
for(auto x : bits[lastmask])
{
for(auto y : bits[lastmask])
{
if(dp2[x][y][addmask] == 1)
{
dp[mask] = dp[lastmask] + cnt;
last_pair[mask] = make_pair(x, y);
last[mask] = addmask;
}
if(f) break;
}
if(f) break;
}
}
if(dp[(1 << n) - 1] == INF)
cout << -1 << endl;
else
{
cout << dp[(1 << n) - 1] << endl;
int cur = (1 << n) - 1;
while(cur != 1)
{
int lst = last[cur];
int x = last_pair[cur].first;
int y = last_pair[cur].second;
cur ^= lst;
while(lst)
{
int ny = lastv[x][y][lst];
cout << y + 1 << " " << ny + 1 << endl;
lst ^= (1 << ny);
y = ny;
}
cout << x + 1 << " " << y + 1 << endl;
}
}
}
My approach for problem D is quite different. I hope it would be easy to understand.
At first, I build 2 arrays Left(i) and Right(j) that return the maximum sum of a subarray ending at i with Left(i) and starting at j with Right(j). I also have array Sum(i) is sum of all elements from 1 to i.
When we multiply the subarray (l..r), the result in current case is
Left(l-1) + x * (Sum(r) - Sum(l-1)) + Right(r+1)
.We can rewrite it by
(Right(r+1) + x * Sum(r)) + (Left(l-1) - x * Sum(l-1))
.With this formula, my solution is a loop for i from 1 to n, take i as the right most of the multiply subarray, get the best value of the left most to update the answer.
See my submission for more details: 53150702
i prefer your solution to this editorial's solution. Your solution is more interesting and easier for me to understand. Love it
Thank you.
Can u please explain the formula part in detail I am not able to understand it?
Let 's take subarray (l..r) to multiply.
The sum of this segment is Sum(r) — Sum(l-1) and after multiply is x * (Sum(r) — Sum(l-1)).
But we don't stop at this with x is negative number. You can see the first test case, we would try to increase the answer by openning its border.
What is best way to do that? My solution is using arrays Left and Right.
Loved your approach
What a great solution!!
So good
Admire !
I am unable to understand why did you do this res = max (res, Left[i]); when you had to maximize just these two terms in the last loop Right(r+1) + x * Sum(r)) + (Left(l-1) — x * Sum(l-1))
We can choose " at most one consecutive subarray of a " but my math expression is just correct when I choose a non-empty subarray from l to r.
thank you , your solution is more easier than tutorial
Beautiful Solution!!!
This approach really helped a lot man ..thanx :)
[user:l0s3r]Can you explain why you did res = max (res, Left[i]); in your code?
https://codeforces.net/blog/entry/66687?#comment-514349
Brilliant way of rearranging and solving complex things in easy way kudos to you!
but how is it handling at most one operation part
why is E so easy
Humblebrag
I can't get my head around as to why greedy won't work for D. If x is non positive, why can't we just find the maximum negative sum and multiply it by x? My code doesn't pass, so it is definitely wrong, but I don't know why.
Edit: my bad, I gave a wrong example. See the responses.
I think your example is wrong cause multiplying x with -2 also gives 2+10-1+10 = 21.
One example can be :
7 -1
-20 21 -15 10 -10 20 10.
Here -20 is the largest non-positive segment but it gives 20+21-15+10-10+20+10 = 56.
But multiplying -15 by -1 gives 21+15+10-10+20+10 = 66
In your example, you'd get 21 in either case. What you wanted to say was:
Is there another way to get the polynomial on problem E? ( Not using Gaussian elimination )
You can use lagrange interpolation
I have an approach for D that is more in the 'style' of Kadane's algorithm. The beautiful part of the array consists of 3 "segments", the 1 part, the X part, and the 1 part again.
Like Kadane's, we loop through each x in the array, maintaining bestK = the largest value of K segments ending in the current x value.
Can you explicate the best3?
Let A[i:j] denote the sum A[i] + ... + A[j] For a given j,
Wow I learned the essence of kadanes algorithm from your solution
Thank You!
For problem B, wasn't it enough to simply ignore the last 10 characters of the string and check whether more than half of the remaining characters are equal to '8'?
Yes. If the number of 8's is at most
(n - 11) / 2
or the number of moves each person gets, Petya can remove all the 8's. The number of digits that are not 8's isn - 10 - numberOf8s
, therefore if the number of 8's is greater than(n - 11) / 2
the number of digits that are not 8 will be less thann - 10 - (n - 11) / 2 = (n - 9) / 2
, which is at most(n - 11) / 2
. So Vasya would be able to remove all the non-8's.Can anyone explain editorial's tutorial for problem D in simple and easy way.
i want this too :/
I honestly don't get why my solution isn't working. I get WA on the 11th test case, but the output seems fine to me. Am I missing something?
https://codeforces.net/contest/1155/submission/53204105
Try to find here.
In problem E, how can we be sure that the value of f(xi) that we use to interpolate the polynomial is actually the value of the polynomial or less than the actual value because of MOD 1e6 + 3
For example, if the polynomial is 1 + (1e6+1)x + x^2, f(0) = 1, f1(1) = 1e6+2, f(2) = 2e6 + 7 MOD 1e6 + 3 = 1. Now the polynomial we interpret will be wrong.
Isn't f(1) = 1e6+3 = 0?
my bad. But the point stands? The function could be changed.
If you do the interpolation with the correct values you'll end up with the correct polynomial and I believe that it will always be correct because of the way modular arithmetic works.
So assume that the question said instead of 11 degrees the polynomial is 2 degrees only. Then the polynomial interpolated from above info is 1 — 2x + x^2, again obviously wrong. Maybe, it will give the correct value of zero when taken MOD 1e6+3 but I don't find in intuitively clear.
-2 is congruent to 1e6 + 1 mod 1e6 + 3, so 1 — 2x + x^2 is congruent to 1 + (1e6 + 1)x + x^2 mod 1e6 + 3 and the interpolated polynomial is correct.
Got it. Thanks a lot, that helped!
Another approach for problem D
We find the Best subarray ending at ith index and at every index maintain three possible sums 1) x has not yet been used previously nor being used by this element 2) x is being used by this element 3) x was used by some prev segment and hence this element cannot use x
Transitions for calculating ith index results
1) is simple to extend using prev index's result
2) either extend prev index result 1) or 2) should multiply a[i] by x
3) can extend 2) or 3) but should not multiply a[i] by x
https://codeforces.net/contest/1155/submission/53223589
Thanks a lot. It helped me to solve the problem!
Glad to know :)
wow very impressive!! and your solution is very similar to ecnerwala's
My "solution" for F: first use dp to calculate for each subset of vertices and each pair of vertices if there is a path between those vertices passing through exactly gives subset of vertices, exactly once. From this we can get for each subset if there is a cycle passing through each of them exactly once. Iterate over all subsets and identify those, which have a Hamiltonian cycle, but none of their proper supersets does. Now while we have time left pick a random of those subsets, put all edges from the cycle to the graph, random_shuffle all other edges, add them in order and if this edge is not redundant (i.e their endpoints aren't already in the same biconnected componend) add it. After each iteration check if current solution is better, than best found so far. If it is store it. I saw some other people getting accepted with similar approach. Any idea how to defeat it? 53200092
I've solved problem F with a random way. We can delete some edges in E, and then run Tarjan algorithm to find all strongly connected components. If the graph is bi-connected, the all nodes are supposed to form a single strongly connected component. The number of deletion strategy is 2^|E|, it's too large to try all possible strategies. But we can turn to a greedy way, iterate over each edge, if it's redundant, just delete it. You need run the process several times to get a satisfying result, before each process, shuffle the E at first.
That's quite unfortunate.
I think if the edges were weighted the model solution would look the same, but any randomized shit would be in trouble because e.g. for random weights it's very likely that optimal solution is unique, or the assertion I used that if for some set of vertices with Hamiltonian cycle there is its superset which also has a Hamiltonian cycle is no longer true.
Can you share your submission?...@dalt
My submission is written on java, hope it will help 53384647
I find a way using greedy and segment tree to solve D You can see my submission 53466247.awoo
Can you explain your solution?
Let we make l the start of the range we multiple x.And then we need to find best r to be the end of the range we multiple x.The answer of [l,r] to multiple x is left[l]+sum(l,r)*x+right[r].Because the left[l] is fixed, we only need to consider sum(l,r)*x+right[r].Then we can use a segment tree to find the best r quickly.
Problem E: What would be the problem if the limit was not a prime?? Can anyone explain??
In this problem, we use Gaussian Elimination to solve a modular SLAE (System of Linear Algebraic Equations). In Gaussian Elimination, some steps involve division operations. So, the division steps, in this case, involve finding out the multiplicative inverse of the denominator and multiplying the numerator by that. The multiplicative inverses may not exist if the module is not prime and in that case, we will not be able to use Gaussian Elimination to solve the problem.
Where can I read about Gaussian elimination method?
change ur profile pic i thought there is something on my screen so tried to rub it off
For problem D can someone explain me what ecnerwala did to solve it. His code looks quite simple but I am unable to understand it :( . Here's the link to his solution 53141642
Okay, so this is what I understood:
A number can be in these 5 states:
This gives you good information about the first loop.
The second loop is about saying "the maximum sum, doing whatever, before the current element".
So for (int z = 0; z+1 < 5; z++) dp[z+1] = max(dp[z+1], dp[z]); makes dp useful for the next for (int z = 0; z < 5; z++) dp[z] += weights[z] * v; Where, we calculate: dp[i] = dp[i](The max until i, by including, not including, multiplying etc) + weights[i]*v(the weight according to state) ;
that is damn cool
what is wrong in this code 1155D
include<bits/stdc++.h>
using namespace std;
define ll long long
define mod 1000000007
define pii pair<ll,ll>
define mp make_pair
define se second
define fi first
define pb push_back
ll max(ll a,ll b) { if(a>b) return a; return b;
}
int main() { ll n,x; cin>>n>>x; ll a[10000007]={0}; for(ll i=0;i<n;i++) { cin>>a[i];
}
The size of dp array is 100000 and should be 300000
1155D - Beautiful Array — My solution is similar to alexwice and arajatchauhan813, you just have a dp table of n * 3 in which you have:
dp[i][1]:the maximum sum without multiplying until i
dp[i][2]:the maximum sum up to i having already multiplied and without multiplying from i
dp[i][3]:the maximum sum up i multiplying a piece that ends in i
Then :
So you only need visit the table and find the greatest solution
There is my solution 55211386