For B, instead of going for every number, we can move at intervals of 9 probably?

My solution for B question has complexity O( k * (log(2 * 10^7)[base 9]) * 10 ).

Source code: link

Is this the optimized one that you are talking about @jinlifu1999

For B, Bonus1: Iterate from 1 and for every number n whose sum of digits is less than 10, answer is concatenation of n and 10 - sum(n). This is 10 times faster than mentioned brute-force.

Submission

jinlifu1999

http://mirror.codeforces.com/contest/919/submission/34773513

http://mirror.codeforces.com/contest/919/submission/34770710

Same Solution. Different Verdict . What type of Judge ?

The k=1 case in problem C does hurt lol. Got hacked, though my code is fairly straightforward still.

Also, is it a right way to solve D by merging strongly-connected components into one node and do the calculations? Just discussed with my friend and I haven't tried this approach.

To be precise complexity of brute force in B is O(ans * log(ans)) :D

Разве при n>=p уравнения может быть верной ? ведь уравнения n*a^n mod p = b при n>=p можно представить так => (p+(n-p))*a^n mod p = b отсюда (p*a^n + (n-p)*a^n ) mod p = b а это можно представить так => ( p*a^n mod p + (n-p)*a^n mod p ) mod p =b => (0 + (n-p)*a^n mod p) mod p =b
= > ( (n-p)*a^n mod p ) mod p =b => (n-p)*a^n mod p =b , а если (n-p)>=p то можно сделать точно самое еще раз

CANNOT UNDERSTAND WHAT IS WRONG WITH THIS CODE..ITS GIVING 0.00000 for the first test case...works fine on my compiler

include<stdio.h>

int main()
{
    double n,m,a,b;
    int i;
    double min=100000;
    scanf("%lf%lf",&n,&m);
    for(i=0;i<n;i++)
    {
            scanf("%lf%lf",&a,&b);
            double c=m*(a/b);
            if(c<min)
            { 
                        min=c;
            }
    }
    printf("%lf\n",min);
return 0;
}

Please add Tutorial for Problem F as well.

FOR PROBLEM B hehe i stuck in the optimisation for this code ignoring that brute force can be run easily for this code ..i was just trying that for a no < 100 starting from ...

19 add 9 for every no to be build which is a perfect positive integer and for 91

ADD 18 to get 109 then again add 9 .... to get the last 190 then add again 18 to obtain 208 then add 9..... finally till now the factor which we are adding to obtain next term is 18 ..now when 208 is added with 9 so and so on till 280 is reached then increment factor with 9 and add 280+(18+9) since prev value of factor is 18 update it to 18+9

to obtain 307 goes till this series

until the last series becomes like this 901 910 then here factor will be 81

but for next term add (81 not with 9 but with 18) to get 910+(81+18) = 1009

then make factor -> 0 and again keep adding 9 to the nos till 1090 is reached then do the above firstly mentioned steps .. that is 1090+(factor+18) to get 1108 then add successivley 9 til 1180 is not reached and then factor will always be updated by 9 that is 1180+(value of factor till here +9) to get new value of next term having sum = 10

perform this till the new 2 term series is not obtained .. I have observe many things about numbers regarding this question but i am so sure some of the cases might not fit in my factor adding approach because in some cases i observed like 1801 1810 (when series like this ) i cant add 1810+(val of factor till here + 18) since it will not yield me the perfect positive integer some other cases also are hot handled by my optimisation but i want that someone plzz understand this and can do further optimise it without using brutforce till 1000000000000(as an estimate no)

Because this code will runs in O(k) iterations rather than some large estimate . Plzz ignore me if i said something wrong . plzz give feedback thnkss

can anyone please tell why am I getting TLE(in 15th test case) IN 4TH question ?

https://ideone.com/Kpl1jy

can anyone explain why I am getting tle on test case 32 in problem d(Java)? http://mirror.codeforces.com/contest/919/submission/34773289

update: same c++ solution of mine is got accepted but it is giving tle in java. link to c++ code http://mirror.codeforces.com/contest/919/submission/34778298

There should be a nice and fairly easy solution for problem E with generators (prime roots). We know which power of g is a, which one is g, so we are just left with a simple congruence on exponents. Finding stuff can be done in O (p) instead of writing some sqrt algorithms, because p is nice

Is the brute-force for B really O(answer)? I mean.. computing the sum of digita on n takes log(n) time does it not?

Can somebody elaborate on Div2E

I seem to be deriving j - i ≡ b·a^- j(mod p)

Thanks!

Edit: They edited the editorial, all clear now :)

Can someone tell me why my submission for C fails in TC 32 ?

My solution here for B is

34769949

First, let’s binay search the answer x

Then our job is to check if there are more than k perfect numbers less than x

Let f(i,j) represent for the previous i digits, the sum is j, how many numbers can we have. Which is a classical digital dp.

I was retarded during the contest and thought k was smaller than 1e5, that’s why I solved B last and didn’t work out E, R.I.P.

Why my code for D is giving wrong answer in TC 7. I used dfs to count the frequency in every path. In the worst case scenerio my code should give TLE, but I can not comprehend why it is giving me wrong answer. Here is my implementation.

I hacked 2 people in problem C, because they're not careful when k=1.

I use dfs+dp in problem D. Dfs to find cycle. When there is a cycle, I will output -1. Dp to calculate which is the maximum number.

You needn't judge every number in problem B. You only need to judge x which x%9==1.

Can someone tell me why my solution for D fails?

What's wrong with this code?

460C

Problem E was such a nice number-theory problem for beginners :D

In problem E, the 'looping' mentioned in the editorial mod p(p - 1) can be proved.

From Euler's Theorem, , for any integer n. Since φ(p) = p - 1, we only need to consider powers of a ranging from 0 to p - 2. This gives us two congruences:

This system of congruences then has a unique solution mod p(p-1)), by the Chinese Remainder Theorem, which gives us the 'looping'.

Edit: Fixed formatting and notation: Fermat's Little Theorem -> Euler's Theorem.

Edit 2: The proof also gives a way to solve the problem using the Chinese Remainder Theorem, which is slightly different from the method mentioned in the editorial in its approach.

The idea follows directly from above: for each $i$ from 0 to p - 2 the above system of congruences can be solved uniquely mod p(p - 1), and the contribution of each of these to the final answer can be counted easily.

See 34764463.

Can anyone please help with Problem D... this solution is giving wrong on test 7.

The test case is huge to manually check it.

Thank you

http://mirror.codeforces.com/contest/919/submission/34794840

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

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

Can Someone please Explain E from expressing n as i*(p-1)+j.

Thank you.

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

Can you please explain how did you get C(m+k-1,k) in F?

hey! can you please explain why i got a TLE error on this code? it seems pretty optimized to me! thanks :)

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef vector<int> vi;
typedef set<int> si;
typedef vector<si> vsi;

vsi edge;
vector<char> nodes;
vector<int> visit;
int maxnum = -1;
bool cycle = 0;

void dfs(int cur, vi dp)
{
    visit[cur] = 1;
    if(maxnum < ++dp[nodes[cur]- 'a']) maxnum = dp[nodes[cur]- 'a'];
    for(auto i: edge[cur])
    {
        if(cycle == 1) return;
        if(visit[i] == 1)
        {
            cycle = 1;
            return;
        }
        dfs(i, dp);
    }
    visit[cur] = 2;
}

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    visit.resize(n);
    edge.resize(n);
    vi inedge(n);
    for(int i = 0; i < n; i++)
    {
        char c;
        cin >> c;
        nodes.push_back(c);
    }
    for(int i =0; i < m; i++)
    {
        int x,y;
        cin >> x >> y;
        if(x == y) cycle = 1;
        else
        {
            edge[x-1].insert(y-1);
            inedge[y-1] = 1;
        }
    }
    vi dp(26);
    for (int i = 0; i< n; i++)
    {
        if(visit[i] == 0 && inedge[i] == 0) dfs(i, dp);
        if(cycle == 1) break;
    }
    if(cycle == 1) cout << -1;
    else cout << maxnum;
    return 0;
}

What is looping section in problem E editorial??

For F,this is what you said: "First we should notice that the useful number of states isn't something like (8^5)^2" Maybe it isn't something like (5^8)^2,right?

can someone help me out ? I submitted problem D with my data structures statically sized using SIZE.I got MLE when my SIZE was 1000005 in the 6th test case. but when i changed it to 300005 I got AC. my question is , why didn't i get MLE in the first test case itself as the data structures are static? MLE :34803955 AC :34804264

Can anybody give a proof why Problem D can't be solved using only DFS?. Keep counting the frequency of each letter in the traversal and record the maximum. -1 if cycle is found. I haven't solved it yet, but was wondering. Thanks

In problem F, how to deal with cycles?

In problem F,when current status is in circle,but I have other succeed status which are all lose states.Maybe I can go into one of the lose states and win instead of make it deal.With topological sort we can have the correct answer for this status,but what about the previous status?The previous status maybe not visited.How to deal with this problem?

For Problem B. My Solution. Instead of iterating each and every value of n, I am finding the next Perfect Number in each iteration.

It came as a surprise to me when I found out k=1 was NOT in the pretests for problem C. I thought about trying to look for solutions which didn't treat this case but I thought surely it must have been in the pretests (usually pretests contain small cases like n = 0, 1, 2) so I decided to pass (I usually never go for hacks anyway, I prefer trying to solve more problems).

Why the graph we built in F don't have any circle?

For problem F bonus, the answer is the number of non-negative integer solution of x₀ + x₁ + x₂ + x₃ + ... + x_m - 1 = k.

It seems to be , and the number of status in the problem F is instead of 245025, right?

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

In the 2nd question, the code I've written works perfectly on my system, but when I uploaded it, it showed me a wrong answer. After the contest, when I executed the test case which went wrong on my own system, it showed the correct answer. Could anyone please help me in identifying the mistake?

1st submission: http://mirror.codeforces.com/contest/919/submission/35751191

^ Passed only the first test case

2nd submission: http://mirror.codeforces.com/contest/919/submission/35751331

^ passed two test cases, even though I changed just the starting number, from 19 to 1

both the codes are working perfectly on my system

D is noice

For question F I am not quite sure why we had to run BFS (topological sort) on the graph? It is certainly cyclic. I tried DFS and got stack overflow but I am still not very sure where we got the idea to run the BFS from.

I started E without the assumption that p is prime(didn't read the question well) and voila! with 100% certainity that the answer was gonna be wrong yet submitted to find an AC!.

In problem E, there is a new algorithm that is newly developed called: "Chinese Reminder Theorem"

if anyone is looking for a digit dp solution for problem B then you can refer to submission

for further bigger value of k, you can also use BigInteger along with StringBuilder.