HackerEarth Gudi trapped in the Room problem solution

In this HackerEarth Gudi trapped in the Room problem solution Gudi enters the castle, and moves along the main path. Suddenly, a block in the ground opens and she falls into it! Gudi slides down and lands in a dark room. A mysterious voice announces:

Intruders are not allowed inside the castle. To proceed, you must solve my puzzle. Here is a string S indexed from 1 to N, consisting of digits from 0-9. If you summon the spell “Sera”, the string will be rotated clockwise by H positions. If you summon the spell “Xhaka”, the number A will be added to all the even-indexed digits of the string.

For example, if H = 1 A = 3 “Sera” and “Xhaka” on the string “781” will result in strings “”178” and “711” respectively i.e. digits post 9 are cycled back to 0. The objective is to obtain the lexicographically smallest string possible as a result of applying any of the two spells any number of times in any order. Find the string and I shall set you free

HackerEarth Gudi trapped in the Room problem solution.

#include<bits/stdc++.h>


using namespace std;

#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define pb push_back

set<string>mp;
int add,shift;
void dfs( string tmp)
{
  //cout<<tmp<<endl;
  mp.insert(tmp);
  string next=tmp;
  int i,n=tmp.size();
  for(i=0;i<n;i++)
  {
    next[(i+shift)%n]=tmp[i];
  }
  if(mp.find(next)==mp.end())
    dfs(next);
  next=tmp;
  for(i=0;i<n;i++)
  {
    if(i%2)
    next[i]= '0'+ (next[i]-'0'+add)%10;
  }
  if(mp.find(next)==mp.end())
    dfs(next);
  return;
}
int main()
{
  // freopen("in.txt","r",stdin);
  // freopen("out","w",stdout);
  ios_base::sync_with_stdio(0);
  int t;
  cin>>t;
  assert(1<=t && t<=10);
  while(t--)
  {
    string inp;
    cin>>inp>>add>>shift;
    mp.clear();
    dfs(inp);
    cout<<*(mp.begin());
    if(t>0)
      cout<<endl;
  }
 return 0;
}

Second solution

import sys
t = int(sys.stdin.readline())
stack = [[] for i in range(1000010)]
for __ in range(t):
  s = map(lambda x: ord(x)-ord('0'), sys.stdin.readline().rstrip())
  a,h = map(int, sys.stdin.readline().split())
  h %= len(s)
  ans = "".join(map(str,s))
  vis = set()
  sidx = 0
  
  def push(val):
    global ans,sidx
    hs = "".join(map(str,val))
    if hs in vis: return
    ans = min(ans, hs)
    vis.add(hs)
    stack[sidx] = val
    sidx += 1
  
  push(s)
  while sidx > 0:
    cur = stack[sidx-1]
    sidx -= 1
    push(cur[h:]+cur[:h])
    for i in range(1,len(cur),2):
      cur[i] = (cur[i]+a)%10
    push(cur)

  print ans

HackerEarth Gudi trapped in the Room problem solution

HackerEarth Gudi trapped in the Room problem solution.

Second solution

Leave a Reply

Pages

Practice