Can anyone help me to find the test case for which i am getting wrong answer for qualification round 1 of google codejam 2021.(Moon and umbrellas)
Here is my code.
;;;codejam question 2
;;;codejam question 2
(defun subseq-safe (str &optional (start 0) (end nil))
(subseq str start (if (<= end (length str)) end (length str))))
(defun find-cost (cj jc str)
(labels ((f-cost (cost s)
(cond ((< (length s) 2) cost)
((equal “JC” (subseq-safe s 0 2)) (f-cost (+ cost jc) (subseq s 1)))
((equal “CJ” (subseq-safe s 0 2)) (f-cost (+ cost cj) (subseq s 1)))
(t (f-cost cost (subseq s 1))))))
(f-cost 0 str)))
(defun minimize-cost-str (str)
(do ((i 0 (incf i))
(j 0)
(rchar #\J))
((equal i (length str))
(if (equal (char str (- i 1)) #?) (nsubstitute (char str j) #? str :start j :end i)) str)
(when (or (and (> (- i j) 1) (not (equal (char str i) #?)))
(and (equal j 0) (not (equal (char str i) #?))))
(cond ((equal (char str j) #?)
(setf rchar (char str i)))
((and (equal (char str j) #\J) (equal (char str i) #\C))
(setf rchar #\J))
((and (equal (char str j) #\C) (equal (char str i) #\J))
(setf rchar #\J))
((and (equal (char str j) #\C) (equal (char str i) #\C))
(setf rchar #\C))
((and (equal (char str j) #\J) (equal (char str i) #\c))
(setf rchar #\J)))
(nsubstitute rchar #? str :start j :end (+ i 1))
(setf j i))))
(defun process-test-case (n)
(labels ((p-test-case (i)
(when (<= i n)
(let ((cj (read))
(jc (read))
(str (string (read))))
(format t “~&Case ~a: ~a” i (find-cost cj jc (minimize-cost-str str)))
(p-test-case (+ i 1))))))
(p-test-case 1)))
(process-test-case (read))
This will run in lisp sbcl.
According to CodeJam Rules, we can discuss in the Qualifier Round.
I already told discussion is allowed. Now can this be reopened again.
vai53
5
I doubt if anyone else here will know this language
You can run this on codechef ide for lisp sbcl. If you wish i may write it in cpp. The test case format is in link
You should try an approach of neglecting initial and terminal question marks and get answer for the remaining string.
I can give you some hint (Coz I solved for first two subtasks).
A contiguous segment of '?' shall be replaced with a single character - either C or J.
only if x and y have same signs
Not very carefully Implemented, but here you go:’
// Code Created BY LEO_VALDEZ
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x).size()
#define sarr(x) (int)(sizeof(x)/sizeof(x[0]))
#define mp make_pair
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
signed main()
{
int t;
cin >> t;
for(int cas = 1; cas <= t; cas++)
{
int x, y;
cin >> x >> y;
string fake;
cin >> fake;
int n = fake.length();
char s[n];
for(int i = 0; i < n; i++)
s[i] = fake[i];
int dp[4][n];//0--> CC, 1--> JJ, 2--> CJ, 3--> JC
dp[0][0] = 0;
dp[1][0] = 0;
dp[2][0] = x;
dp[3][0] = y;
for(int i = 1; i < n; i++)
{
dp[0][i] = min(dp[0][i-1], y + dp[2][i-1]);
dp[1][i] = min(dp[1][i-1], x + dp[3][i-1]);
dp[2][i] = min(dp[2][i-1], x + dp[0][i-1]);
dp[3][i] = min(dp[3][i-1], y + dp[1][i-1]);
}
int h1 = 0, h2 = 0;
while(s[h1] == '?')
h1++;
while(s[n-1-h2] == '?')
h2++;
int a = 0;
int b = 0;
int cost;
int c = 0;
if(h1 == n)
{
if(n==1)
cost = 0;
else
cost = min(min(dp[0][n-2], dp[1][n-2]), min(dp[2][n-2], dp[3][n-2]));
cout << "Case #" << cas << ": " << cost << endl;
continue;
}
if(h1 && s[h1] == 'C')
a = min(dp[0][h1-1], dp[3][h1-1]);
else if(h1 && s[h1] == 'J')
a = min(dp[1][h1-1], dp[2][h1-1]);
if(h2 && s[n-1-h2] == 'C')
b = min(dp[0][h2-1], dp[2][h2-1]);
else if(h2 && s[n-1-h2] == 'J')
b = min(dp[1][h2-1], dp[3][h2-1]);
int curr = 0;
int start = -1;
for(int i = h1; i < n-h2; i++)
{
if(s[i] == '?')
curr++;
else
{
if(start == -1){
start = i;
continue;
}
else
{
}
if(s[i] == 'C')
{
if(s[start] == 'C')
c+=dp[0][i-start-1];
else
c+=dp[3][i-start-1];
}
else
{
if(s[start] == 'C')
c+=dp[2][i-start-1];
else
c+=dp[1][i-start-1];
}
start = i;
curr = 0;
}
}
cout << "Case #" << cas << ": " << a+b+c << endl;
}
return 0;
}
1 Like