RAMPUP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ram Agrawal
Tester: Ram Agrawal
Editorialist: Ram Agrawal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

dynamic programming

PROBLEM:

Yogesh recently learned skating and decided to take his skills to next level. He started attending special coaching for skating and learned some new tricks but he now decided to perfect his skills so he need a ramp to practice his skills, but ramps are very costly so he decided to build his own. He realized he had some wooden logs that he could use to construct his ramp, so he arranged them in increasing order. However, for his ramp to function properly, the logs must be arranged in such a way that the ramp is smooth. For this, he devised a method for that he will only select the logs that meet the following criteria.

  • logs should be in increasing order
  • difference between all the selected consecutive logs should be constant.

You are given an integer NN denoting number of logs and an sorted sequence S[N]S[N] of length NN denoting the height of logs you need select the logs and arrange them in such a way that ramp contains maximum number of them.

QUICK EXPLANATION:

Given a set of numbers, find the L ength of the L ongest A rithmetic P rogression (LLAP ) in it.

EXPLANATION:

For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.

A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.
We can solve this problem in O(n2) time using Dynamic Programming. To get idea of the DP solution, let us first discuss solution of following simpler problem.

Given a sorted set, find if there exist three elements in Arithmetic Progression or not
Please note that, the answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’ and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.

  1. Initialize i as j-1 and k as j+1
  2. Do following while i >= 0 and k <= n-1
  • If set[i] + set[k] is equal to 2*set[j], then we are done.
  • If set[i] + set[k] > 2*set[j], then decrement i (do i–).
  • Else if set[i] + set[k] < 2*set[j], then increment k (do k++).

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

// GCC Optimizations

#pragma GCC optimize(“Ofast,03”)

#pragma GCC target(“fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native”)

#pragma GCC optimize(“unroll-loops”)

#define int long long int

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define PI 3.141592653589793238462

#define set_bits __builtin_popcountll

#define INF 1e18

using namespace std;

using namespace std::chrono;

int maxlogs(int i,int a[],int n){

std::vector<int> v;

for(int j=i;j<n-1;j++)

v.push_back(a[j+1]-a[i]);

int maxi=0;

for(int i=0;i<v.size();i++){

  int ans=1;

  while(binary_search(v.begin(),v.end(),ans*v[i]))

  ans++;

  maxi=max(maxi,ans);

}

return maxi;

}

int32_t main()

{

  auto start1 = high_resolution_clock::now();

  fastio();

  int t;

  cin>>t;

  int tc=t;

  //sieve_of_eratosthenes();

  while(t--){

    int n;

    cin>>n;

    int a[n];

    for(int i=0;i<n;i++)

    cin>>a[i];

    int ans=0;

    for(int i=0;i<n;i++)

    ans=max(ans,maxlogs(i,a,n));

    cout<<ans<<"\n";

  }

auto stop1 = high_resolution_clock::now();

auto duration = duration_cast<microseconds>(stop1 - start1);



  int tm=(double)duration.count()/1000;

  cerr << "Time: " << tm << " ms" << endl;

return 0;

}

Tester's Solution

import sys

from math import sqrt,ceil,floor,gcd

from collections import Counter,defaultdict

def int_arr(): return list(map(int,input().split()))

def str_arr(): return list(map(str,input().split()))

def get_str(): return map(str,input().split())

def get_int(): return map(int,input().split())

def get_flo(): return map(float,input().split())

def lcm(a,b): return (a*b) // gcd(a,b)

mod = 1000000007

def solve(n,arr):

  ans = -1

  d = defaultdict(int)

  for i in range(n):

      d[arr[i]] += 1

 

  for i in range(n-1):

      for j in range(i+1,n):

          diff = arr[j]-arr[i]

          tmp = arr[j]

          c = 2

          while diff+tmp in d:

              tmp += diff

              c += 1

          ans = max(c,ans)

  print(ans)

for _ in range(int(input())):

  n = int(input())

  arr = int_arr()

  solve(n,arr)
Editorialist's Solution

import java.io.BufferedReader;

import java.io.IOException;

import java.io.PrintWriter;

import java.io.InputStreamReader;

import java.util.*;

import java.util.Collections;

import java.util.StringTokenizer;

class Solution{

static FastScanner fs  = new FastScanner();

static PrintWriter out = new PrintWriter(System.out);

static void output(){

    int n = fs.nextInt();

    int[] a = fs.readArray(n);

    int ans = 0;

    for(int i=0;i<n;i++){

        for(int j=i+1;j<n;j++){

            int c = 2,prev = a[i],cur = a[j],dif = cur-prev;

            while(Arrays.binarySearch(a,cur+dif) >= 0){

                int t = cur+dif;

                prev = cur;

                cur = t;

                c++;

            }

            ans = Math.max(c,ans);

        }

    }

    if(n <= 2)

        ans = n;

    out.println(ans);

             

}

public static void main(String[] args) {

 

  int T = 1;

    T=fs.nextInt();

  for (int tt=0; tt<T; tt++) {

    output();

    out.flush();

  }

}

static void sort(int[] a) {

  ArrayList<Integer> l=new ArrayList<>();

  for (int i:a) l.add(i);

  Collections.sort(l);

  for (int i=0; i<a.length; i++) a[i]=l.get(i);

}



static class FastScanner {

  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

  StringTokenizer st=new StringTokenizer("");

  String next() {

    while (!st.hasMoreTokens())

      try {

        st=new StringTokenizer(br.readLine());

      } catch (IOException e) {

        e.printStackTrace();

      }

    return st.nextToken();

  }

 

  int nextInt() {

    return Integer.parseInt(next());

  }

  int[] readArray(int n) {

    int[] a=new int[n];

    for (int i=0; i<n; i++) a[i]=nextInt();

    return a;

  }

  long nextLong() {

    return Long.parseLong(next());

  }

  String nextLine()

      {

          String str = "";

          try {

              str = br.readLine();

          }

          catch (IOException e) {

              e.printStackTrace();

          }

          return str;

      }

}

}