Блог пользователя th3_g0d

Автор th3_g0d, 11 лет назад, По-английски

:) 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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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.me/blog/entry/9867

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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);
}
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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. :)