【TopCoder】ZigZag - 2003 TCCC Semifinals 3

Problem Statement

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. 
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. 
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Solution

class ZigZag{
    public:
        int longestZigZag(vector<int> numbers){
            vector<int> dp(numbers.size(), 1);
            vector<int> mark(numbers.size(), 0);
            for(int i = 1; i < numbers.size(); i++){
                for(int j = 0; j < i; j++){
                    int tmp = numbers[i] - numbers[j];
                    if(tmp > 0 && mark[j] <= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = 1;
                    }else if(tmp < 0 && mark[j] >= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = -1;
                    }
                }
            }
            sort(dp.begin(), dp.end());

            return dp[numbers.size()-1];
        }
};

【TopCoder】 SRM 144 div 2 200

Problem

Problem Statement

Computers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date. Your task in this problem is to write a method whatTime, which takes an int, seconds, representing the number of seconds since midnight on some day, and returns a string formatted as “< H >:< M >:< S >”. Here, < H > represents the number of complete hours since midnight, < M > represents the number of complete minutes since the last complete hour ended, and < S > represents the number of seconds since the last complete minute ended. Each of < H >, < M >, and < S > should be an integer, with no extra leading 0’s. Thus, if seconds is 0, you should return “0:0:0”, while if seconds is 3661, you should return “1:1:1”. 
Definition

Class:

Time

Method:

whatTime

Parameters:

int

Returns:

string

Method signature:

string whatTime(int seconds) 
(be sure your method is public)

Limits

Time limit (s):

2.000

Memory limit (MB):

64

Constraints

seconds will be between 0 and 24*60*60 - 1 = 86399, inclusive.

Examples

0)

0 
Returns: “0:0:0”

1)

3661 
Returns: “1:1:1”

2)

5436 
Returns: “1:30:36”

3)

86399 
Returns: “23:59:59”

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Solution

Get 155.57/200 points

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

class Time{
    public:
        string whatTime(int seconds);

};

string Time::whatTime(int seconds){
    int h = seconds / 60 / 60;
    int m = seconds / 60 - h*60;
    int s = seconds - h*60*60 - m*60;
    stringstream ss;
    string str, str2, str3;
    ss << h;
    ss >> str;
    ss.clear();
    ss << m;
    ss >> str2;
    ss.clear();
    ss << s;
    ss >> str3;
    return str + ":" + str2 + ":" + str3;
}