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

×

BRLADDER - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kamil Dębowski
Testers: Hasan Jaddouh, Sergey Kulik
Editorialist: Pawel Kacprzak

DIFFICULTY:

Cakewalk

PREREQUISITES:

Elementary math

PROBLEM:

For a given infinite ladder graph $G$ with vertices numbered from $1$, and integer $Q$, the goal is to answer $Q$ queries. Each query contains two integers $a$ and $b$ and asks if there is an edge between vertices $a$ and $b$ in $G$.

There are $3$ types of edges between vertices of $G$:

  1. There is an edge between vertices labeled with two consecutive numbers if and only if the smaller label is odd

  2. There is an edge between vertices labeled with two consecutive odd numbers

  3. There is an edge between vertices labeled with two consecutive even numbers

EXPLANATION:

In order to solve the problem, we are going to answer queries one after another. For a fixed query $(a, b)$, we simply check if $a, b$ can form an edge within any of the classes defined above. Notice that performing such a check for each class is easy:

Class 1: Checking if $a, b$ forms an edge of the first class can be done by just checking if the smaller label is odd and the difference between the larger and the smaller label is exactly $1$.

Classes 2 and 3: Checking if $a, b$ forms an edge of either the second or the third class can be done by just checking if the difference between the larger and the smaller label is exactly $2$.

Since performing each of the above checks takes a constant time, the total complexity of the solution is $O(Q)$.

AUTHOR'S AND TESTER'S SOLUTIONS:


Setter's solution can be found here.
First tester's solution can be found here.
Second tester's solution can be found here.

This question is marked "community wiki".

asked 25 Mar '17, 19:03

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 25 Mar '17, 22:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


The links of first tester's solution and second tester's solution are not working again(also not working in SPECIES).

alt text

alt text

link

answered 26 Mar '17, 00:51

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

Hello everyone,

I am new here. Can someone guide me what I am doing wrong in the following code. Seems to run fine when i check it on my computer but when i submit it on codechef, it says wrong answer.

thank you

#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
    int Q;
    long int a,b;
    cin>>Q;
    if(Q>1000)
        {
            cout<<"Err: no. of queries too high";
            exit(1);
        }
    bool *p;
    p = new (nothrow) bool[Q];
    for(int i=0;i<Q;i++)
    {
        cin>>a>>b;
        if ((abs(a-b)==2))
            p[i]=1;
        else if((a-b)==1 && a%2==0)
            p[i]=1;
        else if((b-a)==1 && b%2==0)
            p[i]=1;
        else
            p[i]=0;
    }
    for(int i=0;i<Q;i++)
    {
        p[i]==1? cout<<"yes": cout<<"no";
        cout<<'\n';
    }

    delete[] p;
    return 0;

}
link

answered 02 Apr '17, 15:52

kush0995's gravatar image

0★kush0995
1
accept rate: 0%

@kush0995 the output should be in caps ie. replace "yes" with "YES" and "no" with "NO" in your code.

happy coding:)

link

answered 02 Apr '17, 16:41

ankur_dhir95's gravatar image

4★ankur_dhir95
303
accept rate: 0%

Hello everyone.. Another approach of solving this problem can be:- 1.finding minimum of two...min(a,b) 2.finding maximum of two...max(a,b)

include "bits/stdc++.h"

using namespace std;

int main() { int t; cin>>t; while(t--) { long int a,b; cin>>a>>b; int mn=min(a,b); int mx=max(a,b); double c=(double(mn-1))/2; double d=(double(mx-2))/2; if(abs(a-b)==2) cout<<"YES\n"; else if(int(c)==c && d==int(d) && int(c)==int(d) ) cout<<"YES\n"; else cout<<"NO\n"; } } it is checking for value in double and value in int to be same.

link

answered 02 Apr '17, 19:06

adhish_kapoor's gravatar image

3★adhish_kapoor
90411
accept rate: 9%

edited 02 Apr '17, 19:08

My code isn't working. It works fine on my computer but when I submit it to codechef...it shows that I have a wrong answer...Can someone please please please tell me what is wrong with my code.

include <stdio.h>

int main() { int i,queries,city_1,city_2; printf("Enter the number of queries you would like to check:\n"); scanf("%d",&queries); while(queries<=0) {

 printf("Please enter valid number of queries:\n");
 scanf("%d",&queries);
}
while (queries>0)
{queries=queries-1;
printf("Enter numbers of city 1 and city 2 separated by a single space:\n");
scanf("%d%d",&city_1,&city_2);
if (city_1-city_2==1 || city_2-city_1==1)
 {if(city_1>city_2)
   i=city_2-1;
else    if (city_2>city_1)

i=city_1-1;

if (i%2==0) printf("YES\n"); } if(city_1-city_2==2 || city_2-city_1==2) printf("YES\n"); else printf("NO\n");

}

return 0;

}

link

answered 12 May '17, 00:58

squidsofwar's gravatar image

0★squidsofwar
1
accept rate: 0%

Please upvote me I don't have enough karma points to ask question. Thank you!

link

answered 12 May '17, 08:14

dat160601's gravatar image

3★dat160601
1
accept rate: 0%

I think it would be noteworthy to mention that one is not expected to check whether for example the road no. 3 and road no. 7 connects or not. Although it remains ambiguous in the question. I hope may be it gets mentioned in the editorial .If I am not wrong you just need to find the immediate road that is connected to the first no. "a".

link

answered 11 Jun '17, 23:37

faruk13's gravatar image

2★faruk13
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,855
×1,692
×30
×7

question asked: 25 Mar '17, 19:03

question was seen: 1,790 times

last updated: 11 Jun '17, 23:37