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

×

MAGICHEF - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Shivam Gupta
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

CAKEWALK

PRE-REQUISITES:

Looping, Conditionals Basic Coding .

PROBLEM:

There is a gold coin under box at index $X$. $S$ swaps are performed where two boxes are exchanged. We need to tell that finally, i.e. after all swaps are done, which indexed box has gold coin under it.

QUICK-EXPLANATION:

Key to AC- Having coded 5-6 problems from cakewalk question is enough to solve this problem. Looping, Conditionals and swapping of variables is needed.

We initially know that gold coin is under box $X$. For each swap, we know the indices $(i,j)$ of the boxes which are being swapped. We form basic conditions of form-

  • Let $Curr$ hold the index of box under which coin is initially. By the question, $Curr=X$ initially. Now, for every swap, the following holds-
  • If $i\neq Curr$ and $j \neq Curr$- Do nothing. We dont care about such swaps.
  • If $i==Curr$, then it means that box $i$ and $j$ are swapped, and coin was initially in box $i$. Now, after swapping, it will be under box at index $j$. Hence, we assign $Curr=j$.
  • If $j==Curr$ then by same reasoning we assign $Curr=i$.
  • $i==j==Curr$ , we need to do nothing. (I dont think this case exists in the question XD).

The final ans is in $Curr$. Please note I followed standard programming convention of $=$ representing assignment operator and $==$ representing "Check for Equality" operator.

EXPLANATION:

This is one of the editorial where Quick Explanation more than sums up everything about the logic. Instead of making editorial unnecessarily lengthy by formulating the logic again, lets focus on implementation.

In case there is any doubt of logic under Quick Explanation, do ask. I kept it short as it was simply common sense. The gist of the logic is, if the coin is currently under any one of the bowls, $i$ or $j$, then it will be in the other bowl with which we swapped after the operation. Keep a track of which bowl the coin is CURRENTLY in.

Taking the input is trivial, but with that being said, let me introduce you to Fast Input-Output methods. The rule of thumb says, if number of input is $>10^5$ or output $>10^5$, use fast input-output to save precious time. Else, many times correct solutions get TLE due to huge time wasted in IO operations.

Maintain a temporary variable to store answer. I used $currAns$. After this, implement the conditionals mentioned above. Remember that, for cases where ($i \neq currAns$ $\&\&$ $j \neq currAns$) and $(i==currAns \&\& j==currAns)$ we dont need to do nothing, hence we ignore them. We only handle the remaining $2$ cases. Implementation in tab below-

View Content

SOLUTION

The code is pasted in tabs below for you guys to refer in case solution links dont work.

Setter

Tester

View Content

Editorialist

View Content

$Time$ $Complexity=O(S)$ per test case
$Space$ $Complexity=O(1)$

CHEF VIJJU'S CORNER :D

1. Swapping variables here and there kind of reminds me of the std::swap function of C++ STL. Its a nice function which comes in handy for beginners and professionals alike. It can swap variables, arrays, vectors, queues...you pretty much get it XD.

2. Why did Chef bother accepting Magicians challenge if he needs us to help him? -_-

3. Related Problems: Frankly, the entire beginner section is filled to brim with such level problems. Solve any random problem from there, EXCEPT

  • Rupsa and Game
  • Chef and Weird Game.
  • One more Weird Game.

List item

This question is marked "community wiki".

asked 07 Sep '18, 00:12

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 18 Sep '18, 12:54

admin's gravatar image

0★admin ♦♦
19.8k350498541


https://www.codechef.com/viewsolution/20123005

Please check why is it getting WA?

link

answered 17 Sep '18, 22:51

learnhtc's gravatar image

1★learnhtc
12
accept rate: 0%

Just add this after line 6:
while (t--) {
and a closing brace in the end.

(18 Sep '18, 01:56) the_extractor4★

https://www.codechef.com/viewsolution/20047736

Can someone explain why is this solution giving WA?

link

answered 18 Sep '18, 19:19

anirxdh's gravatar image

1★anirxdh
11
accept rate: 0%

You have a more-than-usually magic coin. In your code, swapping two boxes means the coin always ends up under one of them, even if it was not under either to start with.

(18 Sep '18, 19:30) joffan5★

https://www.codechef.com/viewsolution/20085700

Can someone explain why is this solution giving WA?

link

answered 19 Sep '18, 11:52

sonu007's gravatar image

1★sonu007
1
accept rate: 0%

For the following case, your code prints 1 instead of 3:
3 1 2 2 3 1 3

(19 Sep '18, 15:55) the_extractor4★

You probably want to check the last element of answer instead of ans[i-1].

(19 Sep '18, 15:55) vijju123 ♦♦5★

https://www.codechef.com/viewsolution/20243312

Why does this give WA, please help, someone?

link

answered 19 Sep '18, 23:04

moonking's gravatar image

2★moonking
1
accept rate: 0%

std::cout<<x;

Ans of each test case must be printed in a new line. Make it std::cout<<x<<endl;

(19 Sep '18, 23:41) vijju123 ♦♦5★

https://www.codechef.com/viewsolution/21350841

can anyone tell why this is giving wrong answer

link

answered 31 Oct '18, 20:38

manisimu555's gravatar image

2★manisimu555
1
accept rate: 0%

You never produce any output, because you never enter the main loop. You missed:

cin>>n;

to read the number of test cases.

(01 Nov '18, 00:05) joffan5★
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,689
×3,770
×240
×191
×33
×12

question asked: 07 Sep '18, 00:12

question was seen: 1,147 times

last updated: 27 Dec '18, 19:42