Problem Statement

    

You are given a String s consisting of lower case letters. We assign the letters 'a' to 'z' values of  to , respectively. We will denote the value assigned to the letter X by val[X]. For example, val['a'] =  and val['e'] = .

We define the value of the string s as follows. For each letter s[i], let k[i] be the number of letters in s that are less than or equal to s[i], including s[i] itself. Then, the value of s is defined to be the sum of k[i] * val[s[i]] for all valid i.

Given the string, compute and return the value of the string.

Definition

    

Class:

ValueOfString

Method:

findValue

Parameters:

String

Returns:

int

Method signature:

int findValue(String s)

(be sure your method is public)

Limits

    

Time limit (s):

2.000

Memory limit (MB):

Stack limit (MB):

Constraints

-

s will contain between  and  characters, inclusive.

-

s will consist of lowercase letters ('a'-'z').

Examples

)

    

"babca"

Returns:

The value of this string is * + * + * + * + * = .

We can get the value as follows. The first character is a 'b' which has value , and has  characters that are less than or equal to it in the string (i.e. the first, second, third and fifth character of the string). Thus, this first character contributes * to the sum. We can derive a similar expression for each of the other characters.

)

    

"zz"

Returns: 

)

    

"y"

Returns: 

)

    

"aaabbc"

Returns: 

)

    

"topcoder"

Returns: 

)

    

"thequickbrownfoxjumpsoverthelazydog"

Returns: 

)

    

"zyxwvutsrqponmlkjihgfedcba"

Returns: 

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), TopCoder, Inc. All rights reserved.

#include <string>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

class ValueOfString

{

  public:

    int findValue( string s )

      {

        int res =  ;

        int cnt[] , val[] ;

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

            cnt[i] =  ; val[i] = i +  ;

        }

        for( int i =  ; i < s.length() ; ++i ) {

            cnt[ s[i]-'a' ]++;

        }

        for( int i =  ; i <  ; ++i ) cnt[i] += cnt[i-] ;

        for( int i =  ; i < s.length() ; ++i ) {

             res += cnt[ s[i] - 'a' ] *  val[ s[i]-'a' ] ;

        }

        return res ;

    }

};

Problem Statement

    

Alice and Bob are playing a game called "The Permutation Game". The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first N positive integers. Let p be Bob's permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice's final value will be f(x). Alice wants to choose the smallest x such that f(x) =  for any permutation Bob can provide. Compute and return the value of such x.

Definition

    

Class:

ThePermutationGameDiv2

Method:

findMin

Parameters:

int

Returns:

long long

Method signature:

long long findMin(int N)

(be sure your method is public)

Limits

    

Time limit (s):

2.000

Memory limit (MB):

Stack limit (MB):

Notes

-

The return value will fit into a signed -bit integer.

-

A permutation of the first N positive integers is a sequence of length N that contains each of the integers  through N exactly once. The i-th (-indexed) element of a permutation p is denoted by p[i].

Constraints

-

N will be between  and  inclusive.

Examples

)

    

Returns:

Bob can choose the permutations {,} or {,}. If Alice chooses , then, Bob can choose the permutation {,}, which would would make f() = . However, if Alice chooses , no matter which permutation Bob chooses, Alice will get f() = . Thus the answer in this case is .

)

    

Returns: 

)

    

Returns: 

)

    

Returns: 

)

    

Returns: 

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), TopCoder, Inc. All rights reserved.

#include <string>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

class ThePermutationGameDiv2

{

  public:

    long long gcd( long long a , long long b ) { return b ==  ? a : gcd( b , a % b ) ; }

    long long LCM( long long a , long long b ) { return a/gcd(a,b)*b; }

    long long findMin( int n )

      {

        long long res =  ;

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

            res = LCM( res , i ) ;

        }

        return res ;

    }

};

Problem Statement

    

Roger the Robot has been sent to explore a planet. The surface of the planet can be thought of as a two-dimensional plane. You are given two int[]s x and y. The planet has N interesting points described by these int[]s. The i-th interesting point has coordinates (x[i], y[i]). No three interesting points will be collinear.

Roger will choose a permutation of {,,...,N-}, and will visit the points in that order. Roger will travel in a straight line in between points. There are two conditions he must follow:

He must never cross his own path (that is, if we look at the line segments formed by the path, no two segments strictly intersect).

Due to rather unfortunate oversight, Roger is incapable of making any right turns. This means that for any three consecutive points that he visits, these three points constitute a counter-clockwise orientation.

Your job is to find a path that Roger can take. If there is no valid path, return an empty int[]. Otherwise, return an int[] containing a permutation of ,...,N-, representing a valid path that Roger can take.

Definition

    

Class:

NoRightTurnDiv2

Method:

findPath

Parameters:

int[], int[]

Returns:

int[]

Method signature:

int[] findPath(int[] x, int[] y)

(be sure your method is public)

Limits

    

Time limit (s):

2.000

Memory limit (MB):

Stack limit (MB):

Constraints

-

x will contain between  and  elements, inclusive.

-

y will contain exactly the same number of elements as x.

-

Each element of x,y will be between -, and ,, inclusive.

-

All pairs (x[i], y[i]) will be distinct.

-

No three points will be collinear.

Examples

)

    

{-, , }

{, -, }

Returns: {, ,  }

The points form a triangle. Any of the following return values will be accepted: {,,},{,,},{,,}

)

    

{,,-,-,,}

{-,,-,,-,}

Returns: {, , , , ,  }

Here is a picture of the points:

Here is an example of a different valid solution. This would correspond to a return value of {,,,,,}

)

    

{,,,,,,,,,}

{,,,,,,,,,}

Returns: {, , , , , , , , ,  }

)

    

{, ,-, ,-, ,-, }

{, , , , , , , }

Returns: {, , , , , , ,  }

)

    

{-,,,,-,,,,,,-,-,-,,-,-,-,-,,,,,

,-,,,,,,-,,-,-,,-,-,,-,,,,-,-,,

,,,,-,}

{-,,,-,-,,,,,-,-,-,,-,,-,,-,-,-,,-,

,-,-,,,-,,,,-,-,-,-,-,,,,-,-,-,-,

-,,,-,-,,-}

Returns:

{, , , , , , , , , , , , , , , , , , ,

 , , , , , , , , , , , , , , , , , ,

 , , , , , , , , , , , ,  }

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), TopCoder, Inc. All rights reserved.

#include <string>

#include <cstdio>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <map>

using namespace std;

typedef pair<int,int> pii;

const int N = ;

struct Point {

       int x , y , idx ;

    Point(){};

    Point( int x , int y ):x(x),y(y){}

    bool operator < ( const Point a )const {

        if( x != a.x ) return x < a.x;

        else return y < a.y ;

    }

}p[N];

Point operator - ( const Point a , const Point b ){

    return Point( a.x - b.x , a.y - b.y );

}

int Cross( Point A , Point B ) { return A.x*B.y-A.y*B.x; }

bool vis[N];

class NoRightTurnDiv2

{

  public:

    vector<int> findPath( vector<int> x, vector<int> y )

      {

        vector<int>res ;

        int n = x.size();

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

            p[i].x = x[i] , p[i].y = y[i];

            p[i].idx = i ;

            if( p[i].y < p[].y || p[i].y == p[].y && p[i].x > p[].x ) swap( p[] , p[i] );

        }

        memset( vis , false , sizeof vis );

        vis[] = true ; res.push_back( p[].idx );

        int pre =  ;

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

            int now = - ;

            for( int j =  ; j < n ; ++j ) if( !vis[j] ) {

                if( now == - ) now = j ;

                else {

                    if( Cross( p[pre] - p[now] , p[pre] - p[j] ) <=  ) {

                        now = j ;

                    }

                }

            }

            vis[now] = true ;

            res.push_back( p[now].idx ) ;

            pre = now ;

        }

        return res ;

    }

};