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

×

ICL1701 - EDITORIAL

PROBLEM LINK:

Practice

Contest

Author: Bhuvnesh Jain

Tester: Ankit Sultana

Editorialist: Bhuvnesh Jain

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic Looping techniques

PROBLEM:

Find any valid sequence of magic operations so that all the cards face upwards.

EXPLANATION:

The only observation for this problem required is that the magic operation on the rightmost card affects only itself and not any other card.

So, we simply do a linear scan from left to right and whenever we encounter a card facing down, we perform the magic operation on it. This solution will tak atmost $O(n)$ steps as we can perform the magic operation on all the elements in the worst case. As per the constraints, $k >= n$, so the above solution will work.

COMPLEXITY

$O(n)$

Solution codes:

Setter's solution

asked 27 Mar '17, 00:05

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 28 Mar '17, 16:26

admin's gravatar image

0★admin ♦♦
19.8k350498541


We must do binary search in this question by comparing each element with its consecutive element.We must not do anything if its a positive no. but if its a negative no. there will be two cases-
1. the first element is negative and the second one is also negative.
2. the first element is negative and the second one is positive.
In the first case,the magic operation will make them both positive and so while doing binary search whenever we will encounter consecutive negative number , we will jump onto the next no. by leaving this pair.
In the second case,the magic operation will make the negative no. into positive and vice versa. And therefore we must swap these nos. until we get another negative no. in the array. And thus storing their position in some variable.

link
This answer is marked "community wiki".

answered 27 Mar '17, 00:46

karansingh97's gravatar image

2★karansingh97
1
accept rate: 0%

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,852
×593
×191
×16
×2

question asked: 27 Mar '17, 00:05

question was seen: 628 times

last updated: 28 Mar '17, 16:26