I should have used a faster programming language

[doctorlai]

I am learning Python, and I think Python is elegant, but unfortunately it is slow somehow, especially when tests are hard.

Today, I participated in codeforces round 162, and I made the mistakes using Python in solving problem C/D,

for example, Problem D <good sequence> is definitely a Dynamic Programming problem, and I code in Python very quickly.

It passed tests during the contest and 'accepted' shown, I thought that was it, but apparently not, after contests, harder tests were added and the Python solution got TL on Test 21..

Code: Select all

#!/usr/bin/env python

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(raw_input())
seq = map(int, raw_input().split())
 
f = len(seq) * [1]
 
for i in xrange(len(seq)):
    for j in xrange(i):
        if seq[j] < seq[i] and gcd(seq[j], seq[i]) > 1 and f[j] >= f[i]:
            f[i] = f[j] + 1
 
print max(f)

I will rewrite this in C++ and see how it goes...
next time, i will not use Python to solve the difficult problems.

[doctorlai]

I am learning Python, and I think Python is elegant, but unfortunately it is slow somehow, especially when tests are hard.

Today, I participated in codeforces round 162, and I made the mistakes using Python in solving problem C/D,

for example, Problem D <good sequence> is definitely a Dynamic Programming problem, and I code in Python very quickly.

It passed tests during the contest and 'accepted' shown, I thought that was it, but apparently not, after contests, harder tests were added and the Python solution got TL on Test 21..

Code: Select all

#!/usr/bin/env python

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(raw_input())
seq = map(int, raw_input().split())
 
f = len(seq) * [1]
 
for i in xrange(len(seq)):
    for j in xrange(i):
        if seq[j] < seq[i] and gcd(seq[j], seq[i]) > 1 and f[j] >= f[i]:
            f[i] = f[j] + 1
 
print max(f)

I will rewrite this in C++ and see how it goes...
next time, i will not use Python to solve the difficult problems.

I've implemented the same idea using Java, and to my surprise, it gives the same result, TL at 21.
so maybe, I should optimize my algorithm to kinda of O(nlogn) instead of O(n^2)

Code: Select all

import java.io.*;
import java.util.*;

public class codeforces
{
   static int gcd(int x, int y)
   {
      while (y > 0)
      {
         int t = x;
         x = y;
         y = t % y;
      }
      return x;
   }

    public static void main(String[] args) throws IOException
    {
       BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(rr.readLine());
      String[] s = rr.readLine().split(" ");
      int[] arr = new int[n];
      for (int i = 0; i < n; i ++)
      {
         arr[i] = Integer.parseInt(s[i]);
      }
      int[] f = new int[n];
      Arrays.fill(f, 1);
      int max = 1;
      for (int i = 0; i < n; i ++)
      {
         for (int j = 0; j < i; j ++)
         {
            if ((arr[j] < arr[i]) && (gcd(arr[i], arr[j]) > 1) && (f[j] >= f[i]))
            {
               f[i] = f[j] + 1;
               if (f[i] > max)
               {
                  max = f[i];
               }
            }
         }
      }
      System.out.print(max);
    }
}