Codeforces round 883 Editorial

1846A - Rudolph and Cut the Rope

Author: Sasha0738

1846B - Rudolph and Tic-Tac-Toe

Author: Sasha0738

1846C - Rudolf and the Another Competition

Author: vladmart

1846D - Rudolph and Christmas Tree

Author: vladmart

1846E1 - Rudolf and Snowflakes (simple version)

Author: natalina

1846E2 - Rudolf and Snowflakes (hard version)

Author: natalina

1846F - Rudolph and Mimic

Author: Sasha0738

1846G - Rudolf and CodeVid-23

Author: vladmart

• 8 months ago, # ^ | Hahaha

  • 60 minutes ago, # ^ | Hahaha Hahaha

• 8 months ago, # ^ | Great!

• 8 months ago, # ^ | 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 ?

  • 8 months ago, # ^ | Sure! I assume you meant ,not . If you deal with all (for example by precalculating a set of valid numbers),for all other the exponent must be exactly . That is because the minimmum exponent is and if the exponent was the sum would be larger than .Now we have to check that there exists a such that . This is the same as checking if there is a such that . Now, let . It is easy to see that . However, must be as large as possible so is either or when is a perfect square.

    • 8 months ago, # ^ | 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.

      • 8 months ago, # ^ | Because for n <= 1018 and p = 2 the value of k could be approximately sqrt(n) = 109. But we can precalc values only for k <= 106

        • 8 months ago, # ^ | 1+k+k^2=n how do we get to this ?

          • 8 months ago, # ^ | 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.

• 8 months ago, # ^ | Very inefficient approach. It can be done with binary search sir !!!

  • 8 months ago, # ^ | ← Rev. 2 →   0 I did think about BS in the cts, but I couldn't go with that, can you tell me that solution ?

• 8 months ago, # ^ | can u explain "if (p > (long long)(1e18) / k) break;" Why this statement is necessary?

  • 8 months ago, # ^ | ← Rev. 2 →   0 The if statement is necessary because otherwise the sum could overflow. If you have to check if , a neat way of doing this and avoiding overflow is checking if . Hope this helps!

    • 8 months ago, # ^ | Thank u for your reply, i got it:)

• 7 months ago, # ^ | You don't need to check . Let . For to be , . Let . The question is: which numbers of the form , do we need to check? Substituting in , we get . Note that must be , as . We need to show that if , , so can't equal . Note , otherwise would be negative. Let . Substituting, we get If , , as and .

  • 7 months ago, # ^ | 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 : I claim that for any number such that . When and when . Because is either or than ,we can conclude that .

• 8 months ago, # ^ | I did think about BS in the cts, but I couldn't go with that, can you tell me that solution ?

  • 8 months ago, # ^ | 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.

    • 8 months ago, # ^ | Can you please explain the concept of n^(1/p). I am not getting this part.

      • 8 months ago, # ^ | 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.

        • 8 months ago, # ^ | got it,thanks.

• 8 months ago, # ^ | I don't know why I can't pass test9 :(((

• 8 months ago, # ^ | 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...

• 8 months ago, # ^ | Precision is set before the solution code at the beginning of the main function

  • 8 months ago, # ^ | wow didn't notice. nice info ty

• 8 months ago, # ^ | it's your fault

  • 8 months ago, # ^ | It's plateform fault because it is showing correct how can I know it fails on some test case

    • 8 months ago, # ^ | After contests end more tests are added

    • 8 months ago, # ^ | 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.

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

• 8 months ago, # ^ | A very effective and simple approach, many thanks !!

• 8 months ago, # ^ | e2 hao nan

• 8 months ago, # ^ | ← 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 is used multiple times, we can keep the last occurrence of and remove all earlier ones, and the sequence stays valid. Proof: Consider the symptoms medicine cures. It doesn't matter if these symptoms are cured or not before the last occurrence of since the last time of taking medicine cures these symptoms anyway. Thus, taking medicine also earlier has no effect. Now consider the symptoms medicine gives. It doesn't matter if these symptoms are cured or not before the last occurrence of since taking this medicine will give these symptoms anyways, and they need to be cured later. Thus, taking medicine also earlier has no effect. This means that taking medicine also earlier than the last occurrence has no effect on any symptoms.

  • 8 months ago, # ^ | Thanks a lot for the proof, its crystal clear!

• 8 months ago, # ^ | Your solution is fine (why I don't know), check the announcement page someone explained why this works

  • 8 months ago, # ^ | ← Rev. 2 →   0 ummm... the solution takes at most 20 medicine.

    • 8 months ago, # ^ | 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.

• 8 months ago, # ^ | use c++

• 8 months ago, # ^ | Use fast input. Passed in 202 ms. Code: 215151784

• 8 months ago, # ^ | setprecision() goes before output we set precicion for

• 8 months ago, # ^ | For D you can see my submission here 212968791 (I just change your code a little and get accepted)

  • 8 months ago, # ^ | thanks man. Apparently storing it in an array doesn't work as fast as I thought

• 8 months ago, # ^ | ← Rev. 3 →   0

• 8 months ago, # ^ | 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.

  • 8 months ago, # ^ | 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?

    • 8 months ago, # ^ | 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:

• 8 months ago, # ^ | You output mimic position before reading full response from OJ

• 8 months ago, # ^ | 400,000

• 8 months ago, # ^ | 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++.

• 8 months ago, # ^ | ← Rev. 2 →   0 Assume that we have an array {} satisfied , then we can see is increasing when k increases. So BS works on this array. We can use BS to check whether the given is in {}.Pick =2 and =minimum satisfied and BS.Then we can check , ... till .If the given 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 and compare with the given .

  • 8 months ago, # ^ | Thank you so much, I wish you best in the next contest <3

• 8 months ago, # ^ | ← Rev. 2 →   +8 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 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]); } } } I just swapped the two loops of dp just like we do in coin change dp problem.

• 8 months ago, # ^ | ← Rev. 2 →   0 Line 11: i<62 It should be i<64 i think

• 8 months ago, # ^ | ← Rev. 2 →   0 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

  • 8 months ago, # ^ | ← Rev. 4 →   0 it would be 60, and now it's tle, but complexity for each case woould be logn*logn*60

    • 8 months ago, # ^ | By your approach right, mine is a simple binary search that's just logn*63

      • 8 months ago, # ^ | my solution is giving tle now :(

      • 8 months ago, # ^ | your apporach is logn*logn*60 too

        • 8 months ago, # ^ | ← Rev. 2 →   0 How is this 212715312 logn*logn*60?

          • 8 months ago, # ^ | leave it i have used inbuilt pow function in python

          • 8 months ago, # ^ | 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")

• 7 months ago, # ^ | Same bro, did you find the issue?

  • 7 months ago, # ^ | No, I haven't found it yet. I've stopped debugging it for some days as well

• 8 months ago, # ^ | 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.

  • 8 months ago, # ^ | Yup, got it, thanks so much!

• 5 months ago, # ^ | K=1000007 level=1

  • 5 months ago, # ^ | thanks

• 7 months ago, # ^ | Your code didn't link