Pashmak and Flowers

Problem Link: http://codeforces.com/problemset/problem/459/B

This problem asks you to find how many ways you can pick 2 flowers from the flower fields. My approach was : get numbers for most beautiful and least beautiful flower, then multiply those numbers. I used map to store the numbers due to the input.

However, there was a problem: it’s possible that the input has only one kind of flower. So you’ll have to count how many ways you can pick 2 flowers using combinations ( nC2 ).

In case if you don’t know how to code combinations, or if you are too lazy, you can see it here :

http://stackoverflow.com/questions/9330915/number-of-combinations-n-choose-r-in-c

Onto the unknown and beyond !

So I decided to try AWS. One year ec2 service for 1$ sounds pretty good.

Had some problems with phone verification, sent a ticket and everything got solved smoothly.

The only problem I have is that I can’t really experiment around with multi instance stuff since I’m using the ec2 instance for a certain project.

I guess I’ll have to revisit Lightsail / Vultr and see if the project can actually run there.

Given Length and Sum of Digits…

Problem link : http://codeforces.com/problemset/problem/489/C

I’m pretty sure this one can be categorized as implementation. I simply create the largest number first, by using all the 9s on the first digits, then reverse the number to get the smallest one after substracting one from the rightmost non zero number in the largest number, and add it to the rightmost number in case if the rightmost number is zero.

There’s also a trap which I didn’t check… even if m is equal to zero it doesn’t always mean that there’s no answer (-1 -1)

Elections

Problem link : http://codeforces.com/problemset/problem/570/A

Direct Implementation, do what the problem tells you to do straight. No tricks on this one, except that indices starts from 1 , not 0.

Simply get the winner from each city, increment their final score, and finally find the candidate with highest score and lowest index ( in case if there are candidates with same final score)

This one’s pretty simple. However at first I thought I need to use [su_highlight background=”#feb0c1″]long[/su_highlight] instead of [su_highlight background=”#feb0c1″]int[/su_highlight] since the number of votes can be as high as 109. But then I realized that 109 is the highest value it can be, so [su_highlight background=”#feb0c1″]int[/su_highlight] would suffice

Chewbaсca and Number

Problem link : http://codeforces.com/problemset/problem/514/A

I guess this counts as implementation. I simply scan the number as a string, and flip them if their value is greater than 4 (the flipped value will be lower than 5, ensuring that we will get minimum value), with exception if the first number is equal to 9, don’t flip it since it will produce a leading zero.

Nothing special on this problem. It’s pretty simple and straightforward.

Devu, the Singer and Churu, the Joker

Problem link : http://codeforces.com/problemset/problem/439/A

Another implementation. I simply add up all the time required for the performance and store them in a temporary variable (let’s call it T).

Then, I add (n – 1) * 10 minutes to T. 10 minutes is the time required for Devu to rest. He only needs (n – 1) rests since his final rest can be simply excluded from the concert time.

Then, I check whether T exceeds d . If it does, I simply set the answer to minus one (means that time d isn’t enough even if Churu cracks no joke)

We know that Devu will have n – 1 rests. Which means that Churu can crack (n – 1) * 2 jokes while Devu was resting. If d – T does not equal to zero, we must include number of jokes Churu can crack in the remainder time. We can simplify it as

extraJokes = (d – T) / 5

This problem was pretty simple. However I did make a mistake : I thought that Devu would have n rests. Luckily, the test cases provided by the problem would trip this error. So I guess that is a good thing.

Buy A Shovel

Problem link : http://codeforces.com/problemset/problem/732/A

At first I was kinda confused, but in the end I opted for a simple brute force.

My initial idea was to create an array, mark arrays that is multiple of k with one and mark others with zero. Then iterate on each array, see if current array’s value is one, then whether we can form the index i with the coins. But I realized that there’s no need to store anything, so I simply iterate the multiple of k (We’ll call this k’) ,  see if we can be divide k’ by ten, or if the result of k’ % 10 equals to r.

Why ? We are allowed to use any combination of coins, so if ten coins can form value of k’, we reach our goal already. But if we can’t, we try adding r to the value and see if it forms k’. If we can’t form current k’, we advance by adding k to k’ until we find the right k’.

I’m still wondering if there’s a quicker way to solve this. I had something like instead of bruteforcing multiplies of k, what if we iterate on the amounts formed by ten coins and r instead ? But that I scrapped that idea since we’ll have to multiply k if the current k’ value surpasses current k’. I guess the way above works for now.

Fedor and New Game

Problem link : http://codeforces.com/problemset/problem/467/B

This problem was quite straightforward. The question states that a positive integer represents player’s army, and the binary representation of the integer tells us which troop types the player has. To find the answer, we compare Fedor’s army and all other players’ army to determine how many troop types differences are there, and from that determine if the player can be Fedor’s friend, finally count how many players can be his friend.

At first I was lazy, so I simply scanned all the numbers, directly XOR them with Fedor’s number, then count number of 1 bits manually.

And boom. TLE.

So I tried storing the numbers in form of bitset<32>. The rest is still the same. XOR them, get remaining number of 1 bits ( but this time I’m using bitset’s count() ) and boom. Accepted.

I’m still bit confused until now. I’m not sure which part fixed the TLE thing. Maybe bitset XOR is faster than integer XOR. Or maybe bitset’s count() is waay faster than

While number is not 0, modulus it by 2, append the remainder, divide it by 2, rinse and repeat

maybe.

I tried __builtin_popcount() but it didn’t help with the TLE. So bitset’s count() must be blazing fast.