You are not logged in. Please login at www.codechef.com to post your questions!

×

GERALD03 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Gerald Agapov
Tester: Tasnim Imran Sunny
Editorialist: Jingbo Shang

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

Given a sequence of intervals [Li, Ri], try to transform them one by one using L+, L-, R+, R- in the shortest operation sequence. Tie breaker is the lexicographical order.

EXPLANATION:

Actually, you only need to consider how to transform [A, B] to [C, D].

The first key point is that, the length of shortest operation sequence equals to |A - C| + |B - D|. This is almost straightforward, because we can always move one end towards its target.

The second one is that we can enumerate the next step (4 operations) and greedily choose the minimum one (both length and lexicographical order). This is because the lexicographical order is determined by the first different character.

The only trick is to remember that you must avoid L = R during this process.

This algorithm's time complexity is O(Len), where Len is the length of output.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 23 Dec '13, 00:11

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

edited 23 Dec '13, 00:46


@admin I came here to know the trick to avoid L = R with maintaining lexicographical order and what I get is The only trick is to remember that you must avoid L = R during this process. Really disappointing from codechef side.

Thanks & Regards
CrucifiX

link

answered 23 Dec '13, 10:16

crucifix's gravatar image

1★crucifix
7213810
accept rate: 18%

This is quite simple honestly. You only need to enumerate all four operations, and first check whether they lead to L = R. And then, for all valid operations, check whether they are shortest by judging the distance (formula given in the editorial). In the end, choose the lexicographical smallest one among the operations which are still valid after 2-step checks.

(23 Dec '13, 10:58) shangjingbo ♦♦3★

@crucifix, considering that lexicographical order of the operations is: L+, L-, R+, R- you can transform the interval following this order. L==R only occurs for the first operation. If you follow these operations in the proper order it's impossible to have a conflict for the second operation since R is already bigger than L and it's impossible for the 3rd and 4th operations since L has already been transformed in one of the previous operations and the case L==R has been dealt with in the first operation. I think this is more understandable by the following pseudo code to transform from one interval to the other:

total = number of operations done so far
answer = string of operations done so far

L = current value of L
R = current value of R
nextL = L value of the next interval
nextR = R value of the next interval

while(L < nextL) { // first operation "L+"

    // check for the special case first since we are increasing L
    if(L == R-1) {
       R = R+1; // increase R because if L < nextL then surely R < nextR
       total = total + 1;
       add string "R+" to answer;
    }

    L = L+1;
    total = total + 1;
    add string "L+" to answer;

}

// for the remaining loops we don't have to check the special case

while(L > nextL) {
    L = L-1;
    total = total + 1;
    add string "L-" to answer;
}

while(R < nextR) {
    R = R+1;
    total = total+1;
    add string "R+" to answer;
}

while(R > nextR) {
    R = R-1;
    total = total+1;
    add string "R-" to answer 
}
link

answered 24 Dec '13, 16:35

junior94's gravatar image

4★junior94
3.2k143058
accept rate: 15%

edited 27 Dec '13, 00:42

@junior94 consider the case [4 3] to [2 3]. here L- will go through the following stage [4 3]->[3 3]->[2 3], which is not valid.

(25 Dec '13, 11:39) paramvi3★

@paramvi that cannot happen because the input [4 3] is not valid. Check the constraints on the problem statement page: l<r. The code I wrote is strongly based on that assumption and that's why we only have to check for the special case in the first while block.

(27 Dec '13, 00:38) junior944★

@admin - In the tester's solution, inside the condition l>pl he has checked for this condition while(pl!=pr-1) { ans+="L+"; pl++; if(pl==l) break; }

But he has not used this condition in the (l<=pl) condition. Why? Because in that case also pl can become equal to pr which we do not want.

link

answered 26 Dec '13, 12:59

hawk001's gravatar image

2★hawk001
1
accept rate: 0%

Because we need to avoid pl == pr.

(01 Jan '14, 14:32) shangjingbo ♦♦3★

can anyone tell me where i m going wrong? http://www.codechef.com/viewsolution/3478768

link

answered 27 Feb '14, 18:59

Sandeepripping's gravatar image

4★Sandeepripping
1
accept rate: 0%

i realised my mistake..sorry for any trouble caused

(27 Feb '14, 19:08) Sandeepripping4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×3,764
×1,000
×6

question asked: 23 Dec '13, 00:11

question was seen: 4,188 times

last updated: 27 Feb '14, 19:08