Hello codeforces

This is a summary of our third London UK Meetup. It was great to have Mucosolvan attend the meetup today and suggest some problems.

A recap of the session is in this medium post: https://medium.com/@motatoes/competitive-programming-ldn-3-ef3b01b80d20

We will host events every week, if you are london you are welcome to join us: https://www.meetup.com/London-Competitive-Programming/

Hi Codeforces,

I am organising Competitive Programming London, where we meet once (or twice) a week to solve problems, with free coffee and snacks provided. Currently most of us are div2/3 A-C so if it would be great if someone more advanced joins the club as well. Feel free to join us if you are located in London: https://www.meetup.com/London-Competitive-Programming/

Hi Codeforces

I have been trying to solve this problem on SPOJ: https://www.spoj.com/problems/EASYMATH/

My bruteforce solution is ofcourse TLE'd and I came across this solution: https://github.com/Emsawy/Competitive-Programming/blob/master/SPOJ/EASYMATH.cpp

I have difficulty understanding the "go" function. There is a recursive call and it is calculating the LCM of all the divisors? Can someone explain the logic behind this function in simple terms? Is there a formula for this?

I'm receiving a nullpointer exeption when I visit any of the pages:

Hello Codeforces,

I'm trying to solve this problem on Hackerrank which is to implement Levenshtein distance. I've written this code which as far as I can tell is correct:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000;
int memo[N][N];

int lev_dist(string a, string b, int i, int j) {
    if (i == 0 or j == 0 ) {
        // cout << " I was here" << i << " " << j << " " << endl;
        return max(i,j);
    }   
    else {
        
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        else {
            int d1 = lev_dist(a,b,i-1,j)+1;
            int d2 = lev_dist(a,b,i,j-1)+1;
            int d3 = lev_dist(a,b,i-1,j-1);
            // indicator function
            if (a[i] != b[j]) {
                d3 += 1;
            }
            int res = min(d1, min(d2, d3));
            memo[i][j] = res;
            return res;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        for (int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                memo[i][j] = -1;
        
        string a,b;
        cin >> a;
        cin >> b;
        // cout << "a" << a.length() << "b" << b.length() << endl;
        cout << lev_dist(a,b, a.length()-1, b.length()-1) << endl;
    }
    return 0;
}

However, it fails on the pretests:

INPUT
100
CGICNWFJZOWBDEVORLYOOUHSIPOICMSOQIUBGSDIROYOMJJSLUPVRBNOOPAHMPNGQXHCPSLEYZEYSDGF
TBYHUADAJRXTDDKWMPYKNQFMGBOXJGNLOGIKTLKVUKREEEVZMTCJVUZSHNRZKGRQOXMBZYGBNDFHDVLM
NTBFKWGUYSLYRMMPSXNYXAZNZFJIPJDMNPZNLPEEYEONABFCZEZYVGCJBFMGWKQPTTGJDLKKQYJZYFSL
PEDWJMTVXVGGCLSTOOQEACZJNOVUYXPQGIRAPHFWAESSZKHKGKUEEGVWZXVFJWLQBUBOJMHLEHGKWYTN
RPXZTOSEPHWYBYSOOAKMOOJRSSFHENHDVHOIKVNXMFAEXXTBNPNFPTFGNUPLKDWRSUQYWAUVMNVYJZQL
MFKSTCDHEPTSMYNDRSNJZOULCCIUXZDCGQZRSRYEODXKNBGBBKSPPCQHJYUSCKMJZBPUBLLXPRCQJYRV
USJZEXTQXQYCXPMSRNGIWRHJFQZFQYSOTBEUZMWWHJBOTOUPGLMRDITCGYIUJXGTBIOAJWYXCHUWFNYP
DKAXVOVHAAWFYDZXJHUUXIGQRIBQGNFHYYIYDZDTDYHGOZPRLQLUOHLKWLCPXKVDGWXYROAHSVEICUYF
GMPOQQULURLAFHPSVGLCGWVTGJZEARVPKRKEWEOONARMPIEMYPUJYTHKQBYDMTPXGDKJTSHOJHWIWXBL
VSXFWFBANKGTNLVHZRJPHLGKMTCLSWCIQONXSGEBZESADLWHYUCFLFEJNBISZMVVLLCANHKLRSONBABF
CFACAXPMVDBVRTXQNNALQJVGTRWFIFHUBGFQEUCYVXPABQBPKZWQVRVYIETXJTUKXIDGRRGPYCAOZNEL
UJSLLVNZRJXMXDKRFZMZNQNLZENYKGAKINKZXVRZGCETREQCNCWABDXLKAEBLXRIRDVHELGADMJDMPJN

PROGRAM OUTPUT
73
69
71
71
73
73

JUDGE EXPECTED OUTPUT
74
70
72
72
74
74

can anyone help me find out what I did wrong in my code? Thanks

UPD finally got AC thanks to the comments, my base case was wrong as pointed out in the comments. Also I had to pass strings by reference in order to get the final AC as explained in the comments also :)

Hello Codeforces

As I'm looking for other competitive programmers to train with, I've set up a meetup group for competitive programmers in London.

Ideally I would like to meet other enthusiasts so we can train together on some Gym problems, or maybe train on a specific topics (Prime numbers, DP, modular arithmetic etc.). As this is the first meetup, I'm still unsure of what format we will be sticking to.

I look forward to meeting other Londoners who enjoy competitive coding! :)

https://www.meetup.com/London-Competitive-Programming/events/261578994/

Dear CF

I am trying to solve this problem from the gym, I have found that the solution to the problem is the sum of combinations:

nc(N, K) + nc(N, K+1) + nc(N, K+2) + ... + nc(N, N)

where nc(i, j) is the number of combinations i chose j

However the input sizes of N and K are very large and my submission times out. Can you please advise me about a suitable approach to solve this problem?

Hello Codeforces

I found that I am obsessed with colour changes and rankings that it kills the fun out of solving problems and learning new algorithms. Therefore I have coded a userscript that turns everyone into a pupil and hides your own ranking. My goal from this is to bring back the fun of solving problems on CF and worrying less about by current ranking. Here are some examples of what it does:

Hello CF!

I'm preparing for the next hashcode by solving the following prev. problem:

Given a pizza of size R x C with cells containing either mushrooms or tomatoes as shown bellow:

We are given 2 parameters: L and H. The goal is to split the pizza into rectangular slices such that each rectangle contains at least L cells of mushrooms and at least L of tomatoes. Furthermore, each split rectangle should contain at most H cells in total. Note that not all of the pizza needs to be contained in the split. The goal is to maximize the number of cells

So in the example above, L=1 and H=6 so in this case The ideal split will be:

So each split contains at least 1 mushroom and at least 1 tomato, and each split contains at most 6 cells. I am not sure how to approach the solution to this problem? Which topics should I read about to understand how to solve such a problem?

Hi CF

I'm taking this course on coursera called "algorithms on graphs". In these slides there is a description of a naive algorithm for calculating strongly connected components (SCC) on a directed graph (slide number 5):

I have a question regarding the complexity of this algorithm. We know that for each vertex V we need to explore all its neighbours so I assumed that its complexity is |V|^2 if the graph is fully connected?

Then for each neibghbour of v we must check that we can reach back to V, so what will the complexity be in this case?

My question is how can we prove that the complexity of this naive algorithm is P(|V||V| + |V||E|) where |V| is the number of vertices and |E| is the number of edges?

I'm trying to solve the python indentation problem in round 455C. My submission is receiving a memory limit exceeded.

Memory limit is: 256 * 1024 * 1024 = 268435456 bytes

In my code I am using at most a 5000*5000 matrix to hold the dp values and this will occupy ~ 200000064 bytes

I am also using a string to hold the program and it will occupy: 5049 bytes

I am using about 6 int variables in my program and then will occupy: 6 * 28 = 168 bytes

so in total: 200005281 bytes

Or 191 MB. So According to my calculations I am still bellow 200 MB, but in CF I am exceeding 256MB. Is there something that I am missing in the memory computation? Is the python interpreter size counted within the memory computation also?