Автокомментарий: текст был обновлен пользователем natalina (предыдущая версия, новая версия, сравнить).

HacksForces

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$$$.

E2 is a superb binary search question, liked it

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

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

В задаче Е1 также удобно порассуждать через системы счисления. Если n = 1 + k^2 + k^3 +... ,то можно сказать, что n — десятичное число, состоящее в системе счисления с основанием k только из цифр 1. Таким образом, можно свести задачу к проверке: можно ли подобрать основание системы счисления k для числа n такое что запись числа в этой системе будет состоять только из 1. Т.к. "минимальная" снежинка у нас состоит из 1 + k + k^2 вершин, то k гарантированно меньше sqrt(n). Полный перевод числа в систему счисления с основанием k осуществится в худшем случае за 20 шагов (2^20 > 10^6). Но, конечно, если по ходу перевода встретим не 1, то дальше проверять это k нет смысла и можно переходить к следующему)

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.

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.

#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;
}

e2 is yituodabian

So we can take one medicine multiple times in G?

Задачи интересные, только не понимаю почему людям так не нравится бэшка...

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.

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

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

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

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?

1846-C - Rudolf and the Another Competition

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

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

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.

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

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 ?

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

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.

can someone explain me the problem D in c++? I don't really get the idea of it, thank you in advence

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

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.

can anybody tell me what is wrong with this submission for F.

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?

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

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

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

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.

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

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):

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:

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";

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?

有人吗

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

#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;
}

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

why there is Rudolph and Rudolf?

why there is Rudolf and Rudolph?

Why there is Rudolph and Rudolf?

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.

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

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.

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.

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

Thanks in advance!

What a deceitful problem C!

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

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

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

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:

1

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

Как сбросить буфер вывода в C#? С Console.Out.Flush() после каждого вывода получаю ошибку исполнения.

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

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

alternate dp solution for G

#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);
}

can someone tell me how to assume the probable time complexity require for a particular problem . for example in Q C , n and m are given in range of 1e5 still we can solve it in O(N*M*logM) time complexity how ?

1846G is really a nice question,lovely