Submission link: https://mirror.codeforces.com/contest/1292/submission/239863555

adj is going to use n long long int

dp, cnt, par : n^2 * 3

Each pair of vertices has unique distance so prs would also hold n*n long long int

Total = 4*n^2 = 4*(3*10^3)^2 = 36*10^6 long long int

1 long long int uses 8 Bytes so total = 36*10^6*8 Bytes = 288 * 10^6 Bytes = 288 Megabytes. Memory limit is 512 MB but still I am getting MLE.

Where am I wrong?

My submission works in O(n logn logA) = 1.2*10^8. Its time limit is 8 seconds

Submission link: https://mirror.codeforces.com/contest/1777/submission/238628649

If we iterate on smaller segment then the query will run for nlogn times and trie works in log A

What is the memory limit of my code : https://mirror.codeforces.com/contest/1706/submission/237628836

vector a,r : 2*8MB = 16MB

In vector<vector> change, I am pushing a new element only if a previous element is removed. It ensures that number of integers inside this change 2d vector is exactly n at all times. So it should be 8MB(for integers) + 8MB(for each vector)

Overall, it should be 32 MB only. However, it is exceeding 64 MB and giving help

Problem link: https://mirror.codeforces.com/contest/1625/problem/D

Sorry for necroposting, but I didn't find any solution for this in comments or anywhere

In problem D, The editorial solution uses a trie. if you use trie. Then there are at most nlogA vertices. If we implement using pointers then its memory would be nlogA*32 (32 if because of pointer address size in 32 bit compiler) = 3*10^5*30*30 = 2.7*10^8 ~ 2 GB. But memory limit is just 256 MB. How to solve this issue?

My MLE submission

https://mirror.codeforces.com/contest/1399/submission/229486965

I am iterating on all edges and storing all possible contribution. Then sorting it and using two pointer. Complexity: O(nlogw.log(nlogw)). It is same as jiangly solution. But I am getting Runtime error. I t already tried looking for index out of bounds and memory limit

I tried looking for custom hashes but they are making my TL worse.

Submission without custom hash give TLE on test 58 (https://mirror.codeforces.com/contest/1806/submission/228273003)

Submission with custom hash gives TLE on test 10 only (https://mirror.codeforces.com/contest/1806/submission/228272848)

Tried changing fixed_random to some custom random value but still TLE on test 10 (https://mirror.codeforces.com/contest/1806/submission/228273244)

By range assignment, I mean setting all values in a range to x

I have been looking for this template but could not find anywhere. The best I have got is when updates is not decreasing the value.

I also tried modifying the lazy segment tree but could not get desired result

Can you share your template

Question link

Submission link

My solution is in O(n^2*log(mod)) . It should pass easily

What are some necessary templates and topics for Amritapuri regionals?

This code is not passing : link

However this code is passing: link

The only difference between them is line 63

#ifndef ONLINE_JUDGE 
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__),cerr<<"\n";
#else

#ifndef ONLINE_JUDGE 
#define dbg(...) 233
#else

Since I am printing on cerr I should be getting TLE. And I have used the same template in other problem A,B as well, there it passed

I wanted to host a contest with self created questions which anyone can register with the link. I could not find any way by googling. How to do this? Thank you.

I just read in the FAQ#6 that we should not create alt account. I created this account just for asking problems. Can my account get banned for this? If yes then please delete my this account, I was unaware of the rule.

This submission only took around 1.5 seconds to run atcoder. But in local, for the sample input 3, it is taking 10 seconds. I am using Intel(R) Core(TM) i7-9750H CPU@2.60GHz

Problem link

I understood the editorial except constructing maximal B part. How is he constructing it? Explain please

Source: https://www.geeksforgeeks.org/media-net-interview-experience-for-sde-on-campus/

There is some line missing in the problem statement so I am writing here. Also the code for solution is provided but I am not able to understand

We are given strings containing 1 and 2.

When is string a good ? If we are at index i then we can either move a[i] units left or a[i] units right. We have to start at first index and reach last index such that every index is visited once. If we are able to do the it is a good string

Give 2 strings a, b which are initially good. You can select an array of indexes and for each index i, swap(a[i], b[i]). How many ways are there of selecting an array of indexes such that both strings remain good

bool validate(int num, char value, int& newNum) {
    if(value == '1') {
    newNum = 0;
      return (num != 1);
    }
    if(value == '2'){
    if(num == 1){
      newNum = 2;
        return true;
    }
      else if(num == 0){
      newNum = 1;
        return true;
      }
      else{
      return false;
      }   
    }
}
   
  string A,B; 
  int n = A.size();
  int dp[n][3][3];//initialised to 0
  int solve(int s, int j, int k){
              
      char a = A[s];
      char b = B[s];
      
      int nextj,nextk;
      
      if(validate(j,a,nextj) && validate(k,b,nextk)){
                 dp[s][nextj][nextk] += dp[s-1][j][k];
      }
      
            if(validate(j,b,nextj) && validate(k,a,nextk)){
            dp[s][nextj][nextk] += dp[s-1][j][k];
        }
      
  }
  
  int main(){
      //inputs
    
    for(int i=0;i<n;i++){
      for(int j=0;j<=2;j++){
        for(int k=0;k<=2;k++){
          solve(i,j,k);
        }
      }
    }
      
      cout<<dp[n-2][0][0]*2;
  }

Can someone explain the solution please?

You are given N. Find number of pairs of integers x, y such that

1 <= x < y <= N and sumOfDigits(x) > sumOfDigits(y)

Constraints:

N <= 10^100 and is given as a string.

Output answer modulo 1e9+7

I don't remember the sign of inequality properly, it might be sumOfDigits(x) < sumOfDigits(y). I read about digit DP to solve this but I cannot find any approach.

How to solve this?

Problem link: https://mirror.codeforces.com/problemset/problem/1463/C

Submission link: https://mirror.codeforces.com/contest/1463/submission/166835281

Problem link: https://mirror.codeforces.com/contest/1472/problem/E

Submission link: https://mirror.codeforces.com/contest/1472/submission/165709605

Problem link: https://mirror.codeforces.com/problemset/problem/1478/C

In the editorial its given that di exist twice. The proof is given for the existence of pair. Why can't there be 4 values of same di?

Problem link: https://leetcode.com/contest/weekly-contest-291/problems/k-divisible-elements-subarrays/

since n <= 200. O(n^3logn) solution should pass but it is giving TLE.

TLE submission link: https://leetcode.com/submissions/detail/751013225/

A few minutes ago, it had got accepted but its not getting accepted now.

AC submission link : https://leetcode.com/submissions/detail/751012624/

Can someone tell me why?

Problem link: https://atcoder.jp/contests/abc259/tasks/abc259_b

Submission link(WA): https://atcoder.jp/contests/abc259/submissions/33131531

Submission link(AC): https://atcoder.jp/contests/abc259/submissions/33131108

The only change I have done is how I am calculating the angle. I am getting wrong answer when I use atan, however I am getting AC with atan2.

ld ang;
  if(a == 0){
    if(b > 0) ang = PI/2;
    else ang = -PI/2;
  } else ang = atan((ld)b/a);

Problem link : https://mirror.codeforces.com/contest/1620/problem/C

Submission link : https://mirror.codeforces.com/contest/1620/submission/162394549