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

×

RAINBOWA Help

I'v been keeping this problem in my TODO list ever since it came out. I am still not able to crack it. I get the problem's requirement but am facing problems while implementing it. I am trying to first check if the input number is palindrome or not by a[i] == a[n-i-1] logic. But after that I am not able to put the logic of checking if the next number is in the sequence part to code. I am trying to set a variable j = 1 and check if(a[i+1] == j+1) then increment j then compare the elements with j.. It should end when next element is not equal to j or j > 7. I know this logic is filled with flaw. Also I read the editorial which further increased my confusion by using ones(1). Please help me by simplifying the logic of RAINBOWA problem.

asked 19 Oct '17, 20:57

montycs's gravatar image

0★montycs
1054
accept rate: 0%


@montycs -

Of course.

His solution checks for the palindrome property, which is first part of solution. Thats half of the solution. What you need to do next is-

We need to make sure about the part that it starts from 1, goes upto 7, and ends at 1 again. What you can do is-

  1. Check if it starts and ends at 1.
  2. The difference between any 2 consecutive numbers is ATMOST 1 [i.e. 0 or 1 -can be equal, or increasing by 1 in first half, in second half, can be 0 or decreasing by 1].
  3. Presence of 7 has been already checked
  4. Check that the first half is continuously increasing/non-decreasing, and next is continuously decreasing/non-increasing.

Its better to check out some good coder's AC codes along with what I said, and you will see how easy it is to implement all of this.

link

answered 20 Oct '17, 19:07

vijju123's gravatar image

5★vijju123 ♦
14.4k11653
accept rate: 18%

This other day I was solving VOTERS problem on codechef and for reference I looked your code and I must admit it was really well commented code. So is it possible for you to do the same in RAINBOWA problem?

(20 Oct '17, 19:30) montycs0★

Of course. Give me a minute.

(21 Oct '17, 01:03) vijju123 ♦5★

Can't thank enough bro.. Also, is it possible for me to comment on the solution link of one of your solved problems just so that you could add comments on that specific solution link?

(21 Oct '17, 17:10) montycs0★

You can always mail me a request. I add comments for those codes. :)

(21 Oct '17, 18:20) vijju123 ♦5★

@spp_

Your code isnt correct. I really dont know how you got AC since I dont recall the problem having weak test cases.

Here is the TC-

Input
1
11
7 7 7 7 7 7 7 7 7 7 7
Your Output
yes
Expected Output
no //Rainbow array MUST begin and end with 1.
//n can be anything. 11, 20, 55. The pattern matters here.

So yup, you got lucky :p . I will ask @admin to add this, and few more, corner cases. (Lol, shes gonna rip my head off for I am giving her so much work to do....but NEVERMIND XDXD)

@montycs , please make sure to verify the answers before accepting. You'd help us a big deal if you guys verify, give a check, ask doubts, clarify and then accept. A wrong answer being accepted is bound to confuse some user or other, especially those who search the forums to clarify their doubts.

Thanks! :)

link

answered 20 Oct '17, 01:16

vijju123's gravatar image

5★vijju123 ♦
14.4k11653
accept rate: 18%

edited 20 Oct '17, 01:20

Can you improvise his logic? because his logic was almost correct except for not checking the number sequence..

(20 Oct '17, 18:45) montycs0★

take c=0;

1)If middle element of the array is not 7 then c=1;

2)now first element of the array should be equal to the last element of the array,if not c=1;

3)similarly 2nd ele should be equal to 2nd last ele,if not c=1;

4)repeat this process before the middle of the array

5)now if your c remains 0 print "yes" else "no"

6)here is my accepted code.

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

link

answered 19 Oct '17, 21:10

spp____'s gravatar image

2★spp____
1.1k210
accept rate: 8%

1

nice 1....

(19 Oct '17, 21:17) montycs0★

@vijju123 thanks

link

answered 20 Oct '17, 09:17

pandey_96's gravatar image

1★pandey_96
667
accept rate: 0%

@vijju123 Can you please warn me what i missed this suggested algorithm? I really spend a lot of time about it and try all of the below test cases.

import java.io.*;

public class RAINBOWA {
private static boolean isCodechefModeOn = false;
static final String no = "no";
static final String yes = "yes";

public static void main(String[] args) throws IOException {
    BufferedReader br = createInputStream();
    int testCaseCount = Integer.parseInt(br.readLine());
    for (int i = 0; i < testCaseCount; i++) {
        int lenght = Integer.parseInt(br.readLine());
        System.out.println(checkRainbowArray(br.readLine(), lenght));
    }
    br.close();
}

static String checkRainbowArray(String line, int lenght) {
    String[] sArray = line.split(" ");
    if (lenght % 2 == 0) {
        return no;
    }
    int pivotIndex = (lenght - 1) / 2;
    if (Integer.parseInt(sArray[pivotIndex]) != 7) {
        return no;
    }
    int lastIndex = lenght - 1;
    int current = Integer.parseInt(sArray[0]);
    if (current != 1) {
        return no;
    }
    int i = 0;
    while (current != 7) {
        int diff = Integer.parseInt(sArray[i + 1]) - Integer.parseInt(sArray[i]);
        if (diff != 0
                && diff != 1) {
            return no;
        }
        if (Integer.parseInt(sArray[i]) != Integer.parseInt(sArray[(lastIndex - i)])) {
            return no;
        }
        i++;
        current = Integer.parseInt(sArray[i]);
    }
    int check = 2 * i + 1;
    if (check != lenght) {
        return no;
    }
    return yes;
}

private static BufferedReader createInputStream() throws FileNotFoundException {
    InputStreamReader isr = null;
    if (isCodechefModeOn) {
        isr = new InputStreamReader(System.in);
    } else {
        String path = System.getProperty("user.dir");
        String filePath = path + "/RAINBOWA.txt";
        FileInputStream fis = new FileInputStream(filePath);
        isr = new InputStreamReader(fis);
    }
    BufferedReader br = new BufferedReader(isr);
    return br;
}
}

and all passed test cases on my local:

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class RAINBOWATest {

    @Test
    public void testPositive() {
        assertEquals(RAINBOWA.yes, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 7 6 5 4 3 2 1", 13));
    }

    @Test
    public void testInitialCases() {

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 4 5 6 7 6 5 4 2 1", 11));

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 8 6 5 4 3 2 1", 13));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 7 6 5 4 3 1 1", 13));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("2 1 3 4 5 6 7 6 5 4 3 1 2", 13));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("2 2 3 4 5 6 7 6 5 4 3 2 2", 13));

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 7 6 5 4 3 2 1 1", 14));

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 7 8 6 5 4 3 2 1", 14));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 6 7 8 6 5 4 3 2 1", 15));
        assertEquals(RAINBOWA.yes, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 6 7 6 5 5 4 3 2 1", 15));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("8 2 3 4 5 5 6 7 6 5 5 4 3 2 8", 15));
        assertEquals(RAINBOWA.yes, RAINBOWA.checkRainbowArray("1 1 2 3 4 5 6 7 6 5 4 3 2 1 1", 15));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 7 7 7 6 5 4 3 2 1", 15));

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 4 5 8 7 8 6 5 4 4 3 2 1", 16));

        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 6 7 7 7 8 6 5 4 3 2 1", 17));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 6 8 7 8 6 5 5 4 3 2 1", 17));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 6 6 7 6 7 6 6 5 4 3 2 1", 17));

        assertEquals(RAINBOWA.yes, RAINBOWA.checkRainbowArray("1 2 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 2 1", 19));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("9 2 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 2 9", 19));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 4 5 6 6 7 7 7 6 6 5 4 4 3 2 1", 19));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 4 5 8 6 6 7 6 6 8 5 4 4 3 2 1", 19));

    }

    @Test
    public void testCornerCases() {
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 7 5 5 4 3 2 1", 13));
        assertEquals(RAINBOWA.no, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 7 5 5 4 3 2 1", 13));
        assertEquals(RAINBOWA.yes, RAINBOWA.checkRainbowArray("1 2 3 4 5 5 5 6 7 6 5 5 5 4 3 2 1", 17));
    }
}

I got wrong answer at codechef.

Thanks @vijju123, i fix my issue, the problem is i assume all array should be even otherwise it can't be polidrome by definition. But it is wrong take vijju123's example below comments "1 2 3 4 5 6 7 7 6 5 4 3 2 1", this one also a rainbox array. Finally i update my code according to that. This is my valid solution:

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

link

answered 17 Dec '17, 21:14

erhun's gravatar image

1★erhun
112
accept rate: 0%

edited 21 Jan, 14:32

The question requires you to do 3 things-

  1. Check starting element is 1.
  2. Difference between consecutive elements is 1, and max element is 7.
  3. The array is palindromic.

The length can be odd, and also even (as both, odd and even length arrays are palindromic- number of 7 can be arbitrary). You cannot use-

So-

if (lenght % 2 == 0) { return no; }

Is wrong. There are many other such errors, so i suggest to re-write your code with my points in mind.

(18 Dec '17, 13:01) vijju123 ♦5★

First of all thanks for answer, just wonder how an array can be even and pass all these checks. I mean if array is palindromic and middle element is 7 how is it possible an even array length case. I hope you understand my point.

(19 Dec '17, 03:20) erhun1★

Take this-

1 2 3 4 5 6 7 7 6 5 4 3 2 1

The problem nowhere says the middle element should be 7 , but it says that value should start at 1, go upto 7 and atlast symmetrically go back to 1. As such, number of 7 can be arbitrary.

(19 Dec '17, 15:10) vijju123 ♦5★
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:

×1,512
×193
×5

question asked: 19 Oct '17, 20:57

question was seen: 447 times

last updated: 21 Jan, 14:32