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

×

DIGJUMP - Editorial

48
11

PROBLEM LINK:

Practice
Contest

Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

bfs, dijkstra

PROBLEM:

Given a string s of N. You have to go from start of the string(index 0) to the end of the string (index N - 1). From position i, you can go to next (i + 1) or previous (i - 1) position. You can also move from the current position to the indices where the character is same as current character s[i].

QUICK EXPLANATION

  • Minimum number of operations can not be greater than 19.
  • By your moves, you will never be visiting a single digit more than twice.
  • You can solve this problem by a modified bfs.
  • You can also make use of simple dijkstra's algorithm.

EXPLANATION

Few observations

  • Minimum number of operations can not be greater than 19. Proof:
    You can start from first position and go to rightmost index where you can directly go. Then from that position go to next position and keep repeating the previous step. Note that you will be visiting a single number at most twice. Hence you can at most make 19 moves because first digit will be visited once.

    They will 19 in the cases of 001122334455667788999.

  • By your moves, you will never be visiting a single digit more than twice.
    Proof:
    If you are using more than 2 moves for going from a digit to another, you can simply reduce one of the move by simply going from one of the position to other in just a single move. So you can simply keep the at most 2 moves for moving from a digit to another.

Wrong greedy strategies
Let us first discuss about some greedy strategies and figure out the reason why they are wrong.

From the current position, go to the rightmost index having same character/digit as the current character/digit. If this number does not occur again in the right part of array, then go to next position (ie. i + 1).

Please see the following recursive implementation of this strategy.

Pseudo Code

def greedy(int cur):
    // cur = N denotes end/ target position.
    if (cur = N) return 0;
    last = cur + 1;
    for i = cur + 1 to N:
        if (s[i] == s[pos]):
            last = i;
    return 1 + greedy(cur);

The above strategy will fail in these kind of cases: 010000561
According to greedy strategy, From 0, you will go to rightmost 0, then from that position to 5, then to 6 and finally you will go to 1. Total number of operations required are 4. But you can do it in simply 2 operations. Go from 0 to 1 and then go to rightmost 1 (target position).

Wrong dp algorithm
Some contestants have used wrong dp algorithm. Let dp[i] denote the minimum number of moves needed to reach position i from position 0. Some wre considering the transition from (i - 1) th position to i or from some position j < i (such that digit at j is same as digit at i.) to i.

Note that this kind of dp solutions are wrong because they don't consider the moves going backwards (from position i to i - 1), they are only considering the forward moves.

A simple test case where they will fail.
In the case: 02356401237894, dp program will give answer 6, but we can go from position 0 to 6 and then to 4 on the left side of second 0 (backward move) and then directly go to 4. So total number of operations required are 3.

Bfs Solution
Now consider the movement operations from one position to other to be edges of the graph and indices of the string as nodes of the graphs. Finding minimum number of operations to reach from 0 to N - 1 is equivalent to finding shortest path in the graph above mentioned. As the weights in the give graph are unit weights, we can use bfs instead of using dijkstra's algorithm.

So we can simply do a bfs from our start node(index 0) to end node(index n - 1). Number of nodes in the graph are n, but the number of edges could potentially go up to N 2 (Consider the case of all 0's, entire graph is a complete graph.).

Optimized bfs Solution
Now we will make use of the 2 observations that we have made in the starting and we will update the bfs solution accordingly.
Whenever you visit a vertex i such that then you should also visit all the the indices j such that s[j] = s[i] (this follows directly from observation 2). Now you can make sure to not to push any of the indices having digit same as current digit because according to observation 2, we are never going to make more than 2 moves from a position to another position with same digit, So after adding that the current character, you should make sure that you are never going to visit any vertex with same value as s[i].

For a reference implementation, see Vivek's solution.

Another Easy solution
Credit for the solution goes to Sergey Nagin(Sereja).

Let dp[i] denote the number of steps required to go from position 0 to position i.
From the previous observations, we know that we wont need more than 20 steps.
So lets make 20 iterations.

Before starting all the iterations, we will set dp[1] = 0 and dp[i] = infinity for all other i > 1.
On each iteration, we will calculate Q[k] where Q[k] is the minimum value of dp[i] such that s[i] = k. ie. Q[k] denotes the minimum value of dp over the positions where the digit is equal to k.

We can update the dp by following method.
dp[i] = min(dp[i], dp[i - 1] + 1, dp[i + 1] + 1, Q[s[i]] + 1);

Here the term dp[i - 1] + 1 denotes that we have come from previous position ie (i - 1).
Here the term dp[i + 1] + 1 denotes that we have come from next position ie (i + 1).
The term Q[s[i]] + 1 denotes the minimum number of operations needed to come from a position with same digit as the current i th digit.

Pseudo code:

// initialization phase.
dp[1] = 0;
for (int i = 2; i <= N; i++) dp[i] = inf;
for (int it = 0; it < 20; i++) {
    // Compute Q[k]
    for (int k = 0; k < 10; k++)
        Q[k] = inf;
    for (int i = 1; i <= n; i++) {
        Q[s[i] - '0'] = min(Q[s[i] - '0'], dp[i]); 
    }
    // Update the current iteration.
    for (int i = 1; i <= n; i++) {
        dp[i] = min(dp[i], dp[i - 1] + 1, dp[i + 1] + 1, Q[s[i] - '0'] + 1);
    }
}
// dp[n] will be our answer.

Proof
If you done proof of dijkstra's algorithm, you can simply found equivalence between the two proofs.

Complexity:
Complexity is O(20 * N). Here 20 is max number of iterations.

AUTHOR'S AND TESTER'S SOLUTIONS:

Tester's solution

This question is marked "community wiki".

asked 16 Jun '14, 15:01

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52127164
accept rate: 21%

edited 20 Oct '15, 22:12

admin123's gravatar image

5★admin123
1.2k11

5

Shouldn't the maximum number of moves be 19?

(16 Jun '14, 15:11) kcahdog3★

my solution is below can i know for which test case/cases it went wrong please....

https://ideone.com/iWZLna

(16 Jun '14, 15:45) manmauji2★
1

I'm unable to access Author's solution, It is saying access denied.

(16 Jun '14, 16:26) prithviraj73★

how could the value of i start from 0 during updating dp[i]?I think the value of i should start from 1 in sereja psudo code.

(16 Jun '14, 17:06) rishavz_sagar3★

Author's solution link is broken

(16 Jun '14, 17:18) nitesh783★
6

Nice problem and an amazing tutorial. Lately there's been a decline in the quality of editorials but this one was certainly one of the best.

(16 Jun '14, 17:24) thespacedude2★

For a reference implementation, see one of the solutions in the references. ???

Where are the references?? Or Can anyone point me the solution using bfs??

(16 Jun '14, 18:11) jony1★

beautiful solution, one of the best implementation of bfs

(16 Jun '14, 19:35) nitesh783★

@jony, I have updated the link. @rishavz_sagar, Yes, you are right, Updated.

(17 Jun '14, 18:48) dpraveen ♦♦4★

nice tutorial by dpraveen followed by crisp and self-explanatory implementation by vivek, makes it one of the bestest editorials.

(18 Jun '14, 15:30) hitesh0913★

Can someone explain me that in Sergey Nagin's solution why are we iterating the loop 20 times . for (int it = 0; it < 20; it++)

I can understand that in each loop dp[i] gets updated and after some iterations we will get correct result . but how 20?

(20 Jun '14, 22:48) baljitsingh3★

@dpraveen

I am trying to make it using BFS but I am not getting how the adjacency list of the graph will be generated.

(23 Jan '16, 09:17) arpit7282★
showing 5 of 12 show all

12

Who are getting WA can have the following cases :

94563214791026657896112 ans -> 4

12345178905 ans -> 3

112 ans -> 2

1112 ans -> 2

4589562452263697 ans -> 5

14511236478115 ans -> 2

0123456754360123457 ans -> 5

link

answered 16 Jun '14, 16:34

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61746
accept rate: 10%

1

Actually I don't understand last test case :( My code output for this one(0123456754360123457) is 7... Can anyone help me to understand this test case?

Thanks in advance :)

(16 Jun '14, 23:03) kimbbakar4★

can u explain the last one?how can it be 5??

(16 Jun '14, 23:52) alankar635★
1

for last case follow this path(indexes in bracket):
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) -> 7(18).

(17 Jun '14, 00:28) vaibhavatul473★

one more test case of later updating:- $72266886688661137700886699445511449955$ ans=6 ex 7-7-3-1-1-5-5

(20 Oct '15, 22:01) admin1235★
11

Well the test cases for this problem are still weak . Here is my accepted solution . My code fails on this 348117304825225015142699765169 . The expected output is 5 whereas my code gives 6 as the answer . I was almost half sure whether my solution would pass or not but luckily it passed . Its really difficult to make tricky test cases which can fail wrong solutions . I would request the setter to update the test cases for this problem in the practice section if possible .

link

answered 17 Jun '14, 02:19

aayushagarwal's gravatar image

2★aayushagarwal
2993510
accept rate: 0%

edited 17 Jun '14, 02:21

i think the expected output should also be 6 and not 5. correct me if i m wrong(plzz provide the steps).

(25 Jun '14, 09:58) prakhar04063★
1

indexes -> 0->6,6->5,5->24,24->23,23->29 i.e 3->3,3->7,7->7,7->9,9->9 These are the five steps.

(25 Jun '14, 18:36) obnoxious_soul4★

We can solve it using a Dijkstra too without relying on the fact that the solution would be bounded by 20. Instead of interconnecting all nodes with the same digit value resulting in potentially ~V^2 edges, we create one super node for each digit from 0 to 9, and connect each digit with its corresponding super node with an edge of weight 0.5. We can thus move to and from same digit nodes in distance 1, which was exactly what was required. This results in ~V edges and we can run Dijkstra on the first node in VlogV time. Finally we can double all edge lengths to avoid floating points and divide the required distance by 2 at the end.

link

answered 16 Jun '14, 17:11

sanchit_h's gravatar image

6★sanchit_h
22617
accept rate: 0%

My solution was accepted and uses dynamic programming. However because the solution is based on my intuition I'm not sure if understand whether or why it's 100% correct.

let dp[i] represent the minimum amount of steps in order to reach position i of the input array. We want to find dp[N-1].

let nums be an array of size 10 where nums[i] represents the minimum amount of moves that are needed in order to reach number i. Note that this number can exist anywhere in the array.

Now we have to scan the array from left to right and then from right to left as many times as needed in order to calculate the final value for dp[N-1]. We stop scanning the array when the values of dp aren't changed from a single scan (left->right, right->left).

Initialization

all values of dp and nums to INF

dp[0] = 0

nums[number of input[0]] = 0

First we scan it from left to right.

dp[i] = min(dp[i], dp[i-1]+1, nums[number of input[i]]+1)

then we scan the array from right to left:

dp[i] = min(dp[i], dp[i+1]+1, nums[number of input[i]]+1)

then again from left to right, right to left etc, until nothing changes in the array dp.

Basically I assume that the convergence to a solution is fast, however I have yet to think of a proof to this.

link

answered 16 Jun '14, 16:20

kmampent's gravatar image

3★kmampent
445177
accept rate: 16%

edited 17 Jun '14, 20:40

1

See "Another Easy Solution" section in the editorial.Your method is similar to what is described there.

(16 Jun '14, 17:36) plcpunk5★

thanks a lot, I missed that part!

(16 Jun '14, 17:47) kmampent3★
2

@picpunk : I used the same algorithm as yours but I scanned it only thrice i.e. first from left to right and then from reverse and again finally from front . I got AC with this approach and did not scan multiple times as you said . I would like to get a test case for which my solution will get fail because the test cases are still weak IMHO.

Here's the link to my solution : http://www.codechef.com/viewsolution/4100953

(16 Jun '14, 18:08) aayushagarwal2★

@aayushagarwal, my solution gets AC if we scan the array 3 times as well. I'm also not sure if this AC is due to weak test cases though.

(16 Jun '14, 18:11) kmampent3★

@kmampent : But in the editorial it is mentioned that at most we have to do 20 iterations because the maximum value can be 20 , perhaps there can be a test case which I am not able to deduce now .

(16 Jun '14, 18:42) aayushagarwal2★

indeed, it would be interesting to see if someone can find a test case where this method doesn't work.

(16 Jun '14, 19:11) kmampent3★

@aayushagarwal: your code gives incorrect output for 348117304825225015142699765169, expected output is 5 and your solution gives 6.

(17 Jun '14, 00:55) vaibhavatul473★

@vaibhavatul47 : Thank you for the test case !

(17 Jun '14, 02:15) aayushagarwal2★
showing 5 of 8 show all

If you are finding "Wrong Answer" then try following testcase :-

0998887776665554443322223300885577

Correct Ans --> 5

Directions : 0,0(last occurrence),8(next),8(index:5),7(next),7(last)

link

answered 16 Jun '14, 17:17

chanakya27's gravatar image

2★chanakya27
6112
accept rate: 0%

i have checked all the test cases given here for each one my code is giving correct output. can any one tell me for which test case it got failed.@admin...I think for this problem it will be helpful for many of us if test cases used for evaluation be made public.

https://ideone.com/iWZLna

thanks

link

answered 17 Jun '14, 11:00

manmauji's gravatar image

2★manmauji
462
accept rate: 0%

Can you explain what is wrong with my dp solution. It gave right answer for your test case. I have implemented the dp such that it considers going backwards.

include <iostream>

include <string>

include <cstring>

include <climits>

include <algorithm>

using namespace std;

int main() { int dp[100005]; string s; cin>>s; int len = s.size(); //cout<<s.size()<<endl; int mini[10]; memset(mini,-1,sizeof(mini)); for(int i=0;i<len;i++) dp[i] = 100005;

dp[0] = 0;
mini[s[0]-'0']=0;
int curMin,j;
for(int i=1;i<len;i++)
{
    if(mini[s[i]-'0']==-1)
        mini[s[i]-'0']=i;

    curMin = dp[mini[s[i]-'0']];
    dp[i] = min(dp[i-1]+1, curMin+1);
    if(dp[i] < dp[mini[s[i]-'0']])
        mini[s[i]-'0'] = i;

    j=i;
    while((dp[j-1] > (dp[j]+1))&&(j!=(len-1)))
    {
        dp[j-1] = dp[j]+1;
        if(dp[j-1] < dp[mini[s[j-1]-'0']])
            mini[s[j-1]-'0'] = (j-1);
        j--;
    }
}
/*
cout<<endl;

cout<<mini[3]<<endl;*/
/*for(int i=0;i<len;i++)
    cout<<dp[i];
cout<<endl;*/
cout<<dp[len-1];
return 0;

}

Please it will be great if someone can explain to me my mistake here. My approach is similar to Sergey's approach. My mini array does the same thing that the Q array does in his code

link

answered 16 Jun '14, 15:44

unrealsoul007's gravatar image

5★unrealsoul007
513
accept rate: 0%

edited 16 Jun '14, 15:47

1

7711965557423006 ur o/p: 6, correct o/p: 5

(16 Jun '14, 17:12) vaibhavatul473★

@vaibhavatul47 Why is ans 5..?? 7 to 7(last 7) - 1 7 to 5(left) - 2 5 to 5(left) - 3 5 to 5(left) - 4 5 to 6(left) - 5 6 to 6(last) - 6

It cannot make a jump from '5' at index 8 to '5' at index 6 in 1 step because the problem states only (i-1) backwards. Can you please explain..??

(19 Jun '14, 16:18) unrealsoul0075★

...But we can move to the same digit anywhere in the list. That is the main thing in this problem!

(27 Jun '14, 21:37) yash_155★

Hi All

I used the BFS and dijsktra approach to solve the problem . It is working fine for all cases mentined above .Please have a look at it and would be grateful to let me know whch testcases it failed . Thanks :)

http://www.codechef.com/viewsolution/4092676

link

answered 16 Jun '14, 16:24

anisdube's gravatar image

2★anisdube
161
accept rate: 0%

hi all my code seems to be working for all the below test cases , 94563214791026657896112 ans -> 4 12345178905 ans -> 3 112 ans -> 2 1112 ans -> 2 4589562452263697 ans -> 5 14511236478115 ans -> 2 0123456754360123457 ans -> 5

still it showed WA . any help is appreciated

(17 Jun '14, 01:18) anisdube2★

hey for "348117304825225015142699765169 . The expected output is 5" i am getting 5 also for this . totally not sure why it is still saying WA

(17 Jun '14, 13:10) anisdube2★

@shiplu can you please check y my code is giving WA . thanks

(18 Jun '14, 23:35) anisdube2★

@Praveen Dhinwa , can you please have a look at my code , looks like it is working for eacha nd every tes cases .

(30 Jun '14, 14:34) anisdube2★

@anisdube, your method of taking input is problematic.

(04 Jul '14, 02:11) shiplu3★

Can someone point out the bug in my Greedy problem as well, it gives me WA. Thanks in advance :)

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;
struct intint
{
    int number;
    int start;
    int end;
    int jump;
};

bool compareJumps(intint a,intint b) { return (a.jump > b.jump); }

bool isCompatible(vector<intint> baseVector, intint toCheck)
{
    for(int i=0;i<baseVector.size();i++)
    {
        if((toCheck.start < baseVector[i].start) && (toCheck.end < baseVector[i].start))
        {}
        else if((toCheck.start > baseVector[i].end) && (toCheck.end > baseVector[i].end))
        {}
        else
        {
            return false;
        }
    }
    return true;
}

int main()
{
    string S;
    cin>>S;
    vector<intint> max;
    for(int i=0;i<10;i++)
    {
        intint temp;
        temp.number = i;
        temp.jump = -1;
        temp.start = -1;
        temp.end = -1;
        max.push_back(temp);
    }
    for(int i=0;i<S.length();i++)
    {
        int number = S[i] - 48;
        if(max[number].start == -1)
        {
            max[number].start = i;
            //max[number].jump = 0;
        }
        else
        {
            max[number].end = i;
            max[number].jump = i - max[number].start;
        }
    }
    sort(max.begin(),max.end(),compareJumps);
    vector<intint> jumpsTaken;
    for(int i=0;i<max.size();i++)
    {
        if((max[i].jump > 0)&&(isCompatible(jumpsTaken,max[i])))
        {
            jumpsTaken.push_back(max[i]);
        }
    }
    int path = S.length() - 1;
    for(int i=0;i<jumpsTaken.size();i++)
    {
        path = path - jumpsTaken[i].jump + 1;
    }
    cout<<path;
    return 0;
}
link

answered 16 Jun '14, 15:46

rmagon's gravatar image

2★rmagon
1
accept rate: 0%

edited 16 Jun '14, 16:16

found why is the answer wrong For anyone else who is wondering: The I/p 248612676 answer should be 3

(16 Jun '14, 16:30) rmagon2★

Great Observations. Used BFS for this question. i wish, if i had thought of this bfs optimisation before. great question

link

answered 16 Jun '14, 15:46

brobear1995's gravatar image

2★brobear1995
1561511
accept rate: 0%

I used O(2^8*8!), cause was not able to come up with easier approach. omg ))

link

answered 16 Jun '14, 16:07

anton_postnikov's gravatar image

3★anton_postnikov
7611
accept rate: 0%

Can anyone tell me what is wring with this code, it gives wrong answer on submission, but is working fine on my system for every possible input i can think of. I am not able to find the type of input for which it can give a wrong answer.

http://www.codechef.com/viewsolution/4105903

link

answered 16 Jun '14, 16:33

shubhi1910's gravatar image

1★shubhi1910
1
accept rate: 0%

Author's solution link is broken. http://www.codechef.com/download/Solutions/2014/June/Setter/DIGJUMP.cpp Please fix the link.

link

answered 16 Jun '14, 17:02

abhiabhishek's gravatar image

3★abhiabhishek
11
accept rate: 0%

I tried the DP thing, iterating over it and making it better, made a lot of submissions in the process. Here is my last one I tried:

from __future__ import division
def read_mapped(func=lambda x:x):
    return map(func, raw_input().strip().split(" "))
def read_int():
    return int(raw_input().strip())
def read_str():
    return raw_input().strip()
def read_float():
    return float(raw_input().strip())

s = map(int, list(read_str()))
lim = len(s)-1
dp = [-1 for _ in xrange(lim+1)]
dp[0] = 0

from collections import defaultdict
dpa = [10**10 for i in xrange(11)]
dpa[s[0]] = 0

for i in xrange(1, lim+1):
    minn = dpa[s[i]]
    dp[i] = min(minn, dp[i-1])+1
    dpa[s[i]] = min(dpa[s[i]]+1, dp[i])

for _ in xrange(19):
    dpa = [10**10 for i in xrange(11)]
    dpa[s[0]] = 0
    for i in xrange(1, lim+1):
        minn = dpa[s[i]]
        dp[i] = min(minn, dp[i-1], dp[i+1] if i!=lim else 10**10)+1
        dpa[s[i]] = min(dpa[s[i]]+1, dp[i])

print dp[-1]

But it gives me a WA. Why is it so?

Edit

I tried chanakya's input and it gives me 8 as answer instead of 3. I can't figure out why. :/

Input: 0998887776665554443322223300885577

Output: 8

link

answered 16 Jun '14, 21:25

svineet's gravatar image

3★svineet
26249
accept rate: 0%

edited 16 Jun '14, 21:26

Can anyone tell me what i am commiting mistake in my code......

include<bits stdc++.h="">

using namespace std; string str; int a[10][10],flag[10];

void distance_matrix() { int i,j; for(i=0;i<str.size();i++) { if(i==0) { a[str[i]-'0'][str[i+1]-'0']=1; a[str[i]-'0'][str[i]-'0']=0; flag[str[i]-'0']=1; } else if(i==str.size()-1) { if(flag[str[i]-'0']==1) { a[str[i]-'0'][str[i]-'0']=1; a[str[i]-'0'][str[i-1]-'0']=min(2,a[str[i]-'0'][str[i-1]-'0']); } else { a[str[i]-'0'][str[i]-'0']=0; a[str[i]-'0'][str[i-1]-'0']=1; flag[str[i]-'0']=1; } } else { if(flag[str[i]-'0']==1) { a[str[i]-'0'][str[i]-'0']=1; a[str[i]-'0'][str[i+1]-'0']=min(2,a[str[i]-'0'][str[i+1]-'0']); a[str[i]-'0'][str[i-1]-'0']=min(2,a[str[i]-'0'][str[i-1]-'0']); } else { a[str[i]-'0'][str[i]-'0']=0; a[str[i]-'0'][str[i+1]-'0']=1; a[str[i]-'0'][str[i-1]-'0']=1; flag[str[i]-'0']=1; } } } /for(i=0;i<10;i++) { for(j=0;j<10;j++) cout<<a[i][j]<<" "; cout<<endl; }/ }

int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,i,j,k;
for(i=0;i<10;i++) { for(j=0;j<10;j++) a[i][j]=INT_MAX/2; flag[i]=0; } cin>>str; if(str.size()==1) { cout<<"0"<<endl; return 0; } distance_matrix(); int visit[10],distance[10]; for(i=0;i<10;i++) { visit[i]=0; distance[i]=INT_MAX/2; } visit[str[0]-'0']=1; for(i=0;i<10;i++) { distance[i]=a[str[0]-'0'][i]; } distance[str[0]-'0']=0; /for(i=0;i<10;i++) { cout<<visit[i]<<" "; }cout<<endl; for(i=0;i<10;i++) { cout<<distance[i]<<" "; } for(i=0;i<10;i++) { for(j=0;j<10;j++) cout<<a[i][j]<<" "; cout<<endl; }/ for(i=0;i<10;i++) { int min_dis=INT_MAX/2,index; for(j=0;j<10;j++) { if(visit[j]==0&&distance[j]<=min_dis) { min_dis=distance[j]; index=j; } } visit[index]=1; for(j=0;j<10;j++) { if(visit[j]==0) { distance[j]=min(distance[j],min_dis+a[index][j]); } } } /for(i=0;i<10;i++) { cout<<visit[i]<<" "; }cout<<endl; for(i=0;i<10;i++) { cout<<distance[i]+a[i][i]<<" "; }/ cout<<distance[str[str.size()-1]-'0']+a[str[str.size()-1]-'0'][str[str.size()-1]-'0']<<endl; return 0; }

link

answered 16 Jun '14, 21:32

nadeem13ahamed's gravatar image

4★nadeem13ahamed
1
accept rate: 0%

http://www.codechef.com/viewsolution/4050931

Can someone check my this code. it is showing run time error. but in my compiler it is providing me with all correct answers. help would be appreciated.

link

answered 17 Jun '14, 14:30

tusharsre's gravatar image

3★tusharsre
11
accept rate: 0%

I am not able to understand under the heading "Another Easy Solution" DP. Pseudo Code is not working for me but using the idea I solved the problem. So i change the code for moving from position 0 to n-1 .(rather than from 1 to n).

dp[0]=0 ; dp[1 ]=1;

Answer is given by dp[n-1]

My Solution link is http://www.codechef.com/viewsolution/4110410

link

answered 17 Jun '14, 22:43

pandeytejas's gravatar image

2★pandeytejas
11
accept rate: 0%

edited 17 Jun '14, 22:45

see the updated pseudo code. also see my accepted submission http://www.codechef.com/viewplaintext/4111204

(18 Jun '14, 04:35) dpraveen ♦♦4★

I've used a solution similar to the one by Sergey Nagin. I have, however, used 10 iterations instead of 20. I got AC which could be due to weak test cases.

Can someone please give a test case that shows the possible mistake in my code? Or is it actually possible to do it in 10 and not 20 iterations?

The following arrays in my code have the following meaning as in the pseudo code by Sergin. val[i] - dp[i] (stores minimum no of moves to reach this point) minval[i] - Q[i] (stores minimum no of moves to reach the number i)

include<stdio.h>

include<string.h>

int main() {

int i,n;    
char str[100000];
int minval[10],val[100001];
scanf("%s",str);
n = strlen(str);

val[0]=0;
val[n]=20000;
for(i=0;i<n;i++) str[i]=str[i]-48;
for(i=0;i<10;i++) minval[i]=20;
minval[str[0]]=0;

for(i=0;i<n;i++)
{
    if(i!=0)
    {
        if(val[i-1]<=minval[str[i]])
        {
            val[i]=val[i-1]+1;
        }
    else
    {
        val[i]=minval[str[i]]+1;
    }

    if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
}

if(minval[str[i]]>val[i]) minval[str[i]]=val[i];


}
int j;
for(j=0;j<10;j++)
{


    for(i=0;i<n;i++)
    {
        if( i!=0)
        {
            if(val[i-1]<minval[str[i]]&&val[i-1]<val[i+1])
            {
                val[i]=val[i-1]+1;
            }
            else if(val[i+1]<minval[str[i]]&&val[i+1]<val[i-1])
            {
                val[i]=val[i+1]+1;
            }
            else
            {
                val[i]=minval[str[i]]+1;
            }
            if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
        }
        if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
    }
}
printf("%d\n",val[n-1]);

}

link

answered 18 Jun '14, 22:11

hariharans's gravatar image

3★hariharans
1
accept rate: 0%

i think the expected answer should also be 6 not 5. correct me if i m wrong(plzz write the steps)

link

answered 25 Jun '14, 09:53

prakhar0406's gravatar image

3★prakhar0406
11
accept rate: 0%

For people whose program is passing all the test cases given by the question as well as other users

Check whether ur program works for inputs such as

00112233445566778899 - 19

445566 - 5

001122 - 5

22445599 - 7

I had the same issue and my program was accepted once i rectified this.

link

answered 26 Jun '14, 11:55

abhi011's gravatar image

3★abhi011
0113
accept rate: 0%

edited 26 Jun '14, 11:56

My code passes all the test cases provided above in the comments but I still get WA when submitting :/ Any help ? Here's my code : http://www.codechef.com/viewsolution/4097046

link

answered 04 Jul '14, 00:03

the_aviator's gravatar image

2★the_aviator
26114
accept rate: 0%

I'm getting tle. :( Can plz anyone help me ..?

include<iostream>

include<cstring>

include<queue>

using namespace std;

define MAX 1000000

define for(i,n) for( i=0;i<n;i++)

vector< int > v[10];

define initial 1

define waiting 2

define visited 3

define NIL -1

queue <int> buff;

int main() {

char s[MAX];

cin>>s;

int n,i,val;

n=strlen(s);

for(i,n)

{  val=s[i]-48;

 v[val].push_back(i);
   }

int state[n];

int pre[n];

for(i,n) { state[i]=initial; pre[i]=-1; } int pt,st;

buff.push(0);

vector< int > :: iterator p;

while(!buff.empty())
{ pt=buff.front(); if(pt==n-1) break;

                st=s[pt]-48;

                state[buff.front()]=waiting;
                  //cout<<v[pt].front()<<v[pt].size()<<endl;


                p=v[st].begin();


                while(p!=v[st].end())
                {

                if(state[*p]==initial)                     
               { state[*p]=waiting;
                pre[*p]=pt;

                buff.push(*p);}

                p++;
                }



               if(  (pt+1< n)&& (state[pt+1]==initial))
              { state[buff.front()+1]=waiting;
               pre[buff.front()+1]=pt;
               buff.push(buff.front()+1);}


                if((0<  pt-1 )&& (state[pt-1]==initial) )
              { state[buff.front()-1]=waiting;
               pre[buff.front()-1]=pt;
               buff.push(pt-1);}


               state[pt]=visited;
                buff.pop();






                }

int sd=0; int v=n-1; while(v!=0) { v=pre[v]; sd++;

       }

cout<<sd;

return 0; }

link

answered 18 Sep '14, 22:36

vishalgupta94's gravatar image

1★vishalgupta94
11
accept rate: 0%

I have applied the same logic as given in the Optimized BFS solution and I have tested my program for all the test cases, including the ones given in the comments above. Still it gives wrong answer.

here is the link to my solution: http://www.codechef.com/viewsolution/5358955

Plz help.

link

answered 12 Nov '14, 20:50

amita0906's gravatar image

1★amita0906
11
accept rate: 0%

edited 12 Nov '14, 20:52

Can anyone explain me how to solve this problem using BFS? I am not able to understand how to use BFS on this problem.

link

answered 05 Apr '15, 10:25

codehacker02's gravatar image

2★codehacker02
1
accept rate: 0%

can someone explain me the implementation of optimization part of Vivek's solution ???

link

answered 04 May '15, 11:43

akhileshydv20's gravatar image

3★akhileshydv20
173
accept rate: 0%

Well, my line of reasoning for "Another easy solution" was different. Think in terms of forward jump and backward jump. If there is only forward jumps , then

for(i=1;i<len;++i) { dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1);//min[] equivalent to Q[] in editorial min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]); }

is enough to find dp[n-1].
If there is only one backward jump in the final answer , then we need to run the above code , one more time now considering , dp[i+1]+1 also, i.e.

for(i=1;i<len;++i) { if(i==len-1) dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1); else dp[i] = Min(Min(dp[i-1]+1, dp[i+1]+1) ,min[str[i]-'0']+1); min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]);

}

If there are 'b' backward jumps in total , then we need to run the above code 'b' times. So max is the maximum backward jumps that we can make ?
We know that any minimum moves will not exceed 20. So , that is the bound on backward jumps also. So ,

dp[0]=0; min[str[0]-'0']=0; for(j=1;j<=20;++j) { for(i=1;i<len;++i) { if(i==len-1) dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1); else dp[i] = Min(Min(dp[i-1]+1, dp[i+1]+1) ,min[str[i]-'0']+1); min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]); }

}

link

answered 23 Jun '15, 18:28

empty_life's gravatar image

2★empty_life
355819
accept rate: 20%

edited 23 Jun '15, 18:31

can anyone please tell me why my answer is a tle https://www.codechef.com/viewsolution/9705925

link

answered 20 Mar '16, 17:53

bhawin91's gravatar image

1★bhawin91
1
accept rate: 0%

I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.

link

answered 24 May '16, 19:23

hulk_baba's gravatar image

4★hulk_baba
938
accept rate: 0%

I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.

link

answered 24 May '16, 19:24

hulk_baba's gravatar image

4★hulk_baba
938
accept rate: 0%

I tried again but still getting TLE. Someone pls help solution lnk https://www.codechef.com/viewsolution/10159123

(26 May '16, 04:31) hulk_baba4★

Hi !! My code is showing correct output on all the cases mentioned at any point above.

Here it is :- https://hastebin.com/uhiwezozat.py

Unfortunately, it is showing Wrong Answer. Can anyone please help me with a Test Case or suggestions ?

Thanks.

link

answered 03 Sep, 19:48

naman_bhalla's gravatar image

2★naman_bhalla
1
accept rate: 0%

    #include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
vector<vector<int> > similar(10, vector<int>(0));
typedef pair<int, int> ii;

int main() {

    string s,temp;
    cin >> s;
    int n = s.length();
    bool vist[10] = {0};
    for(int i = 0; i < n; ++i){
        similar[s[i]-'0'].push_back(i);
    }
    int dist[n];
    for(int i = 0; i < n;++i) {
        dist[i] = 100000000;
    }
    dist[0] = 0;
    priority_queue<ii> pq; 
    pq.push(ii(0, 0));
    while(!pq.empty()) {
        int node = pq.top().second;
        int d = -1*pq.top().first;
        pq.pop();
        if(node == n -1) break;




        if(node < n-1){
            if(dist[node+1] > d + 1) {
                pq.push(ii(-1*(d + 1), (node+1)));
                dist[node+1] = d + 1;
            }
        }
        if(node > 0) {
            if(dist[node - 1] > d + 1 ) {
                pq.push(ii(-1*(d + 1), (node-1)) );
                dist[node-1] = d + 1;
            }
        }
        int no = s[node] - '0';

        for(int i = 0;  i < similar[no].size() and !vist[no]; ++i) {
            int curnode = similar[no][i];
            if(curnode > node) {
                if(dist[curnode] > d + 1) {
                    dist[curnode] = d + 1;
                    pq.push(ii(-1*(d+1), curnode));
                }
            }
        }
        vist[no] = true;
    }
    cout << dist[n-1];

}

can someone plz tell me where i am wrong, i have implemented this question using the flavor of Dijikstra.....please help

link

answered 01 Oct, 18:45

vipin_bhardwaj's gravatar image

4★vipin_bhardwaj
1267
accept rate: 8%

-1

what is wrong with my this DP solution its giving correct answer for 02356401237894 (3)

include<stdio.h>

define min(a,b) a<b?a:b

define int_max 1000000

int main() { int jump[100005];

char num[100005];

scanf("%s",num);

int i;

jump[0] = 0;

for(i=0;i<100004;i++)
    jump[i] = 1000000;
jump[0] = 0;
for(i=1;num[i] != '\0';i++)
{
    int j = 0;
    //   jump[i] = 1000000;
    while(j<i)
    {   
        if( ( i == j+1 || num[i] == num[j]  ))
        {
            if(jump[i] > jump[j] + 1)
                jump[i] = jump[j] + 1;

            break;                
        }


        j = j+1;
    }
    if( jump[i-1]  > jump[i] + 1)
        jump[i-1] = jump[i] + 1;
    if(jump[i+1] != '\0' && jump[i+1] > jump[i] + 1)
        jump[i+1] = jump[i] + 1;
    //     printf("%d",j);
}
printf("%d\n",jump[i-1]);
return 0;

}

link

answered 16 Jun '14, 15:33

rd13123013's gravatar image

5★rd13123013
0
accept rate: 0%

can you check your output on this input 023564101237894 ??? Correct answer is 4.

(16 Jun '14, 15:43) code_crack_014★

check your output for: 248612676 Ans should be 3.

(16 Jun '14, 15:51) vaibhavatul473★
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:

×12,235
×2,686
×357
×138
×43
×41

question asked: 16 Jun '14, 15:01

question was seen: 17,077 times

last updated: 01 Oct, 18:45