the dp problem: stamp Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

I try to use dp in the following way, but get wrong on test 9, my method is:

let dp[i][j] be the max value W that can be made from 1 to W, with the condition that we use first i types of coin and at most j coins to make the total value. then anwser is dp[N][K].

for(int i=1;i<=N;i++)for(int j=0;j<=K;j++)
    {
        long long maxlen=dp[i-1][j];
        long long k=1;
        while(k<=j){
            int next= k * a[i];
            if(next>maxlen+1)break;
            else{
                maxlen=max(maxlen,k*a[i]+dp[i-1][j-k]);
                k++;
            }
        }
        dp[i][j]=maxlen;
    }
    
fout<<dp[N][K]<<endl;

it wrong for test case: K(max coin to use)=6, N(size of coins set)=10 , coins={1 2 9 31 255 480 4 15 63 127 } my output is 242,while anwser is 720.

I try hard, but I can't figure out why this method is wrong. Anyone please take a minute to help me with this dp problem, thank you so much in advance!

Hi, all!

I have an array a[] size of n. note that a[i] in range of 10^18. n in range of 10^6.

How to calculate cnt[] in O(n)?

Here cnt[i] = number of elements in a[] that is no greater than a[i].

For exmaple, a[] = 3 2 3 1 1 2, size n= 6

then cnt[] = 6 4 6 2 2 4.

Is there any algorithm to do that in O(n)? or in O(nlogn) if we have to sort?

To clarify, "subarray" is defined like, for example:

if A="abc" B="??a???b????c???" then A is subarray of B.

I have two version to check if A is subarray of B, but versionI get AC, versionII get WA:

version I. iterate the bigger string B.

curA=0;
for(int i=0;i<B.size;i++){
    c=B[i];
    if(curA<A.size && A[curA]==c )curA++;
}
if(curA==A.size)return true;
else return false;

version II. iterate the smaller string A

curB=0;
for(int i=0;i<A.size;i++){
    c=A[i];
    while(curB<B.size && B[curB]!=c ) curB++;
    if(curB==B.size)return false;
}
return true;

**** Why versionI is correct, while versionII is wrong? anyone please explain or give an example to show that versionII is wrong, sincerly thanks in advace!

Abstract

In the following I will describe how to read the input in Java. We will examine the Scanner class and then write our own class for faster input reading.

Using the Scanner class

We can read the input using the Scanner class:

import java.util.*;

public class Main{ public static void main(String[] args) { // Use the Scanner class Scanner sc = new Scanner(System.in);
/* int n = sc.nextInt(); // read input as integer long k = sc.nextLong(); // read input as long double d = sc.nextDouble(); // read input as double String str = sc.next(); // read input as String String s = sc.nextLine(); // read whole line as String */ } } Using the BufferedReader class

However, the Scanner class is slow and may cause a "timelimit exceeded". We can read the input faster with the BufferedReader class. The class "MyScanner" below uses a BufferedReader. The same method names as in the Scanner class have been chosen, e.g. to read the input as an integer we still can use nextInt().

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

public class Main{ public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out));

// Start writing your solution here. -------------------------------------

  /*
  int n      = sc.nextInt();        // read input as integer
  long k     = sc.nextLong();       // read input as long
  double d   = sc.nextDouble();     // read input as double
  String str = sc.next();           // read input as String
  String s   = sc.nextLine();       // read whole line as String

  int result = 3*n;
  out.println(result);                    // print via PrintWriter
  */

  // Stop writing your solution here. -------------------------------------
  out.close();

}

//-----------PrintWriter for faster output--------------------------------- public static PrintWriter out;

//-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st;

public MyScanner() {
     br = new BufferedReader(new InputStreamReader(System.in));
  }

  String next() {
      while (st == null || !st.hasMoreElements()) {
          try {
              st = new StringTokenizer(br.readLine());
          } catch (IOException e) {
              e.printStackTrace();
          }
      }
      return st.nextToken();
  }

  int nextInt() {
      return Integer.parseInt(next());
  }

  long nextLong() {
      return Long.parseLong(next());
  }

  double nextDouble() {
      return Double.parseDouble(next());
  }

  String nextLine(){
      String str = "";
  try {
     str = br.readLine();
  } catch (IOException e) {
     e.printStackTrace();
  }
  return str;
  }

} //-------------------------------------------------------- } References

ReadLine in Java

If you know of a simpler/better method for input reading in Java, please post it below.

I added PrintWriter for a faster output.

Thanks for reading and comments.

Hi, I got a great idea for div2 problem A. Something like this: once upon a time, a coder BiliBala shitpost a post to know how many girls and boys are in codeforces. the post makes a rule, like this, girl comment 1, boys commnet 2, and other creatures commnet 3. Now you have collecte all the n commnets, now please help BiliBala count how many girls and boys and other creatures are in codeforeces. sample:3 1 2 3; output 2 1 1. note that the poster BiliBala itself is unknown creature, so the output can be 2 1 1,1 2 1, 1 1 2. if there are many anwsers, print one.

Hi, I need your help. I am going to study, bye.

problems.thanks