th3_g0d's blog

COCI 2013/2014 Round #3
By th3_g0d, 11 years ago, In English

:) Hello everyone,

Yesterday took place Round#3 of Croatian olympiad.

It seemed to me that contest was a bit unbalanced because first 3 problems were easier than usual. However, the 4th one seemed more complicated than usual. I think it would be great if people would share their ideas about problems here.

Could anyone explain the approach for problem 4? I think we had to use Binary Search there to find the amount of meat. However, I could not find the way I had to build my binary search. I think there was only a certain continuous range of solutions. Though, I could not figure out how and when to change the bounds of binary search.

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

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

Every 4-tuple (Ai-1, Ai, Bi-1, Bi) limits feasible K by upper or lower bound using following formula:

Ai-1 + K*Bi-1 >= Ai + K*Bi

K*(Bi-1 - Bi) >= Ai - Ai-1

K>= (Ai - Ai-1)/(Bi-1 - Bi) if (Bi-1 - Bi) is positive

K <= (Ai - Ai-1)/(Bi-1 - Bi) if (Bi-1 - Bi) is negative

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

At 4th problem: If the total amount of meat the butcher distribute is T and we denote X = a convenable "division" of T, such that each person receive X * B[i] kilos of meat (this is the explanation of that ratio, mentioned in the text), we can transform the problem into a system of inequalities: A[1] + X * B[1] >= A[2] + X * B[2] >= ... >= A[N] + X * B[N]. From these inequalities, we can obtain a lowerbound and an upperbound for X, and the answer is LowerBound_for_X * (B[1] + B[2] + ... + B[N]). Time complexity: O(N ^ 2) :)

LE: I haven't seen Dixtosa's post.

LLE: There is another blogpost about COCI: http://codeforces.net/blog/entry/9867

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, right I didn't see that blogpost. Thank you :)

    Btw, I understood the solution. I was also making the system of inequalities. I rushed and thought that nothing outcomes from it. Thank you!

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

To me, the problems seemed to be reasonably hard this time (I found the 4th around as hard as the 3rd, though). At least compared to the 1st contest of this year, where 1-5 were really easy and the 6th was really hard and without balanced test cases (a bruteforce was given the same amount of points as a much more advanced KMP-using solution). I didn't solve the 6th problem this time either because I didn't have enough time, but I had a complete idea and it wasn't that hard to implement.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    The 4th one seemed harder than the 3rd one to me. Because in 3rd one we just had to implement what was said in a careful manner. However, 4th one required an aprroach that was not straightforward.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      There's more to difficulty of a problem than just if it requires an idea. The 3rd has an annoying implementation (even if you write a short one, it's just hardwiring values and casework, nothing algorithmic — in this case, it's a downside). Also, the 4th has low constraints, so slow solutions can pass, the idea is easy (basic math) and the implementation is just about re-writing formulas you've written on paper.

      Also, it's subjective, so it's fine if opinions differ.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For me, problem 3 was trivial, and problems 4 and 5 were of almost equal difficulty. Problem 4 required only a short code but a correct implementation was tricky (I didn't get full points even if my idea was correct, maybe some problems with double numbers).

        Is there a simple slow and correctly working solution for problem 4?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I got only 60 points with double ! after contest , I used printf("%.12lf") then I got 120 point! probably this is your wrong !

          → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah right. Actually I see what you mean. Each of the problems had its own difficulties in different ways.

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

I solved it with binary search.
Here is my code : 

int isit(double x)
{
	for(int i=0; i<n; i++)
		N[i] = A[i] + B[i]*(x/all);
	
	for(int i=1; i<n; i++)
			if(N[i-1] < N[i])
				return 0;
	
	return 1;
	
}

int tap(double x)
{
	for(int i=0; i<n; i++)
		N[i] = A[i] + B[i]*(x/all);
	
	for(int i=0; i<n; i++)
		for(int j=i+1; j<n; j++)
			if(N[i] < N[j]  &&  A[i] < A[j])
				return 1;
	
	return 0;
}

double galany(double b,double l,double r,int cnt = 0)
{
	if(cnt > 40)	return r;
	if(isit(b+l))		return l;
	if(isit(b+r))		return r;
	
	double mid = l + (r-l)/2.0;
	
	if(tap(double(b + mid)))	return galany(b, mid, r, cnt+1);
	return galany(b, l, mid, cnt+1);
}

double b_s(int l,int r)
{
	if(r-l < 2)
	{
		double a = (double)l + galany((double)l, 0.0, 1.0);
		double b = (double)r + galany((double)r, 0.0, 1.0);
		if(isit(a))	return a;
		if(isit(b))	return b;
		return -1.0;
	}
	
	int mid = (l+r)/2;
	
	if(tap(double(mid)))	return b_s(mid, r);
	return b_s(l, mid);
}
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I think it would be much better if you not just pasted your code but also gave some explanations for your solution. Otherwise, not many people can really benefit from what you post. :)

    → Reply