Potla's blog

By Potla, 13 years ago, In English

I kinda liked this round. Although for the past few rounds, I've been either starting late, or not being able to solve the problems, I enjoyed this one. I don't know any programming, but I just wanted to write something here. I'm a noob at writing programs, so please excuse any mistakes I make. :)

Problem A. Even Odds

Nothing much to write about this one...

Problem B. Strings of Power

Hmm so my first impression when I saw this problem was like lolwut... :D So the idea is pretty simple: we scan the string from start to end, check for the words "heavy" and "metal", and construct a binary string of H and M. I used a boolean string with 1's wherever we encounter "heavy" and 0 for "metal." This way if we try to count the total number of substrings starting with 1 and ending with 0,  and store it in a variable "sum", then we can do the following: find the total number of 0's in the sequence obtained, and store it in a variable c. For each 1 encountered, just add c to the required sum, and for each 0,  decrement c by 1,  then add to sum. Basically, for each 1,  add the total number of 0's to the right of that 1. So anyway the required sum is obtained.

long long cntz=0;
for(long long i=0;i<(long long)A.size();i++)cntz+=!(A[i]); //A is the binary vector we computed
long long reqsum=0; //Required sum
for(long long i=0;i<(long long)A.size();i++)
{
	if(A[i]==1) reqsum+=cntz;
	else cntz--;
}
cout<<reqsum<<endl;

Problem C. Perfect Pair

I felt really bad that I missed this. It had so many tricky test cases that I had missed, or reversed the order of checking stuff, that in the end I could not pass the system tests, due to a TLE in the x > 0, y < 0 case. So there are some "trivial" cases we need to eliminate first.

  • WLOG assume x = max{x, y}. If not, swap x and y.
  • If x ≥ m,  then print 0 and go home.
  • If x < 0, y < 0 and m ≥ 0 then the sum anyway decreases, and this cannot be acheived. Print  - 1 and rejoice.
  • If x > 0 and y < 0... I failed to contemplate that my program might have failed in this case. After doing all that fibonacci precomputation, I had to go through a lot of trouble to fix this case. But well, I wrote a stupid for loop instead of just writing the number of steps required for y to cross zero. It's easy to note that the number is actually , since the optimum way of reaching positive numbers is to repeatedly add x to y,  ie using This way we reduce our problem to the final step.
  • If x > 0, y > 0 then the tricky part comes in. The optimal method of getting to m is going to be the following:
(x, y) → (x, x + y) → (2x + y, x + y) → (2x + y, 3x + 2y) → (5x + 3y, 3x + 2y) → ...

Hmm. 1, 1, 2, 3, 5, 8. Doesn't it remind us of something? So I precomputed the Fibonacci numbers till 1018,  stored them in an array of size 93,  and then wrote a simple for or while loop to check the number of iterations required. After i iterations, the maximum reaches fi·x + fi - 1·y,  so the rest is easy.

Here's my CPP code... o.O

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll f[93]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429};
int main()
{
	ll x,y,m;
	cin>>x>>y>>m;
	if(x<y){ll tmp=x;x=y;y=tmp;}
	if(x>=m) {cout<<"0\n";return 0;}
	if(m>0)
	{
		if(x<=0&&y<=0) {cout<<"-1\n";return 0;}
		ll i,j=0;
		if(y<0)
			j=(ll)floor(((-y)+x-1)/(x));
//		cerr<<j<<endl;
		y=y+j*x;
		for(i=2;(x*f[i]+y*f[i-1])<m;i++);
		cout<<(i-1+j)<<endl;
	}
	else
	{
		cout<<"-1\n";
	}
	
	return 0;
}

Will update this post with a solution to D too. I could not solve E myself, so probably waiting for the tutorials is the best option for me. :)

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

You can read official problem analysis here.

  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Oh thanks! I missed that out totally... Sorry about that. :) Still I enjoyed solving Problem C, so couldn't resist from writing a post. ^_^