I am an iOS developer, in my leisure time i solve coding problem in leetcode using swift language. But my most favourite site codeforces doesn’t support swift language. So i would like to request codeforces software engineers to add swift support. Thanks.

I implemented it using min_heap instead of using built in priority queue. Test case 32 is very long and it is hard to guess. Please give me a test case which my code would fail:

vector<int> edge[100002];
vector<int> cost[100002];
int par[100002];
long long dis[100002];
 
struct customDataType {
    int node;
    long long mincost;
    customDataType() {}
    customDataType(int x,long long y) {
        node=x;
        mincost=y;
    }
};
 
customDataType heapArr[3000001];
 
 
bool heapEmpty() {
    return heapArr[1].node==INT_MAX;
}
 
void push_heap(int node,long long cst,int& index) {
 
    if(heapArr[index].node!=INT_MAX)
        index++;
 
    heapArr[index]=customDataType(node,cst);
 
    int i=index;
    while(i/2>=1 && heapArr[i/2].mincost>heapArr[i].mincost) {
        swap(heapArr[i/2],heapArr[i]);
        i/=2;
    }
 
    index++;
}
 
void pop_heap(int& index) {
 
    if(heapArr[index].node==INT_MAX)
        index--;
 
    heapArr[1]=heapArr[index];
    heapArr[index]=customDataType(INT_MAX,INT_MAX); ///deleted
 
    int i=1;
    while(min(heapArr[i*2].node,heapArr[i*2+1].node)!=INT_MAX && min(heapArr[i*2].mincost,heapArr[i*2+1].mincost)<heapArr[i].mincost) {
 
        if(min(heapArr[i*2].mincost,heapArr[i*2+1].mincost)==heapArr[i*2].mincost) {
            swap(heapArr[i*2],heapArr[i]);
            i*=2;
        } else {
            swap(heapArr[i*2+1],heapArr[i]);
            i=i*2+1;
        }
 
    }
 
    index--;
}
 
void dijkstra(int src) {
 
    int curr=1;
    dis[src]=0;
    push_heap(src,dis[src],curr);
 
    while(!heapEmpty()) {
        customDataType U=heapArr[1];
 
        pop_heap(curr); /// curr is the last inserted value .
 
        for(int i=0; i<edge[U.node].size(); i++) {
            int V=edge[U.node][i];
            long long dstance=U.mincost+cost[U.node][i];
 
            if(dis[V]>dstance) {
                dis[V]=dstance;
                par[V]=U.node;
 
                if(curr==0) /// priority queue is now empty , so start from 1.
                    curr=1;
 
                push_heap(V,dis[V],curr);
            }
 
        }
 
    }
 
}
 
void path_print(int u) {
    if(u==1) {
        printf("%d ",u);
        return;
    }
 
    path_print(par[u]);
    printf("%d ",u);
}
 
void debug(int n){
  puts("");
  puts("");
   for(int i=1;i<=n;i++){
      printf("%d: ",i);
 
      for(int u: edge[i])
            printf("%d ",u);
 
      puts("");
   }
 
   puts("");
 
   for(int i=1;i<=n;i++){
      printf("%d: ",i);
 
      for(int u: cost[i])
            printf("%d ",u);
 
      puts("");
   }
 
}
 
int main() {
 
    int n,m,u,v,w;
 
    while(cin>>n>>m) {
 
        for(int i=1; i<3000001; i++) {
            heapArr[i].node=INT_MAX;
        }
 
        for(int i=1;i<100002;i++){
            dis[i]=LLONG_MAX;
            edge[i].clear();
            cost[i].clear();
        }
 
        while(m--) {
            scanf("%d %d %d",&u,&v,&w);
            edge[u].push_back(v);
            cost[u].push_back(w);
 
            edge[v].push_back(u);
            cost[v].push_back(w);
        }
 
//        debug(n);
 
        dijkstra(1);
 
        if(dis[n]==LLONG_MAX)
            puts("-1");
        else {
            path_print(n);
            printf("\n");
        }
 
    }
 
 
 
    return 0;
}

We know that builtin_popcount returns the number of 1 bits in a number . For example: Binary representation of 5 is 101 and __builtin_popcount(5) will return 2 .

But how it works for negative number ? for example:

1. Binary representation of -8 equals = 1000 but __builtin_popcount(-8) returns 29 . Shouldn't it be return 1 ? Because there are one '1' bits in -8 .

2. Binary representation of -7 equals = 1001 but __builtin_popcount(-7) returns 30 . Shouldn't it be return 2 ? Because there are two '1' bits in -7 .

3. Binary representation of -6 equals = 1010 but __builtin_popcount(-6) returns 30 . Shouldn't it be return 2 ? Because there are two '1' bits in -6 .

4. Binary representation of -5 equals = 1011 but __builtin_popcount(-5) returns 31 . Shouldn't it be return 3 ? Because there are three '1' bits in -5 .

Or __builtin_popcount(x) works only for positive numbers?

Very often we use map c++ and solve many complex problem easily . But what if i am not allowed to use any stl and i have to implement map::std c++ by myself . Which data structure should i use ? Should i use Red black tree ? Is it really possible to implement map using red black tree ? If there are alternative way then tell me .

In a problem i needed just unique elements , so i used set but got time limit exceeded but Later used vector unique + resize() and got AC . I don't know how is this possible , because both code has time complexity of O(nlog(n));

    set<int> st;
    
    for(int i=0;i<n;i++)    
         st.insert(i); // log(n)

This code time complexity: O(nlog(n+container size) )

===================================================================================

       vector<int> vct;       
       for(int i=0;i<n;i++)
         vct.push_back(i);
       
       sort(vct.begin(),vct.end());  // nlogn
       auto it=unique(vct.begin(),vct.end()) ;  // n
       vct.resize(it - vct.begin() ); // n

This code time complexity: O(nlog(n) + n + n) which is approximately equals to O(nlog(n) + n) . Am i wrong in calculating Time Complexity? nlogn for sorting and one n for unique function call , another n for resize() method call

So , O(nlog(n+container size) ) is almost equals to O(nlog(n) + n) but why they depicts different scinario ?

I want to solve this problem 1175C -Electrification , using binary search but got stucked . I checked many code of red coders whom used binary search . But it is hard to guess the logic from code . Can anyone explain what is the binary search approach ?

I tried myself using binary search . My approach was: just pick an mid , f2(mid) <= f2(mid+1) that means all values from mid+1 to high are greater , so high=mid . Else low=mid;

Here f2(x) function takes a value and push all abs(ar[i]-x) to vector then sort it and return kth value [hence i used 0 based index] .

This code fails when f2(mid)==f2(mid+1) .

vector<int> vct;
for(int i=0; i<n; i++)
    vct.push_back(abs(ar[i]-val));

sort(vct.begin(),vct.end());
return vct[k];

cin>>tc;

while(tc--) {
    scanf("%d %d",&n,&k);

    for(int i=0; i<n; i++)
        scanf("%d",ar+i);

    int low=0, high=ar[n-1];

    while(high-low>1) {
        int mid=(low+high)/2;

        if(f2(mid)<=f2(mid+1))
            high=mid;
        else
            low=mid;
    }



    printf("%d\n",high);

}


return 0;

can you please help me to determine what is the time complexity of the following code:

https://pastebin.com/s0QZhBBN

According to my calculation:

since multiset insert complexity is log(n) .

So in that code: each operation takes : i+log(i)

for i=1 takes 1+log(1) opearation

for i=2 takes 2+log(2) opearation

for i=3 takes 3+log(3) opearation
.

.

. for i=n takes n+log(n) opearation

now summing up all = ( log(1) + log(2) + log( 3 ) + .......+log(n) ) + ( 1+2+3+.....+n)

==> log( 1*2*3*.......*n) + (n*(n+1) /2 )

    ===> log( n! ) + (n*(n+1) /2 )

So Complexity: O( log(n! ) + n^2 ) . Am i right or wrong ?

my above code is a demo code . Original problem code :

https://codeforces.net/contest/1119/submission/52407323

Here is the problem link : https://www.hackerrank.com/challenges/down-to-zero-ii/problem

I used bottom up dp , but still getting stack overflow runtime error for input 1000000 . Can anyone help me , to point out where is wrong in my code :

if(N==0)
    return 0;

if(dp[N]!=-1)
    return dp[N];

int x=recursion(N-1)+1;
int y=2147483647;

for(int i=2; i*i<=N; i++)
    if(N%i==0)
        y=min(y,recursion(N/i)+1);

dp[N]=min(x,y);

return dp[N];

memset(dp,-1,sizeof(dp));

scanf("%d",&q);

while(q--) {

    scanf("%d",&n);
    printf("%d\n",recursion(n));

}

return 0;

Hello friends, suggest me some atcoder DP problems which are from any ABC — atcoder beginner contest. Except educational dp contest problems

Given N strings , Then there will be q queries . In each query a string S , you have to determine in how many string ( N given string ) S is a subsequence of that string . For example

N=5

aeh

apoq

xyzq

alpqh

caqwerh

Q=1

ah

ans=3 , because "ah" is a subsequence of aeh , alpqh and caqwerh .

How to solve this problem effeciently . Suppose N=10^5 and Q=3*10^5 , Each string lenght would be <=10^2

Which is the most effective way of practise?

• solve from least difficult to most difficult?

• solve by most submission to least submission?

Is codeforces difficulty is accurate? And what do you think which is the most effective?

I searched google , about this , I understand only that worst case happens when a,b are consecutive fibonacci numbers .

Someone says Euclidian algo's time complexity is O(log(a+b) ) , some says O(log(n) ) . But their explanation is not clear to me . I read the first answer from here : https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm .

I pasted it bellow . It describes the analysis of euclid algo .

"One trick for analyzing the time complexity of Euclid's algorithm is to follow what happens over two iterations:

a', b' := a % b, b % (a % b)
Now a and b will both decrease, instead of only one, which makes the analysis easier. You can divide it into cases:

Tiny A: 2a <= b
Tiny B: 2b <= a
Small A: 2a > b but a < b
Small B: 2b > a but b < a
Equal: a == b
Now we'll show that every single case decreases the total a+b by at least a quarter:

Tiny A: b % (a % b) < a and 2a <= b, so b is decreased by at least half, so a+b decreased by at least 25%
Tiny B: a % b < b and 2b <= a, so a is decreased by at least half, so a+b decreased by at least 25%
Small A: b will become b-a, which is less than b/2, decreasing a+b by at least 25%.
Small B: a will become a-b, which is less than a/2, decreasing a+b by at least 25%.
Equal: a+b drops to 0, which is obviously decreasing a+b by at least 25%.
Therefore, by case analysis, every double-step decreases a+b by at least 25%. There's a maximum number of times this can happen before a+b is forced to drop below 1. The total number of steps (S) until we hit 0 must satisfy (4/3)^S <= A+B. Now just work it:

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
So the number of iterations is linear in the number of input digits. For numbers that fit into cpu registers, it's reasonable to model the iterations as taking constant time and pretend that the total running time of the gcd is linear.

Of course, if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be n^2 times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log* n). The polylogarithmic factor can be avoided by instead using a binary gcd."

In the upper statement , I am unable to understand this line (4/3)^S <= A+B . How does it come from ? If anyone can explain please help .

If anyone has other easier explanation , please share .

You are given N , A , B find such x and y that (A*x + B*y) = N and x>=0 , y>=0 . It is not guaranteed that N will be always gcd(a,b) .

If such x , y does not exist print -1 , either print x and y in same line separated by space , if there are multiple x , y that satisfy the equation print any of them .

For example: If N=9 , A=2 , B=5

then ans is 2 1 . Because 2*2+5*1=9 . Here A=2 , x=2 and B=5 , y=1 .

Constraint:

1<= N , A , B <= 10^18

INPUT

9 2 5

22 3 7

439365 78717 87873

505383 77277 99291

1000000 3 999997

474441 99291 77277

911106 51038 78188

321361 79845 81826

1000000000000000000 8765433 54343345

OUTPUT

2 1

5 1

0 5

-1

1 1

4 1

1 11

3 1

25359400 18397426840

I have solved using linear loop .

for(long long i=0; i<=n/a; i++)
        if((n-i*a)%b==0) {
            printf("%lld %lld\n",i,(n-i*a)/b);
            return 0;
        }

    printf("-1\n");

But constraint is so big so this would not pass . For this test case n=1000000000000000000 , a=3 , b=798877665 code is getting TLE .

How to solve this problem efficiently ? This is a subproblem of this problem http://codeforces.net/contest/932/problem/C

UPD solved it using extended euclid here is the code : https://ideone.com/6fzPLF

You are given an array of size N , then you are given N integers A[i] = i'th element .

You will have to process some query , Q . Two types of query :

1 — that means print the maximum sub array sum in this array .

2 p V — Update the value of index p to V ;

Constraints:

1<=N<=9*10^4

1 ≤ Q ≤ 100000

How to solve it efficiently ? I got TLE in test 4 .

Problem link: https://toph.co/p/problem---smsms

My code : https://ideone.com/GC3o8V

Hello codeforces forum , I am getting WA on test 9 and 11 . Tried many times to find the bug , but failed . Can you please provide me some test case which my code give WA .

problem link : https://csacademy.com/contest/archive/task/socks-pairs/statement/

My code : http://paste.ubuntu.com/25060704/

I am trying to find out the logic to solve this problem , KOIREP — Representatives , i tried for 7 days still get no idea to solve it .

Can anyone please tell me how can i effeciently solve it ? Problem tagged with Sliding window alias two pointer .

I solved this problem : They are everywhere using two pointer ,

but now i am trying to solve this problem using binary search . I am getting TLE on test 11 . Here is my code :

https://pastebin.com/jb5N0EKb .

I have found a problem about pythagorian triple . But input , output will be as like bellow :

Input

Each case will contain one positive integer c (1 ≤ c ≤ 500,000), the length of the hypotenuse of the right triangle.

Output

For each case, print the case number first, then print the other two sides a and b ( a and b are cathetus ). If no such a, b can be found which satisfies the above condition print “Impossible” without quotes. If there are multiple pair of (a, b) exists, print the one with smallest possible a .

5

Case #1: 3 4

6

Case #2: Impossible

25

Case #3: 7 24

How to solve this problem ? CF has a problem : http://codeforces.net/problemset/problem/707/C . But most of the solution are assumed C as cathetus . How to solve if we assume C as hypotenuse .

Hello codeforces community , problem ZigZag array is for distinct data , I solved this problem . But if data are duplicate(same data occur several times) problem become very complex . There has many corner case :

11

2 4 6 8 9 11 10 8 5 3 1

=>2 8 8 1 ( solution 1, remove 7 numbers)

=>2 11 1 (solution 2, remove 8 numbers)

so ans is 7

10

1 2 3 4 7 8 9 7 6 4

=>1 4 4 (solution 1, remove 7 numbers)

=>1 7 7 4 (solution 2, remove 6 numbers)

=>1 9 4 (solution 3, remove 7 numbers)

so ans is 6

6

1 2 3 4 5 4

=>1 4 4 (solution 1, remove 3 numbers)

=>1 5 4 (solution 2, remove 3 numbers)

so ans is 3

5

1 2 3 2 1

=>1 2 2 1 (solution 1, remove 1 number)

=>1 3 1 (solution 2,remove 2 numbers)

so ans is 1

If 1<=n<=10^5 , How to solve this problem ? and how to implement it efficiently ? I implement it but code become very complex : https://pastebin.com/QrhWgdEj

Can this problem : Bounded distinct be solvable using two pointer ? If yes what is the logic ? I implemented it with two pointer but code become very much complex . My code . Getting WA for this code .

UPD : Bug found . :)

I got a problem in here : Link . In this problem they said :

Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring.

Examples:

Input : ((()

Output : 2

Explanation : ()

Input: )()())

Output : 4

Explanation: ()()

Input: ()(()))))

Output: 6

Explanation: ()(())

My code : link here

Getting WA.

My logic is : If i got a balanced parentheses then i store the first and last index of this into vector vct . Then after storing in this manner . I check if(vct[i].first==vct[i-1].second+1) that means ith BP(balanced parentheses) and (i-1)th BP are neighour to each other , then i merge those two BP's length , if that condition is not true then , update sum=vct[i].second-vct[i].first+1 // length of ith BP . I update maximum length by this mx=max(mx,sum) ; . But getting Wrong answer . Can anyone guess the bug . Please help .

Is this possible to solve this problem with math logic ? wIthout bruteforce , easy implementation ? problem link

Hello codeforces community , i am trying to solve this problem :link . I am getting WA in test 15 , but i copied the test case on my compiler codeblocks , it gives correct output which judge want (expected output) . In judge compiler they saying my code gives output 2 , but i checked in my compiler which gives output 1 , which is correct . Dont know why this happening .

My code : https://pastebin.com/NE3sRLrR

Hello codeforces community , can you please suggest me some interesting stack problem from any judge without hackerrank , hackerearth . I solved all stack problem from hackerrank , hackerearth . Thanks in advance .

UPD : Found the bug :)

Hello everyone last day contest problem DIV2 B- not afraid . I solved this problem , One submission with break getting WA on test 10 but test case is too long so cant guess the bug — > WA on test 10 , Submission With break statement .

Another same submission got AC where i just cut the break statement -> GOT AC submission without break statement .

Can not find any short test case which will give the WA for first code .

Here is the diifference : Difference