Codeforces Round #597 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    while (b)
    {
        a %= b;
        swap(a, b);
    }
    
    return a;
}

int main()
{
    int t;
    for (cin >> t; t--;)
    
    {
        int a, b;
        cin >> a >> b;
        
        if (gcd(a, b) == 1)
            cout << "Finite" << '\n';
        else
            cout << "Infinite" << '\n';
    }
    
    return 0;
}

1245B - Restricted RPS

Tutorial

Solution

#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int q;
    for (cin >> q; q--;)
    {
        int n;
        cin >> n;
        int a, b, c;
        cin >> a >> b >> c;
        string s;
        cin >> s;
        
        vector<int> count(26);
        for (char x : s)
        	count[x - 'A']++;
        
        int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);
        
        if (2 * wins < n)
        {
        	cout << "NO" << '\n';continue;
        }
        
        cout << "YES" << '\n';
        string t;
        for (int i = 0; i != n; ++i)
        {
        	if (s[i] == 'S' && a)
        	{
        		t += 'R';
        		a--;
        	}
        	else if (s[i] == 'R' && b)
        	{
        		t += 'P';
        		b--;
        	}
        	else if (s[i] == 'P' && c)
        	{
        		t += 'S';
        		c--;
        	}
        	else
        		t += '_';
        }
        for (int i = 0; i != n; ++i)
        {
        	if (t[i] != '_')
        		continue;
        	
        	if (a)
        	{
        		t[i] = 'R';
        		a--;
        	}
        	else if (b)
        	{
        		t[i] = 'P';
        		b--;
        	}
        	else
        	{
        		t[i] = 'S';
        		c--;
        	}
        }
        cout << t << '\n';
    }
    
    return 0;
}

1245C - Constanze's Machine

Tutorial

Solution

#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;

const int MOD = 1000000007;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string s;
    cin >> s;
    
    for (char x : s)
    {
        if (x == 'w' || x == 'm')
        {
            cout << 0 << '\n';
            return 0;
        }
    }
    
    int n = s.size();
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = dp[i - 1];
        if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))
            dp[i] = (dp[i] + dp[i - 2]) % MOD;
    }
    
    cout << dp[n] << '\n';
    
    return 0;
}

Solution (Arpa)

// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 14, mod = 1e9 + 7;

int n, fib[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    fib[0] = fib[1] = 1;
    for(int i = 2; i < maxn; i++)
        fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
    string s;
    cin >> s;
    n = s.size();
    if(s.find('m') != -1 || s.find('w') != -1)
        return cout << "0\n", 0;
    int ans = 1;
    for(int i = 0, j = 0; i < n; i = j){
        while(j < n && s[j] == s[i])
            j++;
        if(s[i] == 'n' || s[i] == 'u')
            ans = (ll) ans * fib[j - i] % mod;
    }
    cout << ans << '\n';
}

1245D - Shichikuji and Power Grid

Tutorial

Solution

#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    pair<int, int> pos[n];
    for (int i = 0; i != n; ++i)
        cin >> pos[i].first >> pos[i].second;
    int c[n];
    for (int i = 0; i != n; ++i)
        cin >> c[i];
    int k[n];
    for (int i = 0; i != n; ++i)
        cin >> k[i];
    
    long long ans = 0;
    vector<int> power_plants;
    vector<pair<int, int>> connections;
    
    vector<bool> done(n);
    vector<int> parent(n, -1);
    for (int _n = n; _n--;)
    {
        int mi = 2000000000;
        int u = -1;
        for (int i = 0; i != n; ++i)
        {
            if (done[i])
                continue;
            
            if (c[i] < mi)
            {
                mi = c[i];
                u = i;
            }
        }
        
        ans += mi;
        done[u] = 1;
        if (parent[u] == -1)
            power_plants.push_back(u);
        else
            connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));
        
        for (int i = 0; i != n; ++i)
            if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])
            {
                c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));
                parent[i] = u;
            }
    }
    
    cout << ans << '\n';
    cout << power_plants.size() << '\n';
    sort(power_plants.begin(), power_plants.end());
    for (int x : power_plants)
        cout << x + 1 << ' ';
    cout << '\n';
    cout << connections.size() << '\n';
    for (pair<int, int> x : connections)
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
    
    return 0;
}

Solution (PikMike)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main(){
    int n;
    scanf("%d", &n);
    vector<int> x(n), y(n);
    forn(i, n)
        scanf("%d%d", &x[i], &y[i]);
    vector<int> c(n), k(n);
    forn(i, n)
        scanf("%d", &c[i]);
    forn(i, n)
        scanf("%d", &k[i]);
    
    ++n;
    vector<int> p(n, -1);
    vector<int> d(n, int(1e9));
    vector<bool> used(n);
    
    forn(i, n - 1){
        d[i] = c[i];
        p[i] = n - 1;
    }
    used[n - 1] = true;
    
    long long ans = 0;
    vector<int> vv;
    vector<pair<int, int>> ee;
    
    forn(_, n - 1){
        int v = -1;
        forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))
            v = i;
        
        if (p[v] == n - 1)
            vv.push_back(v + 1);
        else
            ee.push_back(make_pair(v + 1, p[v] + 1));
        ans += d[v];
        
        used[v] = true;
        forn(i, n) if (!used[i]){
            long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));
            if (dist < d[i]){
                d[i] = dist;
                p[i] = v;
            }
        }
    }
    
    printf("%lld\n", ans);
    printf("%d\n", int(vv.size()));
    for (auto it : vv)
        printf("%d ", it);
    puts("");
    printf("%d\n", int(ee.size()));
    for (auto it : ee)
        printf("%d %d\n", it.first, it.second);
}

1245E - Hyakugoku and Ladders

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int grid[10][10];
    for (int i = 0; i != 10; ++i)
        for (int j = 0; j != 10; ++j)
            cin >> grid[i][j];
    
    int flat[10][10];
    for (int i = 0; i != 10; ++i)
        for (int j = 0; j != 10; ++j)
                flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
    
    int d = 1;
    int x = 9;
    int y = 0;
    int arr[100];
    for (int i = 0; i != 100; ++i)
    {
        arr[i] = flat[x - grid[x][y]][y];
        
        if (y + d == -1 || y + d == 10)
        {
            d *= -1;
            x--;
        }
        else
            y += d;
    }
    
    double dp[100];
    dp[99] = 0;
    for (int i = 98; i >= 0; --i)
    {
        dp[i] = 1;
        
        int c = 6;
        for (int r = 1; r <= 6; ++r)
        {
            if (i + r >= 100)
                continue;
            dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;
            c--;
        }
        
        dp[i] = 6 * dp[i] / (6 - c);
    }
    
    cout << setprecision(10) << fixed << dp[0] << '\n';
    
    return 0;
}

1245F - Daniel and Spring Cleaning

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;

int f(int a, int b)
{
    int ret = 0;
    int zeroes = 0;
    
    for (int i = 1; i <= b; i <<= 1)
    {
        if (b & i)
        {
            b ^= i;
            
            if (!(a & b))
                ret += 1 << zeroes;
        }
        
        if (!(a & i))
            zeroes++;
    }
    
    return ret;
}

long long rec(int a, int b)
{
    if (a == b)
        return 0;
    if (a == 0)
        return 2 * b - 1 + rec(1, b);
    
    long long ret = 0;
    if (a & 1)
    {
        ret += 2 * (f(a, b) - f(a, a));
        a++;
    }
    if (b & 1)
    {
        ret += 2 * (f(b - 1, b) - f(b - 1, a));
        b--;
    }
    
    return ret + 3 * rec(a / 2, b / 2);
}

int main()
{
    int t;
    for (cin >> t; t--;)
    {
        int a, b;
        cin >> a >> b;
        cout << rec(a, b + 1) << '\n';
    }
    
    return 0;
}

for(int i=1; i<100; i++){ int t = to[i]?to[i]:i; for(int j=max(i-6, 0); j<=i-1; j++){ int k = min(6, 99-j); // k is 6 except for last few squares p[t]+=p[j]/k; dp[t]+=p[j]*(dp[j]+1)/k; } if(p[i]>0) dp[i]/=p[i]; } auto ans = dp[99]; for(int i=1; i<=5; i++){ ans += p[93+i]*(i/6.)/(1-i/6.); // expectation of standing still }

void _segfault_() { ll n; cin >> n; vector<pair<ll, ll>>vec(n); cin >> vec; vector<ll>a(n), b(n); cin >> a >> b; vector<pair<pair<ll, ll>, pair<ll, ll>>>aa; vector<vector<ll>>adj(n + 1); for (ll i = 0; i < n; i++) { aa.pb({{a[i], i}, {vec[i].ff, vec[i].ss}}); } sort(all(aa)); for (ll i = 0; i < n; i++) { for (ll j = i + 1; j < n; j++) { adj[i].pb(j); adj[j].pb(i); } } ll ans = aa[0].ff.ff; vector<ll>temp; vector<pair<ll, ll>>temp2; temp.pb(aa[0].ff.ss + 1); for (ll i = 1; i < n; i++) { priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>pq; vector<ll>dis(n + 1, LLONG_MAX / 2); for (ll j = 0; j < i; j++) { pq.push({0, j}); dis[j] = 0; } vector<ll>par(n + 1, -1); while (!pq.empty()) { pair<ll, ll>p = pq.top(); pq.pop(); for (auto child : adj[p.ss]) { if (dis[child] > dis[p.ss] + (abs(aa[p.ss].ss.ss - aa[child].ss.ss) + abs(aa[p.ss].ss.ff - aa[child].ss.ff)) * (b[aa[p.ss].ff.ss] + b[aa[child].ff.ss])) { dis[child] = dis[p.ss] + (abs(aa[p.ss].ss.ss - aa[child].ss.ss) + abs(aa[p.ss].ss.ff - aa[child].ss.ff)) * (b[aa[p.ss].ff.ss] + b[aa[child].ff.ss]); par[child] = p.ss; pq.push({dis[child], child}); } } } ans += min(dis[i], aa[i].ff.ff); if (aa[i].ff.ff <= dis[i]) { temp.pb(aa[i].ff.ss + 1); } else { temp2.pb({aa[par[i]].ss.ff + 1, aa[i].ff.ss + 1}); } } cout << ans << endl; cout << temp.size() << endl; cout << temp << endl; cout << temp2.size() << endl; for (auto it : temp2) { cout << it.ff << " " << it.ss << endl; } }

Comments (137)

Show archived | Write comment?

DeliciousFlatChest

5 years ago, # |

Auto comment: topic has been updated by DeliciousFlatChest (previous revision, new revision, compare).

→ Reply

VivaanGupta

← Rev. 2 →

+27

fastest editorial :D It also shows that the blog was made 4 hours ago

700YKSEULB

5 years ago, # ^ |

+25

even made before the contest :) This round is excellent, good job!

algo3rythm

orz DeliciousFlatChest

Please, don't stop creating CF rounds!!

Hd7

Sorry, what is orz mean?

+40

Orz (or more commonly, orz) is an emoticon that represents someone who has fallen over or is bowing down on their knees and perhaps pounding their head on the floor. The o is the head, the r is the arms and upper torso, and the z is the rest of the body and legs.

+55

sss

I think it's easier to understand =))

acidLemon

orz

liouzhou_101

"orz" is a verb. The original meaning of "orz someone" is "kneel down for someone", and the extended meaning is "show respect to someone".

gamer37

+60

A smooth Contest without any DDOS attack and any waiting judgement problem!

awoo

wooooo

WingsWings

Thank you for so fast editorial! :)

+11

I solved A without knowing proof. =)))

Me too xD

kolprogrammer

Story of all solver of today's A xD

HarendraSingh22

very true !

Takesha

Wow, the fastest editorial I've ever seen! Thanks for the round. Keep hosting rounds further!

Asuka_Minato

+10

Fastest Tutorial ! Cool !

Falcon__

I just hope there are 2:15 minutes

ameya

+17

(A) is the Chicken McNugget Theorem!

faresbasbas

cool theorem name XD

+18

This conclusion was also used in a problem of NOIP2017, whose name is Xiao Kai's doubt (小凯的疑惑 in Chinese). In fact, (A) is an excellent number theory problem. Thanks to DeliciousFlatChest for this perfect round. :)

yogi

I remained stuck in problem 1 for an hour until I realized I have been reading the question all wrong...

gupta_samarth

← Rev. 3 →

Is there any way to push dp value ahead for E? I was getting wrong answer for no ladders case, and I couldn't figure out why.

After contest, I saw some solutions ( namely neal's solution, PS: please share some insight ), and I had missed the case when the player is at the last 6 squares, after which he will waste some moves standing there itself.

How to implement this using push dp? I understand the pull from previous 6 version. Is it not possible to push in this case?

farmersrice

There is a theorem on bernoulli trials that says if there is a probability $$$p$$$ of an event happening on a turn, then the expected number of turns to reach the event once is $$$1/p$$$. With some logic you can see that for the closest 6 squares to the end, the answer will be 6 for all of them.

frost_

This result is so beautiful. Thanks.

Rafaaaaaaaaaaaam

I implemented push dp for E, calculating p[i] for the possibility for square i to be reached, and dp[i] for the expectation of runs before reaching square i. Also precalculate to[i] for the endpoint for ladder which starts at i.

Then this code can give currect answer to first two pretests:

But later i found out that using this method you cannot judge optically whether using the ladder or not. Because this requires information from the upper values. So i think this problem can only be dp'ed from top to bottom.

I don't understand why you say 'requires information from the upper values'. In fact, it is the opposite, for every cell that is the top of some ladder(s) you require answer from the bottom of the ladder(s).

I get accepted using push DP in 64069972. I hope its helpful to you.

Single_Ready_To_Mingle

DeliciousFlatChest Thanks for the amazing round.

bl4ckfr05t

I thought of solving D with MST but statement confused me and I gave up XD. Just came back after contest end to see the clarification.

It was indeed intended to be MST.

To not get confused by statement, you can always simplify the statement.

Simple idea here is, if all vertices are numbered from $$$1$$$ to $$$N$$$, then make a new vertex with number $$$0$$$, and for each $$$c_i$$$ given, make an edge from $$$0$$$ to $$$i$$$ with weight $$$c_i$$$, $$$ 1 \le i \le N $$$. This edge signifies making power station at $$$i$$$.

Apart from this, make edges between $$$i$$$, $$$j$$$, as mentioned, in $$$O(n^2)$$$ time. Then, it is just simple MST.

( EDIT: just realized Editorial has the same thing written xD ).

ghoshsai5000

Amazing explanation. Things just clicked for me after you added the explanation of an additional vertex $$$0$$$

huzaifa242

Exactly D was very deceiving. At first I thought about MST. Then I realised, that constraints are very low, so MST shouldn't be the answer(and it was D question). so I started looking in some other direction. Something like $$$O(N^2)$$$. After the contest I realised, that my assumption was incorrect. The solution could be MST because though the number of nodes is less, Number of edges are very significant( in worst case around $$$ 4 * 10^6$$$).

iyym

Actually MST is a poosible solution, and once you saw this problem you might think of MST. Each city is a point in the graph, and you add an edge for each pair of points $$$ (i, j) $$$ with weight $$$ (k_i + k_j) \cdot (|x_i - x_j| + |y_i - y_j|) $$$. According to the statement, we can build a power station in any city. This can be solved by adding a point indexed $$$0$$$. For each point $$$ i $$$ we add an edge between $$$i$$$ and $$$0$$$ with weight $$$ c_i $$$, and this edge means to build a power station in city $$$ i $$$ and costs $$$ c_i $$$. Our purpose is to choose some edges to make all the points connected (including point $$$0$$$). And clearly it's the MST problem.

However, we've got two algorithms to solve the MST problem — Kruskal and Prim. Kruskal needs to sort all the edges, so its time complexity is at least $$$ O(m \log m) $$$. There are about $$$ n^2 $$$ edges in our graph, so maybe you'll get a TLE. Prim is different. It is similar to Dijkstra and has time complexity $$$ O(n^2) $$$ and you can easily use it to get an AC in this problem.

Kruskal still pass it.

satyamcse

So true... Got a TLE with Prim

__Apocalypse__

Could someone help me figure out where am I going wrong in Problem D. Here is my submission 64039688. Thanks in advance.

LoneWolfKJ

I Had made the same mistake, found it by trying one of the later test cases.

Try the following test case
6
802169 415058
438621 719382
427378 361095
938841 703007
651689 546630
543902 45803
928313110 402257489 40475518 321650025 335526487 752229521
91 19 18 39 15 99

Correct answer:- 171488866
1
3
5
3 5
2 5
4 5
1 5
3 6

What was wrong in the logic of your code. Could you please elaborate

PRESS_F_2_PAY_RESPECT

4 years ago, # ^ |

Please tell what is wrong in my code for D? I am getting WA on test 13 but the minimal cost is correct. 84475396

hereForFun

In case someone wants to know the reason behind dp[i]=dp[i-1]+dp[i-2]

Eg: Suppose you want to know answer for uuuu, u =1 {u}, uu=2 {uu,w}, uuu=3 {uuu,uw,wu}. Think of uuuu as follows: Uuuu = u+ uuu (Just add u to the strings created by uuu). Also, Uuuu =w+uu (Just add w to the strings created by uu) considering w, because uu case would be considered in previous one)

Hence, uuuu={u+(uuu,uw,wu)}+ {w+ (uu,w)}

Vovkaez

Are you sure it is the reason? I suppose it's due to the fact that by pressing one button we can add either one or two symbols (m -> nn or n -> n) so the number of ways to get to i'th position is dp[i-1] + d[i-2] (e.g. in string "ann" dp[2] = 2 because we could've either written m->nn after "a", that's dp[i-2] ,or just added n in the end of "an", that's dp[i-1])

ashiknur

Can anyone suggest me a solution of problem C using modular inverse?

vrnnntw7965

Can somebody explain me please what is wrong with this approach to problem B.

Let dp[i][j][k] — maximal number of games we can win if we i times choose R, j times P and k times S.

So if we are at condition r,p,s than we can do the following:

if r+1 <= a than we can choose R one more time and move to r+1,p,s and if our opponent chooses S than we will win one more game so dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]+1), if our opponent chooses something different dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]).

Also we remember that if wins we can get with now is bigger than we already know we can, than parent[r+1][p][s] = 1

And we do the same for p and s

After that we check if 2*dp[a][b][c] < n and say "NO"

else we can win this game and recover the answer.

Idea doesn't seem to be wrong.

According to checker, you have printed only $$$9$$$ characters, whereas you should have $$$10$$$ chars for input

$$$n=10, a=5, b=0, c=5, string = RPRSRSRPPS$$$

Your output: $$$RSRRSRSSS$$$

Actual output : $$$RRSRRSSSSS$$$

ok,i got it, it was my previous submission. there i got situation where parent[r][p][s] == 0, so that means i cant get there but i didnt check for that. If i check it i cant find sol for this one at all

Well, an easy way to solve it is greedily. DP is too complicated, and possibly could give TLE as well. Your solution looks like $$$O(10^8)$$$.

Easier way is to solve greedily.

If Bob plays $$$r_b$$$ Rocks, $$$p_b$$$ Papers, $$$s_b$$$ Scissors, and we have $$$a$$$ Rocks, $$$b$$$ Papers, and $$$c$$$ Scissors.

Then maximum wins are $$$min(r_b,b) + min(p_b,c) + min(s_b,a)$$$.

Then, just assign $$$min(r_b,b)$$$ places of Rocks in Bob's string by Paper. Similiarly for the rest.

I just quickly wrote the same DP code. ( Check it here. )

It seems the problem is that you should initialize dp with $$$-1$$$ instead of $$$0$$$. Because in case you have Bob's string as $$$RRRRRR$$$ and you don't have any Paper with you, i.e. $$$b=0$$$, then answer is zero.

But, since you are updating by checking strict inequality, parent is never updated, even though something like $$$SSS$$$ has parent $$$S$$$.

Okay, I might be explaining it in a very bad way, but I think you get the gist of it.

I have done similiar errors. Some basic question like, return index of maximum element in array. I initialize $$$mx = 0$$$ and $$$ind = -1$$$ and return $$$-1$$$, instead of actual index of an element with value $$$0$$$.

I tried initialize dp as -1 and still get wa.

After that i rewrote my whole dp once more and finally get ac. No idea what was wrong in my last one

fazeel

WA for problem B. Can anyone figure out what's wrong in my code? Thanks in advance

(https://codeforces.net/contest/1245/submission/64019871)

murugappan_s

You append thing in the "out" variable only when alice can win, but you should append something when alice loses too.

mrvikash31j

I am unable to understand the editorial for problem F.

zeus_iitg

Can someone explain why my code is wrong.

Link to submission:- https://codeforces.net/contest/1245/submission/64040834

Logic Explained:-

For every city, I calculate the minimum cost of providing electricity to it (either by joining with someother city or by installing a power station in it, the former includes adding an edge between the two cities and the latter introduces no new edge.) Then I calculate the cost for every connected component using dfs.

Any help would be highly appreciated.

Thanks in advance

limabeans

i also did a similar approach and got WA test case 13, see my comment

NEZZ

Test case
5
5 15
19 13
19 13
24 14
20 13
2 10 20 10 2
6 4 2 4 5
Credits goes to GLAYS
More details : https://ibb.co/dD8sJcM

for D, what was the intended corner case for test case 13? here is my submission:64025515.

my idea was: consider the graph where every node x is connected to every other node y with edge weight cost dist(x,y)*(k[x]+k[y]). for every node, join them with union find to the closest node in the graph, unless it is cheaper to just add a power station to that node (in this case, don't join this node to any other node). then, assign one power station (the cheapest one) for every connected component. can anyone point out the flaw in my algorithm? thanks.

check this

thanks! update: the mistake in my algorithm was that i wasn't considering the scenario where the node that has a cheaper power station cost than any neighboring connections could actually be "helpful" to its neighbors and lower the overall cost.

SinKing

Who can explain proof for D from editorial? I stuck on the case, when there is smaller cost in component. Why is it true that putting power plant there gives more profit? I think myself understanding wrong this point. Here is my exmple breaking this statement: City1 : c = 10001, k = 1 City2 : c = 10001, k = 1 City3 : c = 10000, k = 2

And let take coordinates such as dist(City1, City2) = 2, dist(City1, City3) = dist(City2, City3) = 100

let our optimal city to be City1 There are only 3 cases:

Leave all without changes. Then we have cost = 10000 + 2 * (1 + 1) + 100 * (1 + 2) = 10403
Assign new power plant at City3. Obviously, cost > 20000
Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601

So best power plant is City with c = 10001 So to take the lowest c_i appears not to be optimal.

"Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601",

There's an issue here... Looks like you've connected City 3 with 1 and 2, but you should have connected City 3 with City 1 and then provide power to city 2 to via City 1. The answer would be 10000 (Station at City 3) + (1+2)*100 + (1+1)*2 = 10304

HadyKo

In Problem F, Shouldn't f(0,r) = 2 * r — 1 + f(1, r) ?

Ahh yes, thanks for pointing it out. It has been updated now.

doitman1

Can anybody help me with my solution of D. here is my code https://ideone.com/tRcPzZ

it gives the wrong answer to test 13 with a slight difference. please help submission https://codeforces.net/contest/1245/submission/64048567

leave it I got where I go wrong.

_FAHA_

For problem C , how it is reduced to fibonacci ?

let's suppose we have i n's in sequence ( nnn....n i times ). Now two cases can be there:-

(1) last character is n

(2) last character is m ( disguised as nn )

hence dp[i] = dp[i-1] + dp[i-2].

The first term for the first case and the second term for the second case.

Hence, fibonacci

aaijmrt

In problem C, what is wrong with this approach?

Find the number of consecutive n or u.

Then find the number of possible strings that can create it.

eg. number of consecutive n = 4.

With 0 m, number of possible string = 4!/4! = 1

With 1 m, number of possible string = 3!/(2!*1!) = 3

With 2 m, number of possible string = 2!/2! = 1

Total = 5

It is correct approach and gives AC.

Link to submission:-

https://codeforces.net/contest/1245/submission/64014595

Thanks. I was getting WA because of an overflow :(

Nothing, that's exactly what fibonacci is ! Memoize what you just said and you'll have the fibonacci sequence ! Either way will get to the same answer, just that your way the calculation will get a bit lengthy soon! Better just observe how it can be generalized.

lonesome

Regarding Problem C, what is the intuition behind applying Fibonacci( dpi=dpi−1+dpi−2 ),i mean do i try all possible combinations for small input and then deduce the Sequence is Fibonacci. Any help will be appreciated, Thanks in advance.

Here is my explanation:-

https://codeforces.net/blog/entry/71080?#comment-555410

Fype

Hi, can anybody explain why my solution to D is wrong. For each two city x, y add edge between them if (k[x] + k[y]) * d(x, y) is less than building a power station in at least one of them. Then for each component build a power station in city where has the minimum cost and calculate MST for each component for edges that we have to make.

https://codeforces.net/contest/1245/submission/64059625 here is my code. I'm not getting WA on your test

Lets say you have 3 nodes 1,2,3

dist(1,2)=10

dist(2,3)=20

dist(1,3)=30

let k be 1 for all

C[1]=5

C[2]=50

C[3]=10

you try to put them all in one same component,because edge cost for 1,2 would be 20 but max(c[1],c[2]) would be 50. Same explanation for 2,3.

Now you assign power station to minimum C value node in each component. So here in this example it would be 1, and for rest of the node in the component you use MST of edges.

This fails for the above mentioned example. The above mentioned example in terms of input would be,

5 10

15 10

35 10

5 50 10

1 1 1

The answer for this input would be 35, power stations on 1 and 3 and edge 1,2

This fails because you join things to same component when edge weight is less than max of c values of nodes.

When one of the nodes has a c value less than the edge weight, but unfortunately in MST, the node with max c weight can be assigned first, you shouldn't use that edge in this scenario, because instead of the edge, creating a power station on the min C weight node would give better answer.

thanks

gagannagpal68

For 1245E, let's say there are no ladders. After flattening the array, why push dp is wrong.

I am getting 28.0476190

Pushing logic is straightforward.

for(int d= 1;d<=6;d++) 
   dp[f(i +d)]+=(1.0 + dp[i])/6.0

f(x) is the new move as mentioned in editorial.

Here is the code : https://ide.geeksforgeeks.org/BvBaJFwLip

During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is r. If the Goal is less than r squares away on the path, the player doesn't move (but the turn is performed).

← Rev. 4 →

Thank you for the beautiful contest, DeliciousFlatChest !

Here are my thoughts on the problems —

$$$A$$$ — It was a very elegant problem on Bezout's Identity
$$$B$$$ — Good Greedy Construction Problem
$$$C$$$ — DP
$$$D$$$ — It reminded me of this problem on AtCoder — Various Sushi 116D. I was trying to use a similar idea here. After sorting the power stations by their cost,

I thought of first, making power stations in only the first power station and building connections for all the other stations.

Then, to make a power station in only the first 2 power stations and build connections in all other power stations.

And so on.

However, this was $$$O(n^3)$$$ and I couldn't find a way to make it shorter.

The MST solution is quite surprising !

$$$F$$$ — Again it reminded me of 2 AtCoder questions — Sum Equals XOR 129E and XOR Sum 2 098D. The main difference between $$$129E$$$ and this question was that in $$$129E$$$, only $$$a + b$$$ had to be $$$ < L$$$, but here both $$$a, b$$$ had to be in $$$[L, R]$$$. I was trying to build on the solution to these problems for this one.

By the way, here are my solutions to the problems of this contest so far in case anybody wants to refer them.

triple__a

another similar problem in AtCoder 138F Coincident

Thanks for sharing !

wangyc

You seem to put two same links

Thanks, I fixed it.

ale

Is it possible to solve F using digit-dp like algorithm?

arman_ferdous

+35

Yes.

Alternate solution to problem F: you can use digit dp to find the answer :) You need to keep track of 5 states. Let, $$$dp[f1][f2][f3][f4][p]$$$ = Number of pairs of binary numbers with $$$p$$$ digits and $$$f1, f2, f3, f3$$$ are $$$0/1$$$ values indicating:

$$$f1 = 1$$$ means first number is bigger than $$$l, 0$$$ otherwise
$$$f2 = 1$$$ means first number is smaller than $$$r, 0$$$ otherwise
$$$f3 = 1$$$ means second number is bigger than $$$l, 0$$$ otherwise
$$$f4 = 1$$$ means second number is smaller than $$$r, 0$$$ otherwise

Ideally, when you have $$$f1 = f2 = 1$$$, that means our current number is already within $$$[l,r]$$$ giving us the freedom of putting any $$$0/1$$$ as current digit. Other cases? You can easily figure that out.

So using $$$f1, f2$$$ we can find some $$$[l1, r1]$$$ bound for current digit of first number. And using $$$f3, f4$$$ get another bound for second number $$$[l2, r2]$$$. Now bruteforce on all possible pairs other than $$$1,1$$$ pair :)

My submission 64025375

pms_venkatesh_saki_147

could you elaborately explain your approach with few examples.

towrist

Thanks for your solution, but I think the definition of $$$DP(f1, f2, f3, f4, p)$$$ should be

"The number of pairs of integers $$$(a, b)$$$ GIVEN that the first $$$p$$$ digits of BOTH $$$a$$$ and $$$b$$$ cause... (now cases on $$$f1, f2, f3$$$ and $$$f4$$$)"

yes that's exactly what i wanted to say. thanks.

vjvjain0

I recommend to try out few digit-dp problems otherwise you may not understand anything.

My digit-dp approach:
Let $$$f(x, y)$$$ be a function which returns all pairs $$$(a, b)$$$ such that $$$a + b = a \oplus b$$$ where $$$0 \le a \le x$$$ and $$$0 \le b \le y$$$.

Now to calculate $$$f(x, y)$$$ we will use digit-dp approach. In our digit-dp we will consider bit representation of $$$x$$$ and $$$y$$$ rather than decimal representation which is generally used(as this is obviously a bit manipulation problem :P). Let $$$dp[i][f1][f2]$$$ = Number of pairs possible such that $$$a \& b = 0$$$ $$$(0 \le a \le x$$$ and $$$0 \le b \le y)$$$ considering $$$i$$$ rightmost bits. Here $$$f1$$$ signifies if we selected $$$i - 1$$$ rightmost bits in such way that we may not want to consider $$$1$$$ bit for $$$i$$$. $$$f2$$$ signifies same but for $$$y$$$.

Now, answer will be $$$f(r, r) - 2 \times f(l - 1, r) + f(l - 1, l - 1)$$$.

Answer Explaination

Link to Code

hieplpvip

C++ submission

Hi, can you please explain what you mean by "considering $$$i$$$ rightmost bits"? What exactly are you "considering" here?

$$$i$$$ rightmost bit would be like $$$2^{i}$$$

programbhavan

can some explain what is mean by "minimum expected number of turns" in problem E?

It means assuming that the player plays optimally. In this specific problem, whether to take the ladder or not.

Problem A is very, very beautiful. Sad that many of us (including me) solved it without being aware of the complete proof. (I only proved the Bezout's theorem part).

Way_Above_your_level_lol

Please help me. Im getting wrong answer Testcase 9 for Problem C. I think my logic is correct as the alternative solution. Still doesn't work. How to even debug in such cases?64029232

barun511

rep(i,2,100002)
{
    dp[i] = sum[i-2]+1;
    sum[i]=sum[i-1]+dp[i];
}

won't you get an overflow here?

why? after I change to dp[i]=dp[i-1]+dp[i-2] I still get signed integer overflow. Im unable to see why its overflow, dp size is big enough? 64068550

Um, yes, but integer/long long size is not big enough. You should be doing operations mod10^9+7

dhruv_garg

for the problem f I am checking accepted solution and here I found one in which I am not able to understand this line. solution link — https://codeforces.net/contest/1245/submission/64013273

line ===>> int ans = f(r, r) — 2 * f(l — 1, r) + f(l — 1, l — 1);

How above line gonna work . Anybody ..thankyou.

DimmyT

I think that in function f is gets pairs, which a <= l && b <= r && a ^ b == a + b in the rectangle 0, 0, l, r. This line is getting the value of function f in rectangle l, l, r, r, which is rectangle(0, 0, r, r) -rectangle(0, 0, l-1, r) -rectangle(0, 0, r, l-1) + rectangle(0, 0, l-1, l-1)

@DimmyT I got it thankyou..Takes a time but now understand completely..thankyou :)

You're welcome)

Spheniscine

← Rev. 8 →

Problem E is quite interesting; I did manage to figure out the DP logic but I didn't know how to calculate the sum for the squares near the goal... however there is a kick-yourself-simple solution I found once I coded it according to the editorial.

$$$dp_i$$$ for $$$94 \leq i \leq 99$$$ is... always exactly $$$6$$$. Why? Because consider: you have a $$$p = \frac16$$$ chance of rolling the right number to reach the goal exactly, and the expected number of turns require to hit it is the mean of its geometric distribution, $$$\frac1p = 6$$$. But if you roll a lesser number, your new square still only has a $$$\frac16$$$ chance of getting the right number, so though you're closer to the goal physically, you're still no closer in terms of the turns required to roll the right number, so you might as well not have moved at all.

AK18

I got your point, moving not at all and moving some pieces ahead has no difference as it won't affect the number of expected turns, So it's always 6 for that region. Nice observation.

rojansudev700

Can anyone explain A?I didn't understand the solution.

I venture most people just solved A by staring at it for a while and conjecturing the correct solution. Actually proving it is somewhat harder.

OK, here's a perhaps simpler "proof" based on the images in my head when I solved this problem.

Assume WLOG $$$a < b$$$. Consider the sequence $$$an \mod b$$$ for integers $$$n$$$ incrementing from $$$0$$$. If and only if $$$\gcd(a, b) = 1$$$, it will eventually cover the entire ring of integers $$$\mod b$$$ (forming a discrete Weyl sequence), which is equivalent to the cells colored white as you consider chunks of length $$$b$$$ moving to the right, thereby limiting the black cells to a finite number.

Nahid

Even I don't know how works my ac code of 1245A. But how i got ac !!! :o

t1war1

Can someone please help me in problem D? Here is my code: Code

I've used Kruskal using DSU to solve this problem by sorting all the edges by weights and then merging the nodes if the cost of wire to connect them is less than the maximum of their cost of building powerhouses(because on making connection, there will be one powerhouse needed which should be minimum of both).

iamskp

Can someone please explain the proof of problem A in an easy way?

andr1y

if we can reproduce number with any remainder of division by one number using another number, then answer is Finite, otherwise answer is Infinite. This can be checked using GCD (if GCD of two numbers is 1, then answer is Finite, otherwise Infinite).

Arpa

My solutions to some of the problems: B: 64089807, C: 64086504, D: 64086519, E: 64086541.

shubham0898

C can be solved by normal PnC too.My solution

mehulcoder

Do we have to necessarily connect a city in a group to it's parent? Or we can connect it to any city in the group which will give us the minimum connection cost(basically which has electricity but not a power station necessarily)?

PS: Parent of a group is the one with a power station

The latter is the case.

UPD : My code is giving me WA on Test case 13. Could someone please help me with it? I've tried a lot. But couldn't debug it.

My code

I think TC 13 means: You were asked to make all of cities have electricity, and to do it, you don't need all cities connected each other, you only need each city to belong to 1 connected component which has at least 1 city containing power state. To simplify problem, you add a dummy city and make all components connect each other. Now you only need to find the MST of $$$n+1$$$ city (including dummy city).

The statement only says,

You must provide electricity to all cities ( either by making a power station there, or connecting it to "some" other city that already has electricity ).

And the second part basically says, that electricity is transitive, i.e. if City $$$A$$$ has a power station and City $$$B$$$ is connected to it, then $$$B$$$ also has electricity, and thus, if you connect City $$$C$$$ with $$$B$$$, then $$$C$$$ also has electricity.

Also, about your code. It seems you are using a greedy strategy, by making the cheapest power stations, but that is not correct. There could be a possibility to make a costlier power station that supplies all cities, instead of making cheap power stations in each city. ( Read my short explanation here ).

Can you please explain to me, what does 'rt' and 'sz' mean in your code? And what exactly does 'connect' function does!

It's just DSU ( Disjoint Set Union ). Read about it online.

This is a good resource.

UPDATE: Also, I think I didn't explain it clearly, so, we use DSU as part of Kruskal's algorithm for finding a MST ( Minimum spanning tree ) for a graph.

monir82

Problem D is tagged with trees.Can any one explain this problem according to trees algorithms.And thanx in advance.Happy coding.

It can be solved using MST (Minimum Spanning Tree) like this. You can use either Prim or Kruskal algorithm. But in this problem, Prim is better.

You can learn more about this in Wikipeia. (Poor Chinese, we can't link to the Wiki page!)

CarolinaMoura

I don't know if it is right for you to say that f(2l,2r) = 3*f(l,r). Suppose we are looking at the interval 2,5. Your argument implies that, when counting f(4,10), we must consider the case where we chose for the first one's less significant bit number 0, and, for the second one's less significant bit, number 1, and the other ones we chose, for instance, 10 and 101, respectively (that are pairs found in f(2,5) ). But that does not give the answer. In fact, f(2,5) = 6 and f(4,10) = 16.

dulatcodes

Really good editorial!

kiimak

Hello guys!

I was wondering if I could get some help on problem D. I can't seem to find a corner case or prove why my solution is wrong. My solution follows this idea that was already mentioned in the comments by anakib1 in the Announcement page.

"I had following idea to D. Lets make minimum spanning tree of graph with edges c(i,j)=(ki+kj)∗d(i,j) for all i,j. Firstly lets add the cheapest plant. Then sort edges in non-increasing order and we will try to delete every edge. If we are considering edge (x,y) let c1 will be component with vert x of tree without edge (x,y) and c2 will be component with vert y of tree without edge (x,y). Only one of this components has installed plant now. Let it be c2 . Then find cost of the cheapest plant in c2 and check if its better to add plant instead of edge from spanning tree. If its better to add plant, we delete edge (x,y) and add plant."

I did get to test 32, but can't analyze the test case since its quite large (N = 2000). I would really appreciate if anyone can help me find my mistake. I've added comments in the my submission, hope it helps. Thanks! 64906030

Hello.

Here is the generator used for test 32: https://dpaste.de/hSQn

To generate test 32, compile it (you'll need the testlib.h file), and run with command-line arguments 21 2000 100. So for example, if I would do it on my Linux machine, after compiling using g++ file.cpp, I would type ./a.out 21 2000 100 > in and then the testcase would be saved in file in. Hope this helps.

Thank you for the quick reply! I will check this out!

sudhanshu6324

For problem D, can somebody point out what's wrong in my approach

first iterate over all cities one by one
for each city i , find the minimum of all costs to connect this city j ( 1 <= j <= n) let's call it min_cost
now we have two scenario either this city i has its own power house or is connected to some other city which will have a power house

just compare C[i] with min_cost

a. if(C[i] < min_cost) , we can simply have a individual plant for this city

 b. otherwise we connect this to city j, which gave us min_cost

now we have a graph with
simply iterate over all connected components
for each component find the minimum C[i] and add it to final cost answer, since we are planting a power plant at this i'th city
rest of this connected component let's just find the MST and add this to final answer , since all the other cities would be connected to some other city with wires having power connection
repeat 7

My Submission

yeah this logic is incorrect because i might miss some of the edges which could help reduce the overall cost see this example copied from above cmt

5 15

19 13

24 14

20 13

2 10 20 10 2

6 4 2 4 5

gauravmahendraker

16 months ago, # |

D was asked in google interview lol

_Aryan_

13 months ago, # |

why it is getting tle

for each node i have two choices whether to setup station or connect to any existing station so i am using multisource dijikstra to find min cost required to connect it station .

lvisbl_

11 hours ago, # |

I have a weird approach for D, but I can not proof it myself. Hope somebody has the same idea give some proof. Basically, I just "greedy" delete edges of MST. Suppose we have built our MST successfully with n — 1 edges. We will ask "what kind of edges we can remove from the MST by adding power station to reduce the total cost" or we need to choose edges to remove and vertices to build power station so that all connected components connect to at least 1 power station.

The observation: with n — 1 edges chosen it will form a tree, if we remove any edge, the tree will be separated into two components. Greedily, we want to remove the largest edge of the MST. Suppose the largest edge E connect two nodes u, v. We claim that, we can remove this edge if after removing the cost to make "all connected components connect to at least 1 power station" better. If we remove E, we need to make sure two trees in two sides with u and v are root connected, then we DFS from u and v to find two smallest power stations X and Y in two sides (there will be a case when a side is already connected with power station then the cost for that side is 0). And we will remove E if X + Y < weight E + min(X,Y) (the least cost after removing is smaller than least cost before removing then we remove). This expression can be expressed as max(X,Y) < weight E.

Submission: 289959387

DeliciousFlatChest's blog