Codeforces round 883 Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

Hint 1

Hint 2

Tutorial

Solution

#include <iostream>

using namespace std;


int main() {
	int test_cases;
	cin >> test_cases;

	for (int test_case = 0; test_case < test_cases; test_case++) {
		int n;
		cin >> n;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			if (a > b)
				ans++;
		}
		cout << ans << endl;
	}

	return 0;
}

Rate the problem

1846B - Rudolph and Tic-Tac-Toe

Author: Sasha0738

Hint 1

Tutorial

Solution

#include <iostream>
#include <vector>
#include <string>


using namespace std;

int main() {
	int test_cases;
	cin >> test_cases;
	for (int test_case = 0; test_case < test_cases; test_case++) {
		vector<string> v(3);
		for (int i = 0; i < 3; i++)
			cin >> v[i];
		string ans = "DRAW";
		for(int i = 0; i < 3; i++) {
			if (v[i][0] == v[i][1] && v[i][1] == v[i][2] && v[i][0] != '.')
				ans=v[i][0];
		}
		for (int i = 0; i < 3; i++) {
			if (v[0][i] == v[1][i] && v[1][i] == v[2][i] && v[0][i] != '.')
				ans=v[0][i];
		}
		if (v[0][0] == v[1][1] && v[1][1] == v[2][2] && v[0][0] != '.')
			ans=v[0][0];
		if (v[0][2] == v[1][1] && v[1][1] == v[2][0] && v[0][2] != '.')
			ans=v[0][2];
		cout << ans << endl;
	}
	return 0;
}

Rate the problem

1846C - Rudolf and the Another Competition

Author: vladmart

Hint 1

Hint 2

Tutorial

Solution

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ttt;
    cin >> ttt;
    while(ttt--){
        int n, m, h;
        cin >> n >> m >> h;
        pair<int, long long> rud;
        int ans = 1;
        for(int i = 0; i < n; i++){
            vector<int> cur(m);
            for(int j = 0; j < m; j++){
                cin >> cur[j];
            }
            std::sort(cur.begin(), cur.end());
            int task_cnt = 0;
            long long penalty = 0, sum = 0;
            for(int j = 0; j < m; j++){
                if (sum + cur[j] > h) break;
                sum += cur[j];
                penalty += sum;
                task_cnt++;
            }
            if (i){
                if (make_pair(-task_cnt, penalty) < rud) ans++;
            } else rud = {-task_cnt, penalty};
        }
        cout << ans << '\n';
    }
    return 0;
}

Rate the problem

1846D - Rudolph and Christmas Tree

Author: vladmart

Hint 1

Hint 2

Hint 3

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10); cout.setf(ios::fixed);
    int ttt;
    cin >> ttt;
    while (ttt--) {
        int n, d, h;
        cin >> n >> d >> h;
        vector<int> y(n);
        for(int i = 0; i < n; i++){
            cin >> y[i];
        }
        long double ans = (long double)d * h / 2.0;
        for (int i = 0; i + 1 < n; ++i) {
            if (y[i + 1] >= y[i] + h) ans += (long double)d * h / 2.0;
            else{
                long double d2 = (long double)d * (y[i] + h - y[i + 1]) / h;
                long double nh = y[i + 1] - y[i];
                ans += (d + d2) / 2.0 * nh;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Rate the problem

1846E1 - Rudolf and Snowflakes (simple version)

Author: natalina

Hint 1

Hint 2

Hint 3

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

set<long long> nums;

int main() {

    for (long long k = 2; k <= 1000; ++k) {
        long long val = 1 + k;
        long long p = k*k;
        for (int cnt = 2; cnt <= 20; ++cnt) {
            val += p;
            if (val > 1e6) break;
            nums.insert(val);            
            p *= k;
        }
    }



    int _ = 0, __ = 1;
    cin >> __;

    for (int _ = 0; _ < __; ++_) {
        long long n;
        cin >> n;
        

        if (nums.count(n)) cout << "YES" << endl;
        else cout << "NO" << endl;

    }


    return 0;
}

Rate the problem

1846E2 - Rudolf and Snowflakes (hard version)

Author: natalina

Hint 1

Hint 2

Hint 3

Hint 4

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

set<long long> nums;

int main() {

    for (long long k = 2; k <= 1000000; ++k) {
        long long val = 1 + k;
        long long p = k*k;
        for (int cnt = 3; cnt <= 63; ++cnt) {
            val += p;
            if (val > 1e18) break;
            nums.insert(val);
            if (p > (long long)(1e18) / k) break;
            p *= k;
        }
    }



    int _ = 0, __ = 1;
    cin >> __;

    for (int _ = 0; _ < __; ++_) {
        long long n;
        cin >> n;
        if (n < 3)
        {
            cout << "NO" << endl;
            continue;
        }
        long long d = 4*n - 3;
        long long sq = sqrt(d);
        long long sqd = -1;
        for (long long i = max(0ll, sq - 5); i <= sq + 5; ++i) {
            if (i*i == d)
            {
                sqd = i;
                break;
            }
        }
        if (sqd != -1 && (sqd - 1) % 2 == 0 && (sqd - 1) / 2 > 1)
        {
            cout << "YES" << endl;
            continue;
        }

        if (nums.count(n)) cout << "YES" << endl;
        else cout << "NO" << endl;

    }


    return 0;
}

Rate the problem

1846F - Rudolph and Mimic

Author: Sasha0738

Hint 1

Hint 2

Tutorial

Solution

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
	int test_cases;
	cin >> test_cases;
	for (int test_case = 0; test_case < test_cases; test_case++) {
		int n;
		cin >> n;
		vector<int> v(n);
		map<int, int> m;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			m[v[i]]++;
		}
		vector<int> elements_to_erase;
		int ans;
		for (int i = 0; i < 5; i++) {
			if (v.size() - elements_to_erase.size() == 1) {
				cout << "! " << ans << endl;
				break;
			}
			cout << "- " << elements_to_erase.size() << " ";
			for (int j = 0; j < elements_to_erase.size(); j++) {
				cout << elements_to_erase[j] << " ";
			}
			cout << endl;
			vector<int> new_v;
			map<int, int> new_m;
			for (int j = 0; j < v.size() - elements_to_erase.size(); j++) {
				int x;
				cin >> x;
				new_v.push_back(x);
				new_m[x]++;
			}
			elements_to_erase.clear();
			int tm = -1;
			for (auto& k : new_m) {
				if (k.second > m[k.first]) {
					tm = k.first;
				}
			}
			if (tm != -1) {
				for (int j = 0; j < new_v.size(); j++) {
					if (new_v[j] != tm)
						elements_to_erase.push_back(j + 1);
					else
						ans = j + 1;
				}
				m.clear();
				m[tm] = new_m[tm];
			}
			v = new_v;
		}
	}
	return 0;
}

Rate the problem

1846G - Rudolf and CodeVid-23

Author: vladmart

Hint 1

Hint 2

Hint 3

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ttt;
    cin >> ttt;
    while (ttt--) {
        int n, m;
        cin >> n >> m;
        bitset<10> tmp;
        cin >> tmp;
        int s = (int) tmp.to_ulong();
        vector<pair<pair<int, int>, int>> edges(m);
        for (int i = 0; i < m; i++) {
            cin >> edges[i].second;
            cin >> tmp;
            edges[i].first.first = ((1 << n) - 1) ^ (int) tmp.to_ulong();
            cin >> tmp;
            edges[i].first.second = (int) tmp.to_ulong();
        }
        vector<int> dist(1 << n, INT_MAX);
        dist[s] = 0;
        set<pair<int, int>> q = {{0, s}};
        while (!q.empty()) {
            auto [d, v] = *q.begin();
            q.erase(q.begin());
            for (int i = 0; i < m; i++) {
                int to = v & edges[i].first.first;
                to |= edges[i].first.second;
                if (dist[to] > d + edges[i].second) {
                    q.erase({dist[to], to});
                    dist[to] = d + edges[i].second;
                    q.insert({dist[to], to});
                }
            }
        }
        if (dist[0] == INT_MAX) dist[0] = -1;
        cout << dist[0] << '\n';
    }
    return 0;
}

Rate the problem

#include <bits/stdc++.h> using namespace std; long long int sumpow(long long int x, int y) { long long int p=1; for(int i=1;i<=y;i++) { p=1+x*p; } return p; } int main() { int t; cin>>t; for(int i=1;i<=t;i++) { long long int n; cin>>n; int decider=0; for(long double j=2;j<(log(n)/log(2));j++) { long long int c=powl(n,1/j); if(sumpow(c,j)==n) { decider=1; cout<<"YES"<<endl; break; } } if(decider==0) { cout<<"NO"<<endl; } } return 0; }

for (int i = 0; i < m; ++i) { for (int mask = 0; mask < 1 << 10; ++mask) { // cost[mask] = cost for getting this much protection if ((damage[i] & mask) == damage[i]) { minSelf(cost[save[i] | mask], cost[mask] + days[i]); } } }

import sys input=sys.stdin.readline for _ in range(int(input())): n=int(input()) for i in range(2,61): a=int(n**(1/i)) if a==1: print("NO") break c=1 ae=0 t=0 while ae<n: ae+=c c=c*a t+=1 if ae==n and t>2: print("YES") break else: print("NO")

int t = 0; //we use this variable as a switch to check (iterate over all divisors k of n-1){ int a = n*(k - 1) + 1; int x = 0; (since we need p >= 2, x >= 3 while (a % k == 0) { a /= k; x++; //we need x to count the exponent, which is p } x -= 1; if (a == 1 && x >= 2 ) t = 1; break; //if we reach here we can finish early } if (t == 1) cout << "YES"; else cout << "NO";

#include <bits/stdc++.h> #define int long long using namespace std; unordered_map <int, int> mp; int n; signed main() { // n == (k^(t+1) - 1) / (k - 1)，等比数列 // 下边生成在t >= 3时的所有n值 for (int k = 2; k <= 1000100; k ++) { for (int t = 3; ; t ++) { if ((pow(k, t + 1) - 1) / (k - 1) > 1e18) break; __int128 fz = pow(k, t + 1) - 1; __int128 fm = k - 1; if (fz % fm == 0) { mp[fz / fm] = 1; } } } int t; cin >> t; while (t --) { cin >> n; // 如果在t >= 3的时候可以得出n，输出 if (mp[n]) { cout << "YES" << endl; continue; } // 判断在t == 2时是否能够得出n // 即判断1 + k + k^2 = n是否有解，(2 <= k <= x, 其中x约等于1e9) int l = 2, r = 1e9 + 1000; while (l < r) { int mid = (l + r + 1) / 2; if (mid * mid + mid + 1 > n) { r = mid - 1; } else { l = mid; } } if (l * l + l + 1 == n) { cout << "YES" << endl; continue; } cout << "NO" << endl; } return 0; }

Comments (120)

Write comment?

not_ahmed_hamed

10 months ago, # |

+13

HacksForces

→ Reply

Zhiyong99

10 months ago, # ^ |

Hahaha

naman.gokhru.mst20

7 weeks ago, # ^ |

Hahaha Hahaha

MONISM

← Rev. 3 →

For E2 there is a simpler solution to check if there exists a $$$k$$$ such that $$$1 + k + k ^2 = n$$$.

You can rearrange the equation to $$$k(k + 1) = n - 1$$$. It follows that the only $$$k$$$'s you need to check are $$$\lfloor \sqrt{n - 1}\rfloor$$$ and $$$\lfloor \sqrt{n - 1}\rfloor - 1$$$. This is a modified version of the official solution : code

EDIT : as davi-v pointed out,there is no need to check for $$$\lfloor \sqrt{n - 1}\rfloor - 1$$$.

xiojoy

Great!

sagar1213

can you explain why are checking the equation for k=2 and why we only floor(sqrt(n — 1)) and floor(sqrt(n — 1)) — 1 ?

Sure! I assume you meant $$$exponent = 2$$$,not $$$k = 2$$$. If you deal with all $$$k$$$ $$$<=$$$ $$$10 ^ {6}$$$ (for example by precalculating a set of valid numbers),for all other $$$k$$$ $$$>$$$ $$$10 ^ {6}$$$ the exponent must be exactly $$$2$$$. That is because the minimmum exponent is $$$2$$$ and if the exponent was $$$3$$$ the sum would be larger than $$$10 ^{18}$$$.Now we have to check that there exists a $$$k$$$ such that $$$1 + k + k ^2 = n$$$. This is the same as checking if there is a $$$k$$$ such that $$$k(k + 1) = n - 1$$$. Now, let $$$r = \sqrt{n - 1}$$$. It is easy to see that $$$k < r$$$. However, $$$k$$$ must be as large as possible so $$$k$$$ is either $$$\lfloor r \rfloor$$$ or $$$\lfloor r \rfloor - 1$$$ when $$$n - 1$$$ is a perfect square.

I want to say like for p=2 the equation would be 1+k+k^2. So why we have taken for p=2 if the no. Is not found in precalculated array.

natalina

Because for n <= 10¹⁸ and p = 2 the value of k could be approximately sqrt(n) = 10⁹. But we can precalc values only for k <= 10⁶

1+k+k^2=n how do we get to this ?

This is formula for the number of vertexes in minimal snowflake. 1 vertex at the initial value, k vertexes at the second layer and k^2 vertexes at the third one.

eslamfash489

9 months ago, # ^ |

انا

SerbanC

Very inefficient approach. It can be done with binary search sir !!!

leducphuclong

← Rev. 2 →

I did think about BS in the cts, but I couldn't go with that, can you tell me that solution ?

Aqin7

can u explain "if (p > (long long)(1e18) / k) break;" Why this statement is necessary?

The if statement is necessary because otherwise the sum could overflow. If you have to check if $$$a \cdot b > val$$$ , a neat way of doing this and avoiding overflow is checking if $$$a > val / b$$$. Hope this helps!

Thank u for your reply, i got it:)

davi-v

You don't need to check $$$\lfloor{\sqrt{n-1}}\rfloor - 1$$$. Let $$$m = n - 1$$$. For $$$k(k+1)=k^2+k$$$ to be $$$m$$$, $$$k < \sqrt{m}$$$. Let $$$x = \lfloor\sqrt{m}\rfloor$$$. The question is: which numbers of the form $$$k=x-c$$$, $$$c \ge 0$$$ do we need to check?

Substituting in $$$k(k+1)$$$, we get $$$(x-c)(x-c+1)=x^2+x(-2c+1)+c^2-c$$$. Note that $$$x(-2c+1)+c^2-c$$$ must be $$$\ge 0$$$, as $$$x^2 \le m$$$. We need to show that if $$$c > 0$$$, $$$x(-2c+1)+c^2-c < 0$$$, so $$$x^2+x(-2c+1)+c^2-c$$$ can't equal $$$m$$$.

Note $$$c \le x$$$, otherwise $$$k$$$ would be negative. Let $$$x = c + d, d \ge 0$$$. Substituting, we get

$$$ x(-2c+1)+c^2-c = (c+d)(-2c+1)+c^2-c\\ =-2c^2+c-2cd+d+c^2-c=-c^2-2cd+d. $$$

If $$$c > 0$$$, $$$-c^2-2cd+d=-c^2+d(-2c+1) < 0$$$, as $$$-c^2 < 0$$$ and $$$-2c+1 \le 0$$$.

You are correct! Thank you for pointing out my mistake, I will make sure to correct it shortly. Also, I found a simpler proof to prove we don't need to check $$$ \lfloor \sqrt{n - 1}\rfloor$$$ :

I claim that for any number $$$a = k ^ {2},k\in\mathbb{N},\nexists b \in \mathbb{N}$$$ such that $$$b \cdot (b + 1) = a$$$. When $$$b = k,b \cdot(b + 1) > a$$$ and when $$$b <= k - 1,b \cdot(b + 1) < a$$$. Because $$$b \cdot(b + 1)$$$ is either $$$>$$$ or $$$<$$$ than $$$a$$$,we can conclude that $$$b \cdot(b + 1) \neq a$$$.

expertaq

E2 is a superb binary search question, liked it

WarriorOfLiberation

If you still haven't got the idea a more simpler bs solution is consider 1+k+k^2+..k^p, observe that this is less than k^(p+1) and as well observe that the maximum value of p can be 63 since any power greater than p and the sum>1e18, so from here we can bruteforce for all powers and for this power we can upper bound the value of k by n^(1/p), and binary search which value of k satisfies 1+k+...k^p==n, if any confusion feel free to ask.

V1N17

Can you please explain the concept of n^(1/p). I am not getting this part.

So if it's something like if 1+k+k^2+..+k^p=n then k^(p+1)>n, you can easily deduce that I think(correlate it with binary recall that bit set at position i is bigger than all combined from i-1 to 1), so from k^(p+1)>n, we get got any k greater than n^(1/(p+1)) we definitely can't get the answer so that is the upper bound, hope it helps.

got it,thanks.

sanwal_aditya

Hi, can anyone help me debug my submission for E2? Don't know why I am getting WA.Thanks in advance.212818653

Zac_Tang

I don't know why I can't pass test9 :(((

roycf123

I tried the similar approach in python (no overflow) and got WA on tc 16 after increasing the max value upto 1e25... (was AC initially and finally got hacked :(( )

Further increment gave TLE... maybe the constraints weren't designed for the binary search solution... (unless I'm wrong, in which case I would appreciate if someone pls provided me with an AC solution)

P.S: My initial approach in C++ was returning LLONG_MAX in the binpow function whenever overflow occured (used a check_overflow() function...) which gave WA on tc 5... Idk why...

i3mr125

why is the D in editorial AC without setprecision? what differs from my submission . ik i messed up the setprecision in my code but still why

Precision is set before the solution code at the beginning of the main function

wow didn't notice. nice info ty

neelesh510

-16

At the time of contest 1846C is accepted so I have done 4th but next day it is showing wrong on test case 10. it's your fault not mine.

Abito

it's your fault

It's plateform fault because it is showing correct how can I know it fails on some test case

After contests end more tests are added

gardengnome

From the announcement: "The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks."

This is part of typical D3 rounds: you will not know whether your solution passes all tests during the contests, and this challenges you to think carefully about special and corner cases and thus helps to improve your skills.

iamneerajhari

← Rev. 6 →

+23

For E2, there is a much simpler code arising from the result of an inequality.

We can just iterate through the values of p. For each p, we need to check for only a single value of k which is floor(n^(1/j)). This is the only possible value of k that may satisfy the condition for a given value of p. This is because:

k^p < 1+k+(k^2)+....+(k^p) < (1+k)^p implies k < (1+k+(k^2)+....+(k^p))^(1/p) < 1+k

If n is equal to 1+k+(k^2)+....+(k^p), then k should be less than n^(1/p) and as per the above inequality k should be floor(n^(1/p)).

Here's the code.

A very effective and simple approach, many thanks !!

wsy123

e2 is yituodabian

BODH

e2 hao nan

So we can take one medicine multiple times in G?

vgtcross

← Rev. 9 →

+20

It doesn't matter if it's allowed or not since it would never actually be useful to take the same medicine multiple times anyway.

I claim that if there is a sequecne of medicine that removes all symptoms and medicine $$$x$$$ is used multiple times, we can keep the last occurrence of $$$x$$$ and remove all earlier ones, and the sequence stays valid.

Proof: Consider the symptoms medicine $$$x$$$ cures. It doesn't matter if these symptoms are cured or not before the last occurrence of $$$x$$$ since the last time of taking medicine $$$x$$$ cures these symptoms anyway. Thus, taking medicine $$$x$$$ also earlier has no effect.

Now consider the symptoms medicine $$$x$$$ gives. It doesn't matter if these symptoms are cured or not before the last occurrence of $$$x$$$ since taking this medicine will give these symptoms anyways, and they need to be cured later. Thus, taking medicine $$$x$$$ also earlier has no effect.

This means that taking medicine $$$x$$$ also earlier than the last occurrence has no effect on any symptoms. $$$\square$$$

Thanks a lot for the proof, its crystal clear!

kevintooorz

this round has really weak testcases. It's not only for B and C, but also for G. This is my submission for G, in no way should it pass but still it passes.

Your solution is fine (why I don't know), check the announcement page someone explained why this works

tosivanmak

ummm... the solution takes at most 20 medicine.

Yes, but your solution is still correct. It can be shown that we never need more than 10 medicine to get fully cured, here is a short explanation (without proof). I can provide a proof if you can't see why that is true.

syxwz

I failed five times on E2. But G is a piece of cake,because UVA658 is quite similar to it.

aayush249

My Solution Pretty sure , I have the same solution as that of the editorial . Dunno why I got the TLE though

use c++

Nxxlt

Use fast input. Passed in 202 ms. Code: 215151784

aradhyeagarwal

Any idea why this submission is giving a WA for D? I have just subtracted the overlapping area instead of using the trapezium formula.`

https://codeforces.com/contest/1846/submission/212715188

olegmak

setprecision() goes before output we set precicion for

v_i_sh_a_l

In problem G, what if Rudolf cannot transition from the initial state to a specific state using a particular medicine, but can still alleviate symptoms one by one?

dhruv1807

1846-C - Rudolf and the Another Competition

Any idea why my submission gets a TLE here. Time complexity is O(n*mlogm). 212937677

Spoiler

import sys

from os import path

input = sys.stdin.readline

if(path.exists('input.txt')): sys.stdin = open("input.txt","r") sys.stdout = open("output.txt","w")

def listInp(): return list(map(int,input().split()))

def mapInp(): return map(int,input().split())

for _ in range(int(input())):

n,m,h = mapInp()

data = []

for i in range(n):
    data.append(sorted(listInp()))

psums = []

for i in range(n):
    x = [0]
    for j in range(m):
        if data[i][j] + x[-1] <= h:
            x.append(data[i][j] + x[-1])
        else:
            break

    psums.append([len(x)-1,sum(x),i])

psums.sort(key=lambda x:(-x[0],x[1]))

# print(psums)

for i in range(n):
    if psums[i][2] == 0:
        print(i+1)
        break

hukevraainy

can python sqeeze through C and D without TLE?

here's my code and they seem to not work even tho the complexity is exactly identical to the editorial

https://codeforces.com/contest/1846/submission/212613024 (C)

https://codeforces.com/contest/1846/submission/212645926 (D)

an explanation or help would be wonderful.

1xx55

For D you can see my submission here 212968791 (I just change your code a little and get accepted)

thanks man. Apparently storing it in an array doesn't work as fast as I thought

0x81

Del.

bidvamaxim

My solution in B does not require a review of 4 cases.

MichaelR.Moussa

well , i am still a beginner, but in problem 3 ... i don't get how did we store the solution times for each student by this :

for(int i = 0; i < n; i++){ vector cur(m); for(int j = 0; j < m; j++){ cin >> cur[j]; }

while this should only store the last student only since it overwrites the existing values in each new outer loop ?

You're correct; this only stores the solution times for the last student. But notice that right after reading this, we already handle this student by calculating the optimal number of problems and minimum time penalty for this student. Thus, we don't need to store the problem-specific times for any longer and they can be overwtitten by new data.

H3l10816107

if (i){
     if (make_pair(-task_cnt, penalty) < rud) ans++;
} else rud = {-task_cnt, penalty};

how does this work in C solution given in the editorial?

fx_6300

make_pair(-task_cnt, penalty) is used to create a pair with two values: -task_cnt and penalty. The negative sign before task_cnt is used to ensure that when comparing pairs, the pair with a smaller task_cnt value takes higher priority. If the -task_cnt is equal for two pairs, the comparison will be based on the penalty value. This pair is used for comparison in the following line:

pgiaminh8368

-8

212951522 For problem F, why does this code give Idleness Limit Exceeded

You output mimic position before reading full response from OJ

ankitghanghas1072

In E2, can somebody tell me the value of k that satisfy 29th test case i.e. n = 64000160000400001, I think this test case is wrong.

+16

400,000

Krzychuo

Dial's algorithm can be used in G to achieve $$$O(2^n \cdot (m + MAXd))$$$ complexity. 212963777

Cuz the range of weight of a edge is 10^3(d) and there is 1024 vertices at max, so Dial's algorithm work fine but not more effective than Dijkstra's algorithm with STD in C++.

AvikAB

Amazing problemset. Anyone easily can hacks.(hahaha)

I did think about BS at E2 in the cts, but I couldn't go with that, someone please tell me the editorial of that solution, I really need it. Thank you.

Assume that we have an array {$$$a_k$$$} satisfied $$$a_k = k^2+k+1$$$ , then we can see $$${a_k}$$$ is increasing when k increases. So BS works on this array. We can use BS to check whether the given $$$n$$$ is in {$$$a_k$$$}.Pick $$$l$$$=2 and $$$r$$$=minimum $$$k$$$ satisfied $$$a_k > 10^{18}$$$ and BS.Then we can check $$$b_k = k^3+k^2+k+1 $$$ , $$$c_k = k^4+k^3+k^2+k+1 $$$ ... till $$$A_k = k^{63}+k^{62}+...+k+1$$$ .If the given $$$n$$$ doesn't stay in the arrays mentioned above , the answer is "NO".

You don't really need to construct these arrays and store the value of them (MLE) , just calculate $$$a_{mid}$$$ and compare $$$a_{mid}$$$ with the given $$$n$$$ .

Thank you so much, I wish you best in the next contest <3

YoMamaLover

In problem G, you should have mentioned that you can use a medicine several times because without it the problem seems quite complicated. By the way, does anyone know if it's possible to solve the problem if we can use each medicine only once?

CandidateMasterHuMaiAab

this is my submission for this problem submission. When we use one medicine at a time then we just have to make the following change in the code

I just swapped the two loops of dp just like we do in coin change dp problem.

_MASTER__

check this

seanpinyo

For problem E? How do we obtain the maximum possible value for k

yuuma

Try to solve E2 with binary search, Don't know what I've missed

https://codeforces.com/contest/1846/submission/212862518

Line 11: i<62

It should be i<64 i think

abcsumits

← Rev. 4 →

this solution is accepted in e1 but not in e2,provide me some reason, let n=1+x+x^2......+x^i ------ eq(1) now, we know, x^i<n<(x+1)^i (by binomal theorm) that, means x<n^(1/i)<x+1, now x can be gif(n^(1/i)), we will satisfy eq(1) with x, if it is true ans exist. we will do it for i between 2 to 61.

Hey your solution is too slow, the bound for the largest power is incorrect as well, check for i<=63, since 2^63~1e18, it will still tle with the current solution though, check this for an alternate approach my approach

it would be 60, and now it's tle, but complexity for each case woould be logn*logn*60

By your approach right, mine is a simple binary search that's just logn*63

my solution is giving tle now :(

your apporach is logn*logn*60 too

How is this 212715312 logn*logn*60?

leave it i have used inbuilt pow function in python

X_60tp_lew

Oooh, F was sooo easy, why I didn't read it during the contest:(

ducmatgoctoanlyhoa

I'm not sure about this, but for E1 (and maybe E2 for some $$$n$$$ not too large), since $$$n = 1 + k + k^2 + k^3 + \dots$$$, we would have $$$k$$$ be a divisor $$$(n - 1)$$$, and we can iterate all such k, noting that for some integer $$$p \geq 2$$$ (if it exists):

$$$ n = 1 + k + k^2 + k^3 + ... + k^p \\ \rightarrow n = \frac{k^{p + 1} - 1}{k - 1} \\ \rightarrow k^{p + 1} = n(k - 1) + 1 \\ \rightarrow p = log_k{(n(k - 1) + 1)} - 1$$$

We only need to check if $log_k{(n(k - 1) + 1)} - 1$ is an integer and if it is larger to equal to $$$2$$$ using repeated division, since the float log function can be expensive:

有人吗

为什么使用等比数列预处理会WA？

Vinayak286

In E2 , for n greater 1e12 we can directly use Shree Dharacharya formula to know whether a k exist or not. And for k from 1 to 1e6 we can make a set of sum of G.P . I got this intuition in the contest but was getting TLE while calculating the sum of G.P . :( Got accepted in 1 try post contest.

need help of E2 , don't know why can't pass test 9 :(( please help , thx a lot! 213588968

if (p > (long long)(1e18) / k) break; Why this statement is necessary in E2

Ahmed_Solyman

Why there is Rudolph and Rudolf?

cftryharder

9 months ago, # |

Can somebody help me to spot why is giving Idleness Limit Exceeded?

https://codeforces.com/contest/1846/submission/213728138

I've tried several things, but still can't find the issue.

arpcode

Same bro, did you find the issue?

No, I haven't found it yet. I've stopped debugging it for some days as well

ethanhunt1729

my very easy to understand solution for E2,#213938261

I think this thing is simpler than editorial in G problem. Call the current status is S, the good effect is A, the bad effect is B. So when you take a medicine, the status transform S & (~A) | B

HelloFromUnknown

I am getting WA on test case 2 for n = 7 in my submission for E1. I have tried my solution on my local also on the online available gnu c++ compiler it is giving correct answer that is "YES" while when I run it on here it give WA. I am not able to get why so? If anyone here can help me, I will be very thankful to him.

fhritp

Sorry for posting this late, can someone please tell why this gives wrong answer in problem E1 test 2, my approach instead of searching for the exponent I used log to find it, any help would be appreciated, Thanks in advance.

armurox

Hi, could anyone help debug my submission? This is for 1846B. My submission is https://codeforces.com/contest/1846/submission/214305302

Thanks in advance!

Arnur2937

Note that after finding a winner when you check rows and columns, you just break for loop, meaning you are checking diagonals even if you found the winner.

Yup, got it, thanks so much!

hhc0716

What a deceitful problem C!

what is k for 1000015000057 in 11th test in E2?

tr1ten

7 months ago, # ^ |

K=1000007 level=1

thanks

Why do I get a Idleness Limit Exceeded on my code for F? [Code] Please help

MiyawakiSakura

Your code didn't link

MickeyIsAwesome

Hello guys, in 1846F - Rudolph and Mimic, continously getting time limit exceeded, even though I have verified my solution with editorial, and have tried to match it to the author's solution. Can anyone please let me know what could be the issue here :( -> 216464518

RohanJha23

Can anyone tell me why my Code is giving an output of 3 whereas the required output is supposed to be 2 for the following test case(Test Case number 2 — Problem 13).

217202106

Test Case:

5 5 14

7 2 9 10 3

5 3 2 9 7

6 1 10 5 7

2 6 9 10 4

10 5 7 8 9

ja_g_an

8 months ago, # |

why this 221034056 isn't working for c am i missing something

Me_Happy_Me_No_Sad

7 months ago, # |

I did solve G without using Dijkstra is it hackable?

my idea to use dp is either i take the element either not i know sometimes you'll be forced to take medicine two times or 3 ...

but what i did that i did push the element n*m times so that max number we take that element is n times no more that that is that true? https://codeforces.com/contest/1846/submission/223492698

alpha1215

3 months ago, # |

alternate dp solution for G

code

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << << nl;
    int n, m; cin >> n >> m;
    string ds; cin >> ds;
    int dsn = 0;
    for(int b = 0; b < n; b++) {
        if(ds[b] == '1') dsn |= 1 << b;
    }
    vector<array<int, 3>> med(m);
    for(int i = 0; i < m; i++) {
        cin >> med[i][0];
        string cure, dis; cin >> cure >> dis;
        for(int b = 0; b < n; b++) {
            if(cure[b] == '1') med[i][1] |= 1 << b;
            if(dis[b] == '1') med[i][2] |= 1 << b;
        }
    }
    if(dsn == 0) {
        cout << 0 << nl; return;
    }
    vector<int> dp(1 << n, INT_MAX);
    for(int i = (1 << n) - 1; i >= 0; i--) {
        if((i | dsn) == i) dp[i] = 0;
    }
    for(int i = (1 << n) - 1; i >= 0; i--) {
        for(auto& a : med) {
            if((i | a[2]) == i && dp[i | a[1]] != INT_MAX) dp[i] = min(dp[i], dp[i | a[1]] + a[0]);
        }
    }
    cout << (dp[0] == INT_MAX ? -1 : dp[0]) << nl;
}   

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

J_Jain

4 days ago, # |

1846G is really a nice question,lovely

natalina's blog