I and many peoples are getting TLE on Catching Cheaters problem.

The intended solution in pypy3 implementation is getting TLE: https://mirror.codeforces.com/contest/1447/submission/98682330

There aren't any accepted solutions by Python3, Python2, Javascript.

The solution with the fastest execution time in C++ is 62 ms, which in python means 62 * 30 > 1000ms.

My accepted solution is 966 ms. Very tight

At least the time limit should be 1.5 sec. I didn't get the reason for making it so tight?

I have got a simple bug, It happens when the text in a blog is long, reaching the area of Recent Action.

I am using a PC, so the problem is not with the screen size. Link

EDIT: Now it isn't showing because there are some chats added before it.

Hi!

I am eager to know the record of the highest number of successful hacks in a single contest. Is there any way (maybe a website) to figure this out? I have 32 hacks in the recent Educational Codeforces Round 96 (Link Rank: 2259). I am not sure how big is this. I guess there will be guys with more hacks.

Thanks for taking the time to read this.

Hi!

Solution Discussion for HHKB Programming Contest 2020

I created this blog, because I couldn't find an announcement in Codeforces (where usually there would be) and want to have a discussion about the solutions to the problems after the contest ended.

The contest is being held on Atcoder. Link to the problems in the contest: https://atcoder.jp/contests/hhkb2020/tasks.

Hope this will help people who didn't get a solution for problems.

Sorry for the bad English.

The problem is this.

I guess it is a common problem. I have tried it solving with binary search.

def isValid(n, s, k): # Check if **k** is valid on the string **s** of length **n**
    ans = set(s[:k])
    for i in range(1, n-k+1):
        ans = ans.intersection(set(s[i:i+k]))
    if len(ans) >= 1: return 1
    return 0

def solve(s):
    n = len(s)
    l, h = 0, n
    mid = 0
    while l < h-1:
        mid = (l + h) // 2
        # print(l, mid, h, isValid(n, s, mid))
        if isValid(n, s, mid):
            h = mid
        else:
            l = mid
    return mid

s = list(input())
print(solve(s))

Difficulty — TLE

Help Needed — I know python is slow, but there are many peoples solving it with python. My question is how this code can be optimized (especially the valid function taking O(n*k) operations)?

I have seen the editorial, using other methods. But I am learning how to implement binary search, that is why I am trying this way.

Thanks for taking the time for reading this!

UPDATE: Accepted

Getting TLE with a python solution for Coin Combination problem in here

I know that python is slow ..., but have seen other python users solving it here

def solve(n, x, lst):
    dp = []
    for i in range(n+1):
        temp = [1] + [0]*x
        dp.append(temp)

    for i in range(1, n+1):
        for j in range(1, x+1):
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j - lst[i-1] >= 0:
                dp[i][j] = (dp[i][j] + dp[i][j - lst[i-1]]) % mod
    for i in dp: print(i)
    return dp[n][x]

n, x = list(map(int, input().split()))
lst = list(map(int, input().split()))
print(solve(n, x, lst))

Creating the dp 2D array is even taking much time. Is there a way it can be optimized?

Thanks for taking your time and reading this!

In the Top Rated List on the left of the codeforces page, MiFaFaOvO isn't in the list?

Am I the only one seeing this?

Is it a bug, or does he become more than legendary grand master :XD?

Image

Link to the problem.

My idea is first grouping the array into sorted subarray, for example if the the array was [1, 5, 6, 2, 4, 7, 3]. We can group it into [[1, 5, 6], [2, 4, 7], [3]] so that each groups are sorted. Meaning for each group Gi with a length Ni, It is possible to remove Ni — 1 element from it. So if we all ways remove the larger one , the smallest element will left.

After this let minn be the smallest element in group0 (first sorted group), if there is an element greater than minn in group1, then update value of minn to the smallest element greater than minn in group1, else the answer is "NO". Then again there should be an element greater than (updated) minn in group2, and so on.... If there isn't such value then the answer is "NO".

Python Code : Here

Can someone tell me what is wrong in the approach or give a counter example?

Thanks in advance for devoting your time to read this!

Link to the problem.

My idea is first grouping the array into sorted subarray, for example if the the array was [1, 5, 6, 2, 4, 7, 3]. We can group it into [[1, 5, 6], [2, 4, 7], [3]] so that each groups are sorted. Meaning for each group Gi with a length Ni, It is possible to remove Ni — 1 element from it. So if we all ways remove the larger one , the smallest element will left.

After this let minn be the smallest element in group0 (first sorted group), if there is an element greater than minn in group1, then update value of minn to the smallest element greater than minn in group1, else the answer is "NO". Then again there should be an element greater than (updated) minn in group2, and so on.... If there isn't such value then the answer is "NO".

Python Code : Here

Can someone tell me what is wrong in the approach or give a counter example?

Thanks in advance for devoting your time to read this!

I have participated in Educational Codeforces Round 92 Editorial and in the hacking phase I was trying to hack 88307545 solution. The input data I used was:

2
1 25
100 250

The code will output (on local PC and on online compiler):

12 24
25 5
25 5
25 5
25 5
125 250

I write the second test case to make codeforces think "the first line from the output is for the first test case and the others are for the second test case", but I got unsuccessful attempt. I didn't understand why this didn't work? Can someone explain to me?

Thanks in Advance!

Problem from "Competitive Programmer’s Handbook" by Antti Laaksonen, Page 61.

The problem is to find x to minimum the sum of the equation below:

Image

I thought the answer will be the mean on the number because if we plot the in a 1D number line, the mean will be somewhere middle of them, so the absolute difference of distance between each number and the mean can be minimized.

The book says it is the median.

Example [1, 2, 2, 6, 9]

The mean will be 19 / 5 = 3.8. The absolute difference is 13.8.

The median is 2 an the absolute difference is 12.

I know that this is the absolute sum not the just the sum. But the median is only limited to the element of the array. Why x should be the median instead of the mean? Can this be mathematically proved?

For any integer n and where k is power of 2,

n % k = n & (k-1)

Example : Let n = 26 and k = 2 ^ 3 = 8 , so 26 % 8 = 2
bin(26)  = 11010
bin(8-1) = 00111
26 & 7   = 00010 = 2, which is CORRECT

I wasn't able to proof this statement, how could it be proofed without taking number as example?

Thanks in Advance!

I am stuck with a runtime error in UVA Online Judge problem 11559, Event Planning

for _ in range(int(input())):
    lst = list(map(int, input().split()))
    if len(lst) == 1: print(0)
    else: print(max(lst[1:]))

I have run it on my local PC, but it doesn't have error message. I have also added a code for checking if it N is 0 .

How can I solve the error? Is it possible to see the error text?

I am a beginner in c++, I am trying to write a program that read 7 integers like x, a, b, c, d, e, f.

The program is to count how many of the following condition are true:

x is in [a, b]

x is in [c, d]

x is in [e, f]

so the program will return either 1, 2, 3. my program :

#include<iostream>

using namespace std;

int main(){
    int x, a, b, cnt = 0;
    cin >> x;
    cout << x << endl;
    for (int i = 0; i <= 2; i++){
        cin >> a >> b;
        if (x >= a && x <= b)
            //cout << a << " " << b << " " << endl;
            ++cnt;
    }
    cout << "Count: " << cnt;

    return 0;
}

I used to variable a and b to get input for the three pair intervals.

sample input : 7 1 10 5 6 4 40

expected output: 2

The program final result will give 2, but when I uncomment line 12 (print the value of the a and b before increment cnt ) the final result will be 3.

I don't know why I am getting different result. Does printing have effect of the code below?

I haven't seen this kind of thing in Python3 (know well). This question might seem silly for you but I am very confused why this is happening?

Thanks in Advance!

I am stuck with this problem, wrong answer at test case 2, 87494955 .

Is it possible to get the 12th sample on test case 2, if not can some one help me by getting a sample that can make my code wrong?

Thanks in advance

Hey, In Round #655 problem D I am having TLE , 86974560

My idea (mostly similar to the editorial's but have some changes) is in the below image, Let n = 5, a = [1, 2, 3, 4, 5] and I have 2 steps. One step 1 I start from the first element and move by 2, so from 1 --> 3 --> 5 --> 2 --> 4. I will create a array for this [1, 3, 5, 2, 4]. Then I will find the maximum sum of length (n + 1)/2 as maxx1.

On step 2 I will repeat the above from starting from the second element and move by 2, 2 --> 4 --> 1 --> 3 --> 5. [2, 4, 1, 3, 5]. Then find the maximum sum of length (n + 1)/2 as maxx2.

Return the max(maxx1, maxx2). That was all, I am sure it works (No Wrong Answer).

I guess the Time Complexity will be around O(n). Someone tell me if it is larger or know why the TLE occured?

Can someone tell me why I am getting run time error on test case 2: Python3 --> 85214254 ?

When I see the test case it is like 
64
3125 1829
-2695 435 632 2042 202 ...
I don't know why one line is missing at last? 
Thanks in Advance

I get this error on one test case saying wrong output format Extra information in the output file.I think the code works fine.

83541220

What is the reason for this error?

Thanks in Advance!