I forgot to check for a special case while solving DIV2 - 500 point problem, and it failed system test.
I also made one unsuccessful challenge. My only successful submission was for DIV2 - 250.
I ended up getting a very low score, and failed to become blue.
DIV 2 - 250 problem
Problem Statement |
|||||||||||||
| Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks
live together in peace and harmony. The ducks are numbered by
distinct positive integers from A to B, inclusive, where A <= B. Last night, Mr. Dengklek could not sleep, so he tried to count all the ducks in the kingdom. (It is known that counting ducks can help people to fall asleep.) When counting the ducks, Mr. Dengklek walked across an imaginary meadow and whenever he saw a new duck, he called out its number. He only called out actual duck numbers, i.e., numbers from A to B. He never called the same number twice. The numbers he called out are not necessarily in the numeric order. You are given a vector <int> ducks. The elements of ducks are the numbers Mr. Dengklek called out when counting the ducks last night. It is possible that he missed some of the ducks. Obviously, the number of ducks he missed depends on the values A and B. The values of A and B are unknown to you. Compute and return the smallest possible number of ducks Mr. Dengklek might have missed. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | ducks will contain between 1 and 50 elements, inclusive. | ||||||||||||
| - | Each element of ducks will be between 1 and 100, inclusive. | ||||||||||||
| - | All element of ducks will be distinct. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
Logic.
Sort "ducks", which will make ducks[0] == A and ducks[N-1] == B, where N = is length of duck.
Since ducks do not have a same number, (B-A+1) - N is our answer.
Source Code.
class DengklekTryingToSleep {
public:
int minDucks(vector <int>);
};
int DengklekTryingToSleep::minDucks(vector <int> ducks) {
sort(ducks.begin(), ducks.end());
int N = ducks.size();
int A = ducks[0];
int B = ducks[N-1];
return ( (B-A+1) - N);
}
DIV2 - 600 point problem
Problem Statement |
|||||||||||||
| Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks
live together in peace and harmony. Mr. Dengklek works as a chain maker. Today, he would like to make a beautiful chain as a decoration for one of his lovely ducks. He will produce the chain from leftovers he found in his workshop. Each of the leftovers is a chain piece consisting of exactly 3 links. Each link is either clean or rusty. Different clean links may have different degrees of beauty. You are given a vector <string> chains describing the leftovers. Each element of chains is a 3-character string describing one of the chain pieces. A rusty link is represented by a period ('.'), whereas a clean link is represented by a digit ('0'-'9'). The value of the digit in the clean link is the beauty of the link. For example, chains = {".15", "7..", "532", "..3"} means that Mr. Dengklek has 4 chain pieces, and only one of these ("532") has no rusty links. All links have the same shape, which allows Mr. Dengklek to concatenate any two chain pieces. However, the link shape is not symmetric, therefore he may not reverse the chain pieces. E.g., in the above example he is able to produce the chain "532.15" or the chain ".15..37..", but he cannot produce "5323..". To produce the chain, Mr. Dengklek will follow these steps:
Return the largest possible beauty a chain can have according to the above rules. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Notes |
|||||||||||||
| - | Mr. Dengklek is not allowed to remove and discard individual links before concatenating the chain pieces. | ||||||||||||
| - | If all links in the input are rusty, Mr. Dengklek is forced to select an empty sequence of links. The beauty of an empty sequence is 0. | ||||||||||||
Constraints |
|||||||||||||
| - | chains will contain between 1 and 50 elements, inclusive. | ||||||||||||
| - | Each element of chains will contain exactly 3 characters. | ||||||||||||
| - | Each character in each element of chains will be either a '.' or one of '0'-'9'. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
| 5) | |||||||||||||
|
|||||||||||||
Logic.
Let's start by recognizing patterns.
Let n = a number.
Let Golden Rule = Mr.Denglek picks only contiguous sequence of links that contains no rusty links.
#1. All "nnn" chain will be included in answer.
Proof.
A chain made of all numbers can fit anywhere, so it will be optimal to include it in the answer.
The least you can get is 0 by adding it, so it wouldn't "hurt" the optimal solution.
#2 Only one of chain with format either ".nn" or "..n" can be included in answer.
Proof.
Apply Golden Rule.
Since ".nn" and "..n" both have a rusty link at its leftmost position. they can be connected by other chains only with their right link. ex> ".nn" + "nnn"
#3 Only one of chain with format either "n.." or "nn." can be included in answer.
Proof.
Same as #2
#4. Chains with format "n.n" can use only one of its numbers as a part of answer.
According to Golden Rule, he has to stop when he reaches "."
#5 Chain with format ".n." can only used as a single link.
Algorithm.
Answer will have a format left + middle + right.
Go through each string in chains, find which chain can be include in left, middle, and right, and store their maximum values.
Find a combination that results in maximum value.
Also, check for a single chain that results in maximum value. This is to prepare for cases like "7.1", ".3.", where an answer is made of a single link. ( I forgot to do this during test).
Source Code. (it passed system test.)
int toInt(char ch)
{
if(ch == '.') return 0;
return (ch - '0');
}
int DengklekMakingChains::maxBeauty(vector <string> chains) {
int left = 0;
int right = 0;
int mid = 0;
int solo = 0;
int maxSideL = 0;
int maxSideR = 0;
vector<int> sideL;
vector<int> sideR;
int N = chains.size();
for(int i=0; i < N; i++)
{
string cur =chains[i];
int len = cur.size();
bool isDot1 = (cur[0] == '.');
bool isDot2 = (cur[1] == '.');
bool isDot3 = (cur[2] == '.');
bool isSolo = (isDot1 && !isDot2 && isDot3);
bool isSide = (!isDot1 && isDot2 && !isDot3);
bool isRusty = (isDot1 && isDot2 && isDot3);
bool isLeft = (isDot1);
bool isRight = (isDot3);
bool isMiddle = (!isDot1 && !isDot2 && !isDot3);
int now = 0;
for(int j=0; j < len; j++)
now += toInt(cur[j]);
if(isSolo)
{
solo = max(solo, now);
}
else if(isSide)
{
maxSideL = max(maxSideL, toInt(cur[2]));
maxSideR = max(maxSideR, toInt(cur[0]));
sideL.push_back(toInt(cur[2]));
sideR.push_back(toInt(cur[0]));
}
else if(isMiddle)
{
mid += now;
}
else if(isRusty)
{
continue;
}
else if(isLeft)
{
left = max(left, now);
}
else if(isRight)
{
right = max(right ,now);
}
}
int S = sideL.size();
int best = 0;
//left + middle + right
best = max(best, left + right);
//left + middle + side
best = max(best, left + maxSideR );
//side + middle + right
best = max(best, maxSideL + right );
//side + middle + side
for(int i=0; i < S; i++)
{
for(int j=0; j < S; j++)
{
if(i==j) continue;
best = max(best , sideL[i] + sideR[j]);
}
}
solo = max(solo, left);
solo = max(solo, right);
solo = max(solo, mid);
solo = max(solo, maxSideL);
solo = max(solo, maxSideR);
return max(solo ,(mid + best));
}
No comments:
Post a Comment