[gcj] Re: What's my mistake? - [Round 1B - 2020 : Expogo]

[Matt Fenlon]

Some of the hardcoded conditions/appends are out of whack. For example, 
X1==4 and Y1==1 should be SNE, not NSE. Also, down below these conditions, 
when X<0, we need to change E and W, not N and S. The opposite is true for 
when Y<0. When all these get corrected, the code passes Test Set 1. For 
Test Set 2, I imagine there is something up with the logic in the loop when 
X>4 and Y>4. I leave it to you to check out the Analysis and work it out: 
https://codingcompetitions.withgoogle.com/codejam/round/0019fef2/002d5b62

Best,
Matt

On Monday, April 20, 2020 at 12:38:32 PM UTC-4, Rohan Shukla wrote:
>
> Just attempted the GCJ 2020 : Round 1B. I was able to solve Blindfolded 
> Bullseye but my code for Expogo gave wrong answer. Would have got a good 
> score if I could have cracked this as well. 
> Here's my python3 code.
>
> T = int(input())
> t = 1 
> while(t <= T):
> res = ""
> Y = input().split(" ")
> X = int(Y[0])
> Y = int(Y[1])
> X1 = abs(X)
> Y1 = abs(Y)
> while(X1 > 4 or Y1 > 4):
> if((X1+Y1)%2 == 0):
> res = "IMPOSSIBLE"
> break
> else:
> if(X1 % 2 != 0):
> c1 = (X1+1)//2 + (Y1)//2
> c2 = (X1-1)//2 + (Y1)//2
> if(c1 % 2 == 0):
> res += "E"
> X1 = (X1-1)//2
> else:
> res += "W"
> X1 = (X1+1)//2
> Y1 //= 2
> elif(Y1 % 2 != 0):
> c1 = (Y1+1)//2 + (X1)//2
> c2 = (Y1-1)//2 + (X1)//2
> if(c1 % 2 == 0):
> res += "S"
> Y1 = (Y1-1)//2
> else:
> res += "N"
> Y1 = (Y1+1)//2
> X1 //= 2
> else: 
> break
> if(X1 == 0 and Y1 == 1):
> res += "S"
> elif(X1 == 1 and Y1 == 0):
> res += "E"
> elif(X1 == 0 and Y1 == 3):
> res += "SS"
> elif(X1 == 3 and Y1 == 0):
> res += "EE"
> elif(X1 == 1 and Y1 == 2):
> res += "ES"
> elif(X1 == 2 and Y1 == 1):
> res += "SE"
> elif(X1 == 2 and Y1 == 3):
> res += "SEN"
> elif(X1 == 3 and Y1 == 2):
> res += "ESW"
> elif(X1 == 1 and Y1 == 4):
> res += "WES"
> elif(X1 == 4 and Y1 == 1):
> res += "NSE"
> elif(X1 == 3 and Y1 == 4):
> res += "EES"
> elif(X1 == 4 and Y1 == 3):
> res += "SSE"
> else: 
> res = "IMPOSSIBLE"
> if(res != "IMPOSSIBLE"):
> l = list(res)
> if(X < 0):
> for i in range(len(l)):
> if(l[i] == "S"):
> l[i] = 'N'
> elif(l[i] == 'N'):
> l[i] = 'S'
> if(Y < 0):
> for i in range(len(l)):
> if(l[i] == "E"):
> l[i] = 'W'
> elif(l[i] == 'W'):
> l[i] = 'E'
> res = ''.join([str(elem) for elem in l])
> print("Case #{}: {}".format(t,res))
> t += 1
>
> Would be great if someone could point out my mistake. 
>
> Thanks in advance!
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3410979b-cf65-4f65-8845-579c813d0604%40googlegroups.com.

[gcj] Re: [2020][PYTHON3][Expogo] RE on judge

[Matt Fenlon]

When I run it locally, I get 

{SyntaxError: unexpected EOF while parsing}

Maybe it has something to do with how you are handling the input?

Best,
Matt

On Monday, April 20, 2020 at 12:38:27 PM UTC-4, Nabil Marquez wrote:
>
> Hello, the following code always gives me RE on the judge (during the 
> first test set):
>
> from math import sqrt, ceil, log
>
> possible = [(0,1),(1,0),(0,-1),(-1,0)]
>
> reflected = {
> "E" : "W",
> "W" : "E",
> "S" : "N",
> "N" : "S",
> }
>
> def evenReachable(Xi, Yi, Xf, Yf):
> if ((Xi + Yi) == 0) or ((Xf + Yf) == 0):
> return True
> else:
> return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)
>
> def distance(Xi, Yi, Xf, Yf):
> return sqrt((Xf-Xi)**2+(Yf-Yi)**2)
>
> def getCase(Xi, Yi, Xn, Yn):
> if Xn > Xi:
> return 'E'
> if Xn < Xi:
> return 'W'
> if Yn > Yi:
> return 'N'
> if Yn < Yi:
> return 'S'
>
> def reflect(solution):
> return ''.join([reflected[c] for c in solution])
>
> def recursiveJumps(lowestJumps, maxJ, Xf, Yf, Xi, Yi, totalD, jumpN, 
> oldResult = ""):
> requiredD = distance(Xi, Yi, Xf, Yf) + totalD
> result = oldResult
>
> if (jumpN > maxJ) or (jumpN > lowestJumps) or not evenReachable(Xf, Yf
> , Xi, Yi):
> return ("IMPOSSIBLE", float("inf"))
>
> if (Xf == Xi and Yf == Yi):
> # print("goal!")
> return (result, totalD)
>
> bestResult = None
>
> for i,j in possible:
> Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
> Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
> newD = distance(Xi,Yi, Xn, Yn) + totalD
>
> if (newD <= requiredD):
> newResult = result + getCase(Xi, Yi, Xn, Yn)
> (newResult, newD) = recursiveJumps(lowestJumps, maxJ, Xf, Yf, 
> Xn, Yn, newD, jumpN+1, newResult)
>
> if (newD >= requiredD) and newResult != "IMPOSSIBLE" :
> bestResult = (newResult, newD)
> lowestJumps = jumpN + 1
>
> return bestResult if bestResult is not None else ("IMPOSSIBLE", float(
> "inf"))
>
> def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN, solutions):
> key = "{}_{}".format(Xf, Yf)
> keyR = "{}_{}".format(-Xf, -Yf)
>
> if key in solutions:
> return solutions.get(key)
> elif keyR in solutions:
> solutions[key] = reflect(solutions[keyR])
> return solutions.get(key)
> else:
> maxJ = ceil(log(distance(Xi, Yi, Xf, Yf))/log(2)+1) if distance(Xi
> , Yi, Xf, Yf) > 0 else 1
> lowestJumps = float("inf")
> (result, d) = recursiveJumps(lowestJumps, maxJ + 1, Xf, Yf, Xi, Yi
> , totalD, jumpN)
>
> solutions["{}_{}".format(Xf, Yf)] = result
> return result
>
> if __name__ == "__main__":
> T = int(input())
> solutions = dict()
> for i in range(1, T+1):
> [Xf, Yf] = map(lambda i: int(i), input().split())
> result = findJumps(Xf, Yf, 0, 0, 0, 1, solutions)
> print("Case #{}: {}".format(i, result))
>
> Likewise, this version, doesn't (I changed it to the other one due to LTE 
> on the second test):
>
> from math import sqrt, ceil, log
>
> MAX_SIZE = 10**4
> possible = [(0,-1),(-1,0),(0,1),(1,0)]
>
> def evenReachable(Xi, Yi, Xf, Yf):
> if (Xi + Yi) == 0 or (Xf + Yf) == 0:
> return True
> else:
> return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)
>
> def distance(Xi, Yi, Xf, Yf):
> return sqrt((Xf-Xi)**2+(Yf-Yi)**2)
>
> def getCase(Xi, Yi, Xn, Yn):
> if Xn > Xi:
> return 'E'
> if Xn < Xi:
> return 'W'
> if Yn > Yi:
> return 'N'
> if Yn < Yi:
> return 'S'
> return ""
>
> def recursiveJumps(maxJ, Xf, Yf, Xi, Yi, totalD, jumpN, covered, 
> oldResults = []):
> requiredD = distance(Xi, Yi, Xf, Yf) + totalD
> result = oldResults[-1] if len(oldResults) else ""
>
> if (jumpN > maxJ) or evenReachable(Xf, Yf, Xi, Yi) == 0:
> return ("IMPOSSIBLE", float("inf"))
> 
> if (Xf == Xi and Yf == Yi):
> # print("goal!")
> return (result, totalD)
>
> possibleResults = []
>
> for i,j in possible:
> Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
> Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
> newD = distance(Xi,Yi, Xn, Yn) + totalD
>
> if (newD <= requiredD):
> newResult = result + getCase(Xi, Yi, Xn, Yn)
> newResult = oldResults[0:-1]+[newResult]
> (newResult, newD) = recursiveJumps(maxJ, Xf, Yf, Xn, Yn, newD, 
> jumpN+1, covered + [(Xn, Yn)], newResult)
> if (newD >= requiredD) and newResult != "IMPOSSIBLE":
> possibleResults.append((newResult, newD))
>
> if not len(possibleResults):
> return ("IMPOSSIBLE", float("inf"))
> else:
> possibleResults.sort(key = lambda x: len(x[0]))
> return possibleResults[0]
>
> def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN):
> maxJ = ceil(log(distance(Xi, Yi, 

[gcj] Re: Inexplicable "Wrong Answer" (Blindfolded Bullseye, Round 1B 2020)

[porker2008]

Also, your *binary_search_right()* is incorrect, it fails when *left = 
10**9 - 1* and *func(10**9)* is *HIT*
In this case, it returns *10**9 - 1* instead of *10**9*

Wrong implementation:
*def binary_search_right(self, left, func):*
*right = 10**9*
*while left < right:*
*m = (left + right) // 2*
*f = func(m)*
*if f == 'HIT':*
*left = m + 1*
*elif f == 'MISS':*
*right = m*
*else:*
*return None*
*return right - 1*


Correct implementation:
*def binary_search_right(self, left, func):*
*right = 10**9*
*while left < right:*
*m = (left + right + 1) // 2*
*f = func(m)*
*if f == 'HIT':*
*left = m*
*elif f == 'MISS':*
*right = m - 1*
*else:*
*return None*
*return right*

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/bd58d574-1c92-4606-a56a-ad4c9976a09b%40googlegroups.com.

[gcj] Re: Inexplicable "Wrong Answer" (Blindfolded Bullseye, Round 1B 2020)

[porker2008]

While test data is not random, your solution is.

It is very likely that you have a bug in your code that in some cases, the 
random number you generated cause your program to behave incorrectly.


-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/6455f745-047b-4f89-8df4-70d3eb2eae81%40googlegroups.com.

[gcj] Re: Expogo BFS solution corner case

[Matt Fenlon]

-4 -1 is outputting IMPOSSIBLE when a possible path is NSW. As a matter of 
fact, all solutions involving 1 and 4, positive and negative, say 
IMPOSSIBLE. Maybe the program is failing to account for the fact that you 
can use 1 and -2 or -1 and 2 to reach -1 and 1 respectively? Hope this 
helps.

Best,
Matt

On Monday, April 20, 2020 at 12:38:18 PM UTC-4, Cheung Scott wrote:
>
> Hi guys, I wrote a straight forward BFS solution to solve 1B Expogo 
> question, targeting to solve test set 1 and 2.
> However, not knowing which corner case it fails, the solution got WA.
> Basic cases are all past locally, anyone could advise why below solution 
> fails?
>
> import java.util.Arrays;
> import java.util.LinkedList;
> import java.util.Queue;
> import java.util.Scanner;
>
> public class Solution {
>
> private static final int LIMIT = 400; // target at set 2: limit 100, 
> loosen a bit
> private static final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
> private static final String[] ways = {"N", "S", "E", "W"};
>
> private static String solve(int x, int y) {
> int maxStep = (int) (Math.log(LIMIT) / Math.log(2) + 1);
> Queue queue = new LinkedList<>();
> boolean[][] visited = new boolean[2*LIMIT+1][2*LIMIT+1];
> String[][] paths = new String[2*LIMIT+1][2*LIMIT+1];
> for (String[] path : paths) Arrays.fill(path, "");
> queue.offer(new int[]{0, 0});
> //visited[LIMIT][LIMIT] = true; // let (0, 0) output IMPOSSIBLE
> int step = 0, dist;
> while (!queue.isEmpty() && step <= maxStep + 3) { // loosen a bit
> int size = queue.size();
> dist = (int) Math.pow(2, step);
> for (int s = 0; s < size; s++) {
> int[] cell = queue.poll();
> if (step > 0 && cell[0] == x && cell[1] == y) return 
> paths[x+LIMIT][y+LIMIT]; // let (0, 0) output IMPOSSIBLE
> for (int i = 0; i < 4; i++) {
> int xx = cell[0] + dirs[i][0] * dist;
> int yy = cell[1] + dirs[i][1] * dist;
> if (xx >= -LIMIT && xx <= LIMIT && yy >= -LIMIT && yy 
> <= LIMIT && !visited[xx+LIMIT][yy+LIMIT]) {
> visited[xx+LIMIT][yy+LIMIT] = true;
> queue.offer(new int[]{xx, yy});
> paths[xx+LIMIT][yy+LIMIT] = 
> paths[cell[0]+LIMIT][cell[1]+LIMIT] + ways[i];
> }
> }
> }
> step++;
> }
> return "IMPOSSIBLE";
> }
>
> public static void main(String[] args) {
> Scanner in = new Scanner((System.in));
> int T = in.nextInt(); // Scanner has functions to read ints, 
> longs, strings, chars, etc.
> for (int ks = 1; ks <= T; ++ks) {
> int x = in.nextInt();
> int y = in.nextInt();
> System.out.println("Case #" + ks + ": " + solve(x, y));
> }
> }
> }
>
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/5717e0a9-37c1-4e9b-b4a5-2315ce3a379f%40googlegroups.com.

[gcj] Re: [JAVA] Round 1B - Expogo (Reader stuck at input)

[Matt Fenlon]

I have little practice with Java, but take a look at this link: 
https://codingcompetitions.withgoogle.com/codejam/submissions/0019fef2/ZWF0bW9yZQ

These are submissions from the 18th place finisher in the competition. 
Compare your code to this. Maybe you will catch something.

Best,
Matt

On Monday, April 20, 2020 at 12:37:39 PM UTC-4, aman kumar wrote:
>
> Hi
> I'm just a beginner in Java. 
>
> I was attempting to submit my solution for  *Round 1B - Expogo.*
>
> The sample test case was :
>
> * 4
>  2   3
> -2  -3
>  3   0
> -1   1*
>
>
> It did not had a new line character or any delimiter such as space which 
> tells the BufferedReader or Scanner to stop waiting for input. 
> For now the reader will keep stuck and gives a RE. If we add a new line 
> character at the end it works perfectly.
> How to overcome such cases ?
>
> Thanks
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3061bc9e-e970-4aa7-b3f4-ca95bc49adee%40googlegroups.com.

[gcj] Re: Pattern Matching: WA for Test Set 2

[Matt Fenlon]

It's this little block right here:

   if (j2 != n - 1) {
   right.push_back(s.substr(j2 + 1));
   }

specifically the condition. n-1 should be s.length()-1. Change that over, 
and it passes all test cases.

Best,
Matt

On Monday, April 20, 2020 at 12:37:35 PM UTC-4, Sahil Bansal wrote:
>
> #include 
> using namespace std;
> #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
> typedef long long ll;
> const ll MOD = 1e9 + 7;
> #define endl '\n'
>
> bool len_function (string a, string b) {
>int m = a.length();
>int n = b.length();
>return m <= n;
> }
> void solve(int case_no) {
>
> int n;
>cin >> n;
>
> vector left, right;
>string mid = "";
>for (int i = 0; i < n; ++i) {
>string s;
>cin >> s;
>
>int j1 = s.find("*");
>int j2 = s.find_last_of("*");
>if (j1 != 0) {
>left.push_back(s.substr(0, j1));
>}
>if (j2 != n - 1) {
>right.push_back(s.substr(j2 + 1));
>}
>string temp = "";
>for (int j = j1 + 1; j < j2; ++j) {
>if (s[j] != '*') {
>temp += s[j];
>}
>}
>mid += temp;
>}
>
> int ls = left.size();
>int rs = right.size();
>  
>string ansleft = "";
>for (int i = 0; i < ls; ++i) {
>if (left[i].length() >= ansleft.length()) {
>ansleft = left[i];
>}
>}
>string ansright = "";
>for (int i = 0; i < rs; ++i) {
>if (right[i].length() >= ansright.length()) {
>ansright = right[i];
>}
>}
>
> int p1 = ansleft.length();
>int p2 = ansright.length();
>
>bool poss = true;
>if (ls >= 2) {
>for (int i = 0; i <= ls - 1; ++i) {
>string s = left[i];
>int m = s.length();
>if (m == 0) {
>continue;
>}
>for (int j = 0; j < min(m, p1); ++j) {
>if (s[j] != ansleft[j]) {
>poss = false;
>break;
>}
>}
>if (poss == false) {
>break;
>}
>}
>}
>if (rs >= 2) {
>for (int i = 0; i <= rs - 1; ++i) {
>string s = right[i];
>int m = s.length();
>if (m == 0) {
>continue;
>}
>for (int j = 0; j < min(m, p2); ++j) {
>if (s[m - j - 1] != ansright[p2 - j - 1]) {
>poss = false;
>break;
>}
>}
>if (poss == false) {
>break;
>}
>}
>}
>string res;
>if (!poss) {
>res = "*";
>} else {
>res = ansleft;
>res += mid;
>res += ansright;
>}
>//*/
>cout << "Case #" << case_no << ": " << res << endl;
> }
>
> int main() {
>FAST_IO;
>
> int t;
>cin >> t;
>
> for (int id = 1; id <= t; ++id) {
>solve(id);
>}
>
>return 0;
> }
>
> Unable to find the mistake in the code, please help.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/2ec8d3ed-4185-4fb5-b294-befdc19dac55%40googlegroups.com.

[gcj] Re: Sample Failed RE

[Matt Fenlon]

Get rid of this line:

{package p3;}

You don't need it, and it makes the judge all moody ;)

Best,
Matt

On Monday, April 20, 2020 at 12:37:16 PM UTC-4, Moustafa Farouk wrote:
>
> Code works fine on local eclipse. Returns Runtime Error on KickStart 
> platform. Any idea?
> Round B 2020 - 1st problem:
>
> package p3;
>
> import java.io.BufferedReader;
> import java.io.InputStreamReader;
> import java.util.ArrayList;
> import java.util.List;
> import java.util.Scanner;
>
> public class Solution {
>
> public static int checkPeakPoints(int n, int[] arr) {
> int peak = 0;
> for (int i = 1; i < arr.length - 1; i++) {
> if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
> peak++;
> }
> return peak;
> }
>
> public static void main(String[] args) {
> Scanner in = new Scanner(new BufferedReader(new 
> InputStreamReader(System.in)));
> int t = in.nextInt();
> List x = new ArrayList();
> for (int i = 1; i <= t; ++i) {
> int n = in.nextInt(); // number of arr
> int[] arr = new int[n];
> for (int j = 1; j <= n; j++) {
> int m = in.nextInt();
> arr[j-1] = m;
> }
> x.add(arr);
> }
> StringBuilder sb = new StringBuilder();
> for (int i = 0; i < x.size(); i++) {
> int[] arr = x.get(i);
> int sol = checkPeakPoints(arr.length, arr);
> sb.append("Case #"+(i+1)+": "+sol+"\n");
> }
> System.out.println(sb.toString());
> }
> }
>
>
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/a78522b4-9c23-4c07-9fbc-5e0b1b1ed3b4%40googlegroups.com.

[gcj] Re: Square Dance from Round 1A: Cannot figure out correct solution

[Matt Fenlon]

My python is a bit rusty, so bear with me. I feel as if there is a problem 
with this line:

{s[l['x']][l['y']] = 0}

in the solve() method. Consider the following case on a 2x3 floor where 
each digit represents the competitor's skill level:

3   2   3

5   1   2 

after Round 1, the floor should look like this:

--   3

5   -   2

However, your algorithm sets to the board to this:

-   2   3

5   -   -

Here's why. When you set the skill level of a competitor to 0 and remove 
them from the linked list, they are no longer being considered when they 
should be. For example, the competitor in the top left gets eliminated, but 
their skill level should still be taken into account when evaluating the 
remaining competitors in that round. More specifically, for the competitor 
in the top middle, the average (if we look at the full board) skill level 
of surrounding competitors is 2.33 which is, of course, greater than 2, so 
this person gets eliminated. But, if we set our first competitor's skill to 
0 before we evaluate the second, then the average drops from 2.33 to 2, and 
top-middle competitor lives to fight another day. In a nutshell, this may 
cause competitors *to last longer than they should be*, which could be 
resulting in your TLE. Hope this helps.

Best,
Matt


On Monday, April 13, 2020 at 12:07:56 PM UTC-4, Bohdan Dovhan wrote:
>
> During Round 1A I wasn't able to submit correct solution in time.
> When round finished, I have submitted solution which shown in Practice 
> Correct result for 3A and TLE for 3B.
>
> I read Analysis and wrote an "optimized" version but instead of receiving 
> both Correct results, I received TLE for 3A.
>
> Can anyone help to understand why optimized version written by solution 
> analysis guideline doesn't work?
>
> This is my code without optimisation
>
> import sys, copy;
> debug = False
> def pem(a):
> for i in range(len(a)):
> print  >> sys.stderr, ' '.join(map(str, a[i]))
> 
> def verify(r,c,i,j,s):
> if debug:
> print  >> sys.stderr, ' i ', i, ' j ', j
> 
> k = i-1
> comp = []
> while k >= 0:
> if s[k][j] > 0:
> comp.append(s[k][j])
> if debug:
> print  >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]- ', s[k
> ][j], ' comp ', comp
> break
> k-=1
> k = i+1
> while k < r:
> if s[k][j] > 0:
> comp.append(s[k][j])
> if debug:
> print  >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]+ ', s[k
> ][j], ' comp ', comp
> break
> k+=1
>
>
> l = j-1
> while l >= 0:
> if s[i][l] > 0:
> comp.append(s[i][l])
> if debug:
> print  >> sys.stderr, ' i ', i, ' l ', l, ' s[il]- ', s[i
> ][l], ' comp ', comp
> break
> l-=1
> l = j+1
> while l < c :
> if s[i][l] > 0:
> comp.append(s[i][l])
> if debug:
> print  >> sys.stderr, ' i ', i, ' l ', l, ' s[il]+ ', s[i
> ][l], ' comp ', comp
> break
> l+=1
> if debug:
> print  >> sys.stderr, ' #competitors ', len(comp)
> if len(comp) > 0:
> print  >> sys.stderr, ' average ', float(sum(comp))/len(comp)
> return False if len(comp) == 0 else float(sum(comp))/len(comp) > s[i][
> j]
> def solve(r,c,s):
> eliminationHappens = True
> su = 0
> while eliminationHappens:
> su += sum([sum(s[i]) for i in range(r)])
> eliminationHappens = False
> cop = copy.deepcopy(s)
> for i in range(r):
> for j in range(c):
> if s[i][j] > 0:
> if verify(r,c,i,j,cop):
> s[i][j] = 0
> eliminationHappens = True
> if debug:
> print  >> sys.stderr, 's ' 
> pem(s)
> return str(su);
>
>
> t = int(raw_input())
> for i in range(1, t + 1):
> r,c = map(int,raw_input().split())
> s = [map(int,raw_input().split()) for j in range(r)]
> print "Case #" + str(i) + ": " + solve(r,c,s)
>
>
>
> and this is the optimized version
>
> import sys, copy;
> debug = False
> def pem(a):
> for i in range(len(a)):
> print  >> sys.stderr, ' '.join(map(str, a[i]))
> def buildLinkedList(r,c,s):
> return [[buildLLI(r,c,i,j,s) for j in range(c)] for i in range(r)]
>  
> def buildLLI(r,c,i,j,s):
> upper = None
> lower = None
> left = None
> right = None
> k = i-1
> while k >= 0:
> if s[k][j] > 0:
> upper = {'x':k,'y':j,'s':s[k][j]}
> break
> k-=1
> k = i+1
> while k < r:
> if s[k][j] > 0:
> lower = {'x':k,'y':j,'s':s[k][j]}
> break
> k+=1
>
>
> l = j-1
> while l >= 0:
> if s[i][l] > 0:
> left = {'x':i,'y':l,'s':s[i][l]}
> break
> l-=1
> l = j+1
> while l < c 

Re: [gcj] Re: Help with run time error on Bus Routes

[Randall Woodruff]

Thank you!  I miss read the 10^12 as 2^12.  What an expensive lesson.
Thanks!

On Mon, Apr 20, 2020 at 3:48 PM porker2008  wrote:

> You need to use long long to handle the day because it is out of range of
> 32-bit integers.
>
>
> -
>
>
> *#include *
> *#include *
> *#include *
> *using namespace std;*
>
> *long long calcTime();*
> *vector readVector(int n);*
>
> *int main() {*
> * int nCases = 0;*
> * cin >> nCases;*
>
> * for (int i = 0; i < nCases; i++) {*
> * long long maxDay = calcTime();*
> * cout << "Case #" << i + 1 << ": " << maxDay << endl;*
> * }*
>
> *}*
>
> *long long calcTime() {*
> * int n = 0;*
> * long long d = 0;*
> * cin >> n;*
> * cin >> d;*
> * vector routes = readVector(n);*
> * long long currDay = d;*
>
> * for (int i = n - 1; 0 <= i; i--) {*
> * currDay -= currDay % routes[i];*
> * }*
> * return currDay;*
> *}*
>
> *vector readVector(int n) {*
> * vector rtnV;*
> * for (int i = 0; i < n; i++) {*
> * long long temp = 0;*
> * cin >> temp;*
> * rtnV.push_back(temp);*
> * }*
> * return rtnV;*
> *}*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/d03b785e-71c1-4fc7-abc3-4f10d3686278%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAAjo1BfJ6pjwDzOFzzfsdGzLr7AF3gEuMGHQaimfqzo0q5791A%40mail.gmail.com.

Re: [gcj] RE in bike tour problem round B Kickstart

[chitaranjan pradhan]

Taking test case loop and again ur print the output in another loop

Thank You
Chitaranjan Pradhan

On Mon, 20 Apr, 2020, 10:09 PM vishakha narang, 
wrote:

> *package* bike_tour;
>
>
> *import* java.util.Scanner;
>
> *import* java.io.*;
>
>
> *public* *class* Solution {
>
>
> *public* *static* *void* main(String[] args) {
>
> Scanner in = *new* Scanner(*new* BufferedReader(*new*
> InputStreamReader(System.*in*)));
>
> *if*(in.hasNext())
>
> {
>
> *int* t = in.nextInt();
>
> *int* peaks[] = *new* *int*[t];
>
> *for*(*int* i = 0;i
> {
>
> *int* n = in.nextInt();
>
> *int* arr[] = *new* *int*[n];
>
>
> *for*(*int* j = 0;j
> {
>
> arr[j] = in.nextInt();
>
>
> }
>
> *for*(*int* j = 1;j<(n-1);j++)
>
> {
>
> *if*(arr[(j-1)]arr[(j+1)])
>
> {
>
> peaks[i]++;
>
> }
>
> }
>
> }
>
> *for*(*int* j = 0;j
> {
>
> System.*out*.println("Case #"+(j+1)+": "+peaks[j]);
>
> }
>
> }
>
> }
>
>
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/7e7d9e8b-68d3-4a71-aedf-747ac3ac3c33%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAAGy8Wu-z2FWEWssbmyOmQ0NPu66b0JxMvUZy%2BrPWHaiZzHJ9A%40mail.gmail.com.

Re: [gcj] Round 1B - Join the Ranks

[porker2008]

AFAICT, your solution is exactly what the analysis is trying to do.

Your code is simply doing the work in a more effective way. (by keeping 
track of how many cards in pile A and where to insert it into pile B)

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/48f12a9c-844d-424e-8ae2-5bb96438bd8c%40googlegroups.com.

[gcj] Re: Help with run time error on Bus Routes

[porker2008]

You need to use long long to handle the day because it is out of range of 
32-bit integers.


-


*#include *
*#include *
*#include *
*using namespace std;*

*long long calcTime();*
*vector readVector(int n);*

*int main() {*
* int nCases = 0;*
* cin >> nCases;*

* for (int i = 0; i < nCases; i++) {*
* long long maxDay = calcTime();*
* cout << "Case #" << i + 1 << ": " << maxDay << endl;*
* }*

*}*

*long long calcTime() {*
* int n = 0;*
* long long d = 0;*
* cin >> n;*
* cin >> d;*
* vector routes = readVector(n);*
* long long currDay = d;*

* for (int i = n - 1; 0 <= i; i--) {*
* currDay -= currDay % routes[i];*
* }*
* return currDay;*
*}*

*vector readVector(int n) {*
* vector rtnV;*
* for (int i = 0; i < n; i++) {*
* long long temp = 0;*
* cin >> temp;*
* rtnV.push_back(temp);*
* }*
* return rtnV;*
*}*

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/d03b785e-71c1-4fc7-abc3-4f10d3686278%40googlegroups.com.

[gcj] Re: Round 1b 2020 BUS routes problem

[porker2008]

Your approach is wrong IMO.

Please checkout the analysis and try to understand the intended solution.

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3f30e57f-be0e-43e3-a1f8-4a93b152ad3b%40googlegroups.com.

[gcj] Re: Round B 2020 - Bike Tour - Python3

[porker2008]

should be *m[j + 2]* instead of *m[j]* at line 11


*t = int(input())*
*for i in range(0, t * 2, 2):*
*n = int(input())*
*m = [int(x) for x in input().split()]*
*peaks = 0*
*before, current, after = m[0], m[1], m[2]*
*for j in range(1, n - 1):*
*if before < current and current > after:*
*peaks += 1*
*if j + 2 < n:*
*before, current, after = current, after, m[j + 2]*

*print("Case #{}: {}".format(str(int(i/2 + 1)), str(peaks)))*

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/9e3e62a6-0360-4908-939f-c50da740dbc5%40googlegroups.com.

Re: [gcj] RE in bike tour problem round B Kickstart

[Radhika Sethi]

Try removing the package declaration and it should work.

On Mon, 20 Apr, 2020, 10:09 PM vishakha narang, 
wrote:

> *package* bike_tour;
>
>
> *import* java.util.Scanner;
>
> *import* java.io.*;
>
>
> *public* *class* Solution {
>
>
> *public* *static* *void* main(String[] args) {
>
> Scanner in = *new* Scanner(*new* BufferedReader(*new*
> InputStreamReader(System.*in*)));
>
> *if*(in.hasNext())
>
> {
>
> *int* t = in.nextInt();
>
> *int* peaks[] = *new* *int*[t];
>
> *for*(*int* i = 0;i
> {
>
> *int* n = in.nextInt();
>
> *int* arr[] = *new* *int*[n];
>
>
> *for*(*int* j = 0;j
> {
>
> arr[j] = in.nextInt();
>
>
> }
>
> *for*(*int* j = 1;j<(n-1);j++)
>
> {
>
> *if*(arr[(j-1)]arr[(j+1)])
>
> {
>
> peaks[i]++;
>
> }
>
> }
>
> }
>
> *for*(*int* j = 0;j
> {
>
> System.*out*.println("Case #"+(j+1)+": "+peaks[j]);
>
> }
>
> }
>
> }
>
>
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/7e7d9e8b-68d3-4a71-aedf-747ac3ac3c33%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAJwGY1UVm7EGtnF85L97w%3DDU3CgM4gk8v4TRngdq2ENXKu0u-w%40mail.gmail.com.

[gcj] Re: Java RE!

[porker2008]

Maybe you should remove the package declaration?


-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/cf274167-92cf-401b-b780-4dd5f0139212%40googlegroups.com.

[gcj] RE in bike tour problem round B Kickstart

[vishakha narang]

*package* bike_tour;


*import* java.util.Scanner;

*import* java.io.*;


*public* *class* Solution {


*public* *static* *void* main(String[] args) {

Scanner in = *new* Scanner(*new* BufferedReader(*new* 
InputStreamReader(System.*in*)));

*if*(in.hasNext())

{

*int* t = in.nextInt();

*int* peaks[] = *new* *int*[t];

*for*(*int* i = 0;iarr[(j+1)])

{

peaks[i]++;

}

}

}

*for*(*int* j = 0;jhttps://groups.google.com/d/msgid/google-code/7e7d9e8b-68d3-4a71-aedf-747ac3ac3c33%40googlegroups.com.

[gcj] Round 1b 2020 BUS routes problem

[D A Mahesh]

from math import ceil
t=int(input())
for p in range(1,t+1):
n,d=map(int,input().split())
a=list(map(int,input().split()))
minn=0
i=0
j=0
for y in a:
b=(d//y)*y
if(i!=0):
if(minn>b):
mi=m-(a[j]*ceil((m-b)/a[j]))
if(minn>mi):
minn=mi
j+=1
else:
minn=b
m=b
i+=1
print("Case #{}: {}".format(p,minn))
Whats wrong in my code??
my results are wrong answer and test set skipped
the code is working good on sample test.
please help me to find out the mistake.
note - Im just a beginner

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/594922b0-e1d8-4a1f-8fb6-da1f3524bce0%40googlegroups.com.

[gcj] Inexplicable "Wrong Answer" (Blindfolded Bullseye, Round 1B 2020)

[XYZT]

My Python 3 submission got a "Wrong Answer" on Test Set 1 inexplicably. 
Since then, I have made the same submission over and over again, and it 
always passes. For Test Set 1, there should be no RNG in the solution - so 
I don't see how there can be a "Wrong Answer". Unfortunately, I can't seem 
to reproduce this - all my Practice Attempts since with identical code has 
successfully passed all Test sets:





I'd love to know if anyone can reproduce this error that appears to be on 
the server-side. I am pasting my code below:

# Codejam 2020, Round 1B: Blindfolded Bullseye

import sys
from random import randint


class Case:
def __init__(self):
self.queries_left = 300

def query(self, X, Y):
self.queries_left -= 1
print("{} {}".format(X, Y), flush=True)
response = input()
if response == 'WRONG':
sys.exit()
return response

def binary_search_left(self, right, func):
left = -10**9
while left < right:
m = (left + right) // 2
f = func(m)
if f == 'HIT':
right = m
elif f == 'MISS':
left = m + 1
else:
return None
return left

def binary_search_right(self, left, func):
right = 10**9
while left < right:
m = (left + right) // 2
f = func(m)
if f == 'HIT':
left = m + 1
elif f == 'MISS':
right = m
else:
return None
return right - 1

def solve(self):
x, y = 0, 0
r = self.query(x, y)
while r == 'MISS':
x, y = randint(-10**9, 10**9), randint(-10**9, 10**9)
r = self.query(x, y)

if r == 'CENTER':
return

x_low = self.binary_search_left(x, lambda x: self.query(x, y))
if x_low is None:
return

x_high = self.binary_search_right(x, lambda x: self.query(x, y))
if x_high is None:
return

y_low = self.binary_search_left(y, lambda y: self.query(x, y))
if y_low is None:
return

y_high = self.binary_search_right(y, lambda y: self.query(x, y))
if y_high is None:
return

r = self.query((x_low + x_high) // 2, (y_low + y_high) // 2)
if r != 'CENTER':
sys.exit()


# I/O Code
num_cases, A, B = map(int, input().split())

for _ in range(1, num_cases + 1):
case = Case()
case.solve()

sys.exit()


Thanks

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3c160542-486b-4d3b-add5-7268e05f4d8e%40googlegroups.com.

[gcj] [2020][PYTHON3][Expogo] RE on judge

[Nabil Marquez]

Hello, the following code always gives me RE on the judge (during the first 
test set):

from math import sqrt, ceil, log

possible = [(0,1),(1,0),(0,-1),(-1,0)]

reflected = {
"E" : "W",
"W" : "E",
"S" : "N",
"N" : "S",
}

def evenReachable(Xi, Yi, Xf, Yf):
if ((Xi + Yi) == 0) or ((Xf + Yf) == 0):
return True
else:
return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)

def distance(Xi, Yi, Xf, Yf):
return sqrt((Xf-Xi)**2+(Yf-Yi)**2)

def getCase(Xi, Yi, Xn, Yn):
if Xn > Xi:
return 'E'
if Xn < Xi:
return 'W'
if Yn > Yi:
return 'N'
if Yn < Yi:
return 'S'

def reflect(solution):
return ''.join([reflected[c] for c in solution])

def recursiveJumps(lowestJumps, maxJ, Xf, Yf, Xi, Yi, totalD, jumpN, 
oldResult = ""):
requiredD = distance(Xi, Yi, Xf, Yf) + totalD
result = oldResult

if (jumpN > maxJ) or (jumpN > lowestJumps) or not evenReachable(Xf, Yf, 
Xi, Yi):
return ("IMPOSSIBLE", float("inf"))

if (Xf == Xi and Yf == Yi):
# print("goal!")
return (result, totalD)

bestResult = None

for i,j in possible:
Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
newD = distance(Xi,Yi, Xn, Yn) + totalD

if (newD <= requiredD):
newResult = result + getCase(Xi, Yi, Xn, Yn)
(newResult, newD) = recursiveJumps(lowestJumps, maxJ, Xf, Yf, Xn
, Yn, newD, jumpN+1, newResult)

if (newD >= requiredD) and newResult != "IMPOSSIBLE" :
bestResult = (newResult, newD)
lowestJumps = jumpN + 1

return bestResult if bestResult is not None else ("IMPOSSIBLE", float(
"inf"))

def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN, solutions):
key = "{}_{}".format(Xf, Yf)
keyR = "{}_{}".format(-Xf, -Yf)

if key in solutions:
return solutions.get(key)
elif keyR in solutions:
solutions[key] = reflect(solutions[keyR])
return solutions.get(key)
else:
maxJ = ceil(log(distance(Xi, Yi, Xf, Yf))/log(2)+1) if distance(Xi, 
Yi, Xf, Yf) > 0 else 1
lowestJumps = float("inf")
(result, d) = recursiveJumps(lowestJumps, maxJ + 1, Xf, Yf, Xi, Yi, 
totalD, jumpN)

solutions["{}_{}".format(Xf, Yf)] = result
return result

if __name__ == "__main__":
T = int(input())
solutions = dict()
for i in range(1, T+1):
[Xf, Yf] = map(lambda i: int(i), input().split())
result = findJumps(Xf, Yf, 0, 0, 0, 1, solutions)
print("Case #{}: {}".format(i, result))

Likewise, this version, doesn't (I changed it to the other one due to LTE 
on the second test):

from math import sqrt, ceil, log

MAX_SIZE = 10**4
possible = [(0,-1),(-1,0),(0,1),(1,0)]

def evenReachable(Xi, Yi, Xf, Yf):
if (Xi + Yi) == 0 or (Xf + Yf) == 0:
return True
else:
return not ((Xf+Yf) % 2 == 0 and (Xi+Yi) % 2 == 0)

def distance(Xi, Yi, Xf, Yf):
return sqrt((Xf-Xi)**2+(Yf-Yi)**2)

def getCase(Xi, Yi, Xn, Yn):
if Xn > Xi:
return 'E'
if Xn < Xi:
return 'W'
if Yn > Yi:
return 'N'
if Yn < Yi:
return 'S'
return ""

def recursiveJumps(maxJ, Xf, Yf, Xi, Yi, totalD, jumpN, covered, oldResults 
= []):
requiredD = distance(Xi, Yi, Xf, Yf) + totalD
result = oldResults[-1] if len(oldResults) else ""

if (jumpN > maxJ) or evenReachable(Xf, Yf, Xi, Yi) == 0:
return ("IMPOSSIBLE", float("inf"))

if (Xf == Xi and Yf == Yi):
# print("goal!")
return (result, totalD)

possibleResults = []

for i,j in possible:
Xn = Xi+i*2**(jumpN-1) if jumpN-1 >= 0 else Xi
Yn = Yi+j*2**(jumpN-1) if jumpN-1 >= 0 else Yi
newD = distance(Xi,Yi, Xn, Yn) + totalD

if (newD <= requiredD):
newResult = result + getCase(Xi, Yi, Xn, Yn)
newResult = oldResults[0:-1]+[newResult]
(newResult, newD) = recursiveJumps(maxJ, Xf, Yf, Xn, Yn, newD, 
jumpN+1, covered + [(Xn, Yn)], newResult)
if (newD >= requiredD) and newResult != "IMPOSSIBLE":
possibleResults.append((newResult, newD))

if not len(possibleResults):
return ("IMPOSSIBLE", float("inf"))
else:
possibleResults.sort(key = lambda x: len(x[0]))
return possibleResults[0]

def findJumps(Xf, Yf, Xi, Yi, totalD, jumpN):
maxJ = ceil(log(distance(Xi, Yi, Xf, Yf))/log(2)+1) if distance(Xi, Yi, 
Xf, Yf) > 0 else 0
(result, d) = recursiveJumps(maxJ + 1, Xf, Yf, Xi, Yi, totalD, jumpN, [(
0,0)])

return result

if __name__ == "__main__":
T = int(input())
for i in range(1, T+1):
[Xf, Yf] = map(lambda i: int(i), input().split())
result = findJumps(Xf, Yf, 0, 0, 0, 1)
print("Case #{}: {}".format(i, result))


Do you have any idea of what might be wrong? Thanks a lot!

-- 
You received this message because you are subscribed 

[gcj] What's my mistake? - [Round 1B - 2020 : Expogo]

[Rohan Shukla]

Just attempted the GCJ 2020 : Round 1B. I was able to solve Blindfolded 
Bullseye but my code for Expogo gave wrong answer. Would have got a good 
score if I could have cracked this as well. 
Here's my python3 code.

T = int(input())
t = 1 
while(t <= T):
res = ""
Y = input().split(" ")
X = int(Y[0])
Y = int(Y[1])
X1 = abs(X)
Y1 = abs(Y)
while(X1 > 4 or Y1 > 4):
if((X1+Y1)%2 == 0):
res = "IMPOSSIBLE"
break
else:
if(X1 % 2 != 0):
c1 = (X1+1)//2 + (Y1)//2
c2 = (X1-1)//2 + (Y1)//2
if(c1 % 2 == 0):
res += "E"
X1 = (X1-1)//2
else:
res += "W"
X1 = (X1+1)//2
Y1 //= 2
elif(Y1 % 2 != 0):
c1 = (Y1+1)//2 + (X1)//2
c2 = (Y1-1)//2 + (X1)//2
if(c1 % 2 == 0):
res += "S"
Y1 = (Y1-1)//2
else:
res += "N"
Y1 = (Y1+1)//2
X1 //= 2
else: 
break
if(X1 == 0 and Y1 == 1):
res += "S"
elif(X1 == 1 and Y1 == 0):
res += "E"
elif(X1 == 0 and Y1 == 3):
res += "SS"
elif(X1 == 3 and Y1 == 0):
res += "EE"
elif(X1 == 1 and Y1 == 2):
res += "ES"
elif(X1 == 2 and Y1 == 1):
res += "SE"
elif(X1 == 2 and Y1 == 3):
res += "SEN"
elif(X1 == 3 and Y1 == 2):
res += "ESW"
elif(X1 == 1 and Y1 == 4):
res += "WES"
elif(X1 == 4 and Y1 == 1):
res += "NSE"
elif(X1 == 3 and Y1 == 4):
res += "EES"
elif(X1 == 4 and Y1 == 3):
res += "SSE"
else: 
res = "IMPOSSIBLE"
if(res != "IMPOSSIBLE"):
l = list(res)
if(X < 0):
for i in range(len(l)):
if(l[i] == "S"):
l[i] = 'N'
elif(l[i] == 'N'):
l[i] = 'S'
if(Y < 0):
for i in range(len(l)):
if(l[i] == "E"):
l[i] = 'W'
elif(l[i] == 'W'):
l[i] = 'E'
res = ''.join([str(elem) for elem in l])
print("Case #{}: {}".format(t,res))
t += 1

Would be great if someone could point out my mistake. 

Thanks in advance!

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/7b622114-7c6a-437d-8960-528bad2508cd%40googlegroups.com.

Re: [gcj] Round 1B - Join the Ranks

[Katalin Brányiné Sulák]

Editorial for this problem seems to be resulting an unnecessarly
complicated code.
Solution is O(R*S) and 15 LOC (python 3). [I missed it during the contest
"of course", as I spent much time on the interactive problem.]
The idea is same but it is easy to prove that resulting sizes for A and B
can be calculated by the fact, that one [actually the first]
2-difference-cancelling move is: A ends before the 3rd rank appears, and
the last card in B is always increased by 2, starting with R+1. End of A
can be calculated by just maintaining the longest same-rank so far for all
ranks.
Special case is the same [ending B for the last is R*S-2, not R*S-1], but
no need to count, it's always R-1, (S-1)*R.

Axioma / Kata





spoiler alert








-
T = int(input())
for tst in range(T):
R, S = map(int, input().split())
nums=[1]*R
i=0
todo=R*(S-1)
print("Case #" + str(tst + 1) + ": " + str((todo+1)//2))
for lst in range(R+1,R*S,2):
fst=nums[i]+nums[(i+1)%R]
print(fst,lst-fst)
nums[i]+=1
nums[(i+1)%R]+=1
i=(i+2)%R
if lst==R*S-2:
print(S-1,(R-1)*S)

'Samantha' via Google Code Jam  ezt írta
(időpont: 2020. ápr. 18., Szo 1:28):

> Hello,
>
> The time has come — the next chance to participate in Code Jam Round 1
> begins in under 48 hours with Round 1B! Visit the schedule page
>  to see
> rounds in your browser's local time zone and to add events to your
> calendar. *All posting on this group will be paused during all Code Jam
> online rounds.*
>
> *Important Reminders:*
>
>- Round 1 is divided into two more sub-rounds (1B and 1C). Each lasts
>for two hours and thirty minutes. You may compete in as many of the
>sub-rounds as you want, but if you place in the top 1500 in any sub-round,
>you'll qualify for Round 2 and won't be eligible to compete in any later
>sub-rounds
>- Round results will not be immediately finalized when the round is
>over. You'll be notified of your advancement status to Round 2 at least one
>day before that round in the "Alerts" section of the competition website
>and by email.
>- *Unlike in the Qualification Round, collaboration is strictly
>prohibited in Round 1 and all future rounds of Code Jam 2020.* Section
>7 of the Code Jam Terms
>
>prohibits sharing or using from others any information about a problem
>before the end of the round. Such actions that violate those Terms &
>Conditions will result in your disqualification. *Moreover, please
>note that if you are utilizing a web integrated development environment
>(IDE), be sure to not publish your code or otherwise allow it to be
>publicly visible during the contest, or you could be subject to
>disqualification.*
>
> If you have any questions, start by reviewing the FAQs
>  and Rules and
> Terms . If
> you have questions during the round, use the "Ask a Question" feature in
> the competition interface.
> Good luck to all of those who have advanced and are participating!
> -The Code Jam Team
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/e9bf2dd5-c5e3-4e87-9870-13b79a742b80%40googlegroups.com
> 
> .
>

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/CAPOU4JPgY73V_FCNGAb3dY46%2BK9H8TJgJRLKESd17Y2oH3v6kA%40mail.gmail.com.

[gcj] CodeJam 2020 Round 1B - 3.JoinTheRanks - WA for my submission

[Atif Hussain]

Hi, 
For Google CodeJam 2020 Round 1B - 3.JoinTheRanks - below was my C++ 
submission, which gave WA for hidden inputs. 
https://codingcompetitions.withgoogle.com/codejam/round/0019fef2/002d5b64
Please help identify my error - in code, or input where it fails. 


#include 
using namespace std;

int main()
{
int testcases; cin >> testcases;
for (int t = 1; t <= testcases; t++) {
int R, S; cin >> R >> S;

vector> deck(R*S);
for (int j = 0; j < S; j++)
for (int i = 0; i < R; i++)
deck[i + R * j].first = i + 1,
deck[i + R * j].second = j + 1;

vector> moves;
int till, from;
for (till = R * S - 1; till >= 0; till--) {
int toR = (till / S) + 1;
if (deck[till].first==toR) continue;

for (from = till - 1; deck[from].first != toR; from--); 

// deck[from].first = toR != deck[till].first
from++; till++;
moves.push_back(make_pair(from, till-from));
vector> A(deck.begin(), deck.begin() + from);
vector> B(deck.begin()+from, deck.begin() + 
till);
deck.erase(deck.begin() + from, deck.begin() + till);
deck.insert(deck.begin(), B.begin(), B.end());
}

cout << "Case #" << t << ": " << moves.size() << endl;
for (int i = 0; i < moves.size(); i++)
cout << moves[i].first << " " << moves[i].second << endl;
}
return 0;
}

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/c184071e-578b-4624-ade5-42129d013737%40googlegroups.com.

[gcj] Expogo Test Suites?

[birid]

Does anyone have a set of (or can generate, using a passed solution) of 
test cases for large X and Y? My solution didn't work for them, and as I 
took a completely different approach than the model solution, I'm curious 
where I went wrong. 

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/622dca4c-cf7d-487e-8b0d-bf09f3d9fb0b%40googlegroups.com.

[gcj] Expogo BFS solution corner case

[Cheung Scott]

Hi guys, I wrote a straight forward BFS solution to solve 1B Expogo 
question, targeting to solve test set 1 and 2.
However, not knowing which corner case it fails, the solution got WA.
Basic cases are all past locally, anyone could advise why below solution 
fails?

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {

private static final int LIMIT = 400; // target at set 2: limit 100, 
loosen a bit
private static final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
private static final String[] ways = {"N", "S", "E", "W"};

private static String solve(int x, int y) {
int maxStep = (int) (Math.log(LIMIT) / Math.log(2) + 1);
Queue queue = new LinkedList<>();
boolean[][] visited = new boolean[2*LIMIT+1][2*LIMIT+1];
String[][] paths = new String[2*LIMIT+1][2*LIMIT+1];
for (String[] path : paths) Arrays.fill(path, "");
queue.offer(new int[]{0, 0});
//visited[LIMIT][LIMIT] = true; // let (0, 0) output IMPOSSIBLE
int step = 0, dist;
while (!queue.isEmpty() && step <= maxStep + 3) { // loosen a bit
int size = queue.size();
dist = (int) Math.pow(2, step);
for (int s = 0; s < size; s++) {
int[] cell = queue.poll();
if (step > 0 && cell[0] == x && cell[1] == y) return 
paths[x+LIMIT][y+LIMIT]; // let (0, 0) output IMPOSSIBLE
for (int i = 0; i < 4; i++) {
int xx = cell[0] + dirs[i][0] * dist;
int yy = cell[1] + dirs[i][1] * dist;
if (xx >= -LIMIT && xx <= LIMIT && yy >= -LIMIT && yy 
<= LIMIT && !visited[xx+LIMIT][yy+LIMIT]) {
visited[xx+LIMIT][yy+LIMIT] = true;
queue.offer(new int[]{xx, yy});
paths[xx+LIMIT][yy+LIMIT] = 
paths[cell[0]+LIMIT][cell[1]+LIMIT] + ways[i];
}
}
}
step++;
}
return "IMPOSSIBLE";
}

public static void main(String[] args) {
Scanner in = new Scanner((System.in));
int T = in.nextInt(); // Scanner has functions to read ints, longs, 
strings, chars, etc.
for (int ks = 1; ks <= T; ++ks) {
int x = in.nextInt();
int y = in.nextInt();
System.out.println("Case #" + ks + ": " + solve(x, y));
}
}
}



-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/b4688fc7-0a3f-4b64-b401-02b520093d6c%40googlegroups.com.

[gcj] [JAVA] Round 1B - Expogo (Reader stuck at input)

[aman kumar]

Hi
I'm just a beginner in Java. 

I was attempting to submit my solution for  *Round 1B - Expogo.*

The sample test case was :

* 4
 2   3
-2  -3
 3   0
-1   1*


It did not had a new line character or any delimiter such as space which tells 
the BufferedReader or Scanner to stop waiting for input. 
For now the reader will keep stuck and gives a RE. If we add a new line 
character at the end it works perfectly.
How to overcome such cases ?

Thanks

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/fa893a2c-3272-4a6f-b6b5-846a71aad1cd%40googlegroups.com.

[gcj] WA- - GCJ'19 ROUND 1C - Robot Programming Strategy

[Rohan Shukla]

Hello all,

Was just attempting this question for practice and have used Python3.  I am 
repetitively getting WA and I am not able to find any specific case that I 
might have missed.

Here's the code: 

T = int(input())
t = 1
cas = ["P","R","S"]
while(t <= T):
res = ""
A = int(input())
l = []
for i in range(A):
l.append(input())
pos = 0
while(len(l) > 0):
#print(l)
al = []
for i in l:
if(i[pos%len(i)] not in al):
al.append(i[pos%len(i)])
if(len(al) == 1):
res += cas[(cas.index(al[0])-1)%3]
l.clear()
elif(len(al) == 3):
res = "IMPOSSIBLE"
l.clear()
else:
al = sorted(al)
if(al[1] == "S" and al[0] == "P"):
res += "S"
else:
res += al[0]
l = list(filter(lambda x: x[pos%len(x)] != al[1],l))
pos += 1
print("Case #{}: {}".format(t, res))
#print("Case #",t,": ",res,sep="")
t += 1

would be great if someone could help me out.

Thanks in advance! 

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/11d66745-c963-4ded-b944-b1090ec53a61%40googlegroups.com.

[gcj] WA in Robot Programming Strategy - Round 1C - GCJ '19

[Rohan Shukla]

Hello All!

Question : 
https://codingcompetitions.withgoogle.com/codejam/round/000516b9/00134c90
Was just trying out the robot programming strategy problem for practice. 
But I feel I am missing some constraint which is giving me an wrong  
answer. Here's my solution in Python3.

T = int(input())
t = 1
cas = ["P","R","S"]
while(t <= T):
res = ""
A = int(input())
l = []
for i in range(A):
l.append(input())
pos = 0
while(len(l) > 0):
#print(l)
al = []
for i in l:
if(i[pos%len(i)] not in al):
al.append(i[pos%len(i)])
if(len(al) == 1):
res += cas[(cas.index(al[0])-1)%3]
l.clear()
elif(len(al) == 3):
res = "IMPOSSIBLE"
l.clear()
else:
al = sorted(al)
if(al[1] == "S" and al[0] == "P"):
res += "S"
else:
res += al[0]
l = list(filter(lambda x: x[pos%len(x)] != al[1],l))
pos += 1
print("Case #{}: {}".format(t, res))
#print("Case #",t,": ",res,sep="")
t += 1

Would be great, if someone could point out where I am going Wrong.

Thanks in advance!

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/b4f68665-8c3a-4cac-b0f5-59d662b70dbc%40googlegroups.com.

[gcj] Sample Failed RE

[Moustafa Farouk]

Code works fine on local eclipse. Returns Runtime Error on KickStart 
platform. Any idea?
Round B 2020 - 1st problem:

package p3;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {

public static int checkPeakPoints(int n, int[] arr) {
int peak = 0;
for (int i = 1; i < arr.length - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
peak++;
}
return peak;
}

public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new 
InputStreamReader(System.in)));
int t = in.nextInt();
List x = new ArrayList();
for (int i = 1; i <= t; ++i) {
int n = in.nextInt(); // number of arr
int[] arr = new int[n];
for (int j = 1; j <= n; j++) {
int m = in.nextInt();
arr[j-1] = m;
}
x.add(arr);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < x.size(); i++) {
int[] arr = x.get(i);
int sol = checkPeakPoints(arr.length, arr);
sb.append("Case #"+(i+1)+": "+sol+"\n");
}
System.out.println(sb.toString());
}
}




-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/48131e7f-8609-4c5e-8ac0-9fd0eab8e968%40googlegroups.com.

[gcj] Java RE!

[Moustafa Farouk]

Code works fine on eclipse, but returns RE on kickstart. Any idea?

package p3;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {

public static int checkPeakPoints(int n, int[] arr) {
int peak = 0;
for (int i = 1; i < arr.length - 1; i++) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
peak++;
}
return peak;
}

public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new 
InputStreamReader(System.in)));
int t = in.nextInt();
List x = new ArrayList();
for (int i = 1; i <= t; ++i) {
int n = in.nextInt(); // number of arr
int[] arr = new int[n];
for (int j = 1; j <= n; j++) {
int m = in.nextInt();
arr[j-1] = m;
}
x.add(arr);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < x.size(); i++) {
int[] arr = x.get(i);
int sol = checkPeakPoints(arr.length, arr);
sb.append("Case #"+(i+1)+": "+sol+"\n");
}
System.out.println(sb.toString());
}
}



-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/3eacf230-b34f-47de-adb6-494dc8139eb1%40googlegroups.com.

[gcj] Round B 2020 - Bike Tour - Python3

[Scott Larsen]

Please help me understand where I went wrong on this one.  My output from 
the test data seemed to match the test output exactly so I'm not sure if it 
was some formatting I was missing or a hidden corner case but every 
submission I made returned WA.

Thanks,
Scott

*t = int(input())*
*for i in range(0, t * 2, 2):*
*n = input()*
*m = [int(x) for x in input().split()]*
*peaks = 0*
*before, current, after = m[0], m[1], m[2]*
*for j in range(1, len(m) - 1):*
*if before < current and current > after:*
*peaks += 1*
*before, current, after = current, after, m[j]*

*print("Case #{}: {}".format(str(int(i/2 + 1)), str(peaks)))*



Returns:

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 0

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/f5b0673b-114e-4259-890b-22914ec33ab2%40googlegroups.com.

[gcj] Help with run time error on Bus Routes

[Randall Woodruff]

Really Stumped, Got a Run time error during the competition and still have 
not been able to figure it out.  Any ideas welcome.  

#include 
#include 
#include 

using namespace std;

int calcTime();
vector readVector(int n);

int main() {
int nCases = 0;
cin >> nCases;

for (int i = 0; i < nCases; i++) {
int maxDay = calcTime();
cout << "Case #" << i + 1 << ": " << maxDay << endl;
}

}

int calcTime() {
int n = 0, d = 0;
cin >> n;
cin >> d;
vector routes = readVector(n);
int currDay = d;

for (int i = n - 1; 0 <= i; i--) {
currDay -= currDay % max(routes[i],1);
}
return currDay;
}


vector readVector(int n) {
vector rtnV;
for (int i = 0; i < n; i++) {
int temp = 0;
cin >> temp;
rtnV.push_back(temp);
}
return rtnV;
}

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/db640663-5f3e-44c0-90aa-5033000deede%40googlegroups.com.

[gcj] Pattern Matching: WA for Test Set 2

[Sahil Bansal]

#include 
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7;
#define endl '\n'

bool len_function (string a, string b) {
   int m = a.length();
   int n = b.length();
   return m <= n;
}
void solve(int case_no) {

int n;
   cin >> n;

vector left, right;
   string mid = "";
   for (int i = 0; i < n; ++i) {
   string s;
   cin >> s;
   
   int j1 = s.find("*");
   int j2 = s.find_last_of("*");
   if (j1 != 0) {
   left.push_back(s.substr(0, j1));
   }
   if (j2 != n - 1) {
   right.push_back(s.substr(j2 + 1));
   }
   string temp = "";
   for (int j = j1 + 1; j < j2; ++j) {
   if (s[j] != '*') {
   temp += s[j];
   }
   }
   mid += temp;
   }

int ls = left.size();
   int rs = right.size();
 
   string ansleft = "";
   for (int i = 0; i < ls; ++i) {
   if (left[i].length() >= ansleft.length()) {
   ansleft = left[i];
   }
   }
   string ansright = "";
   for (int i = 0; i < rs; ++i) {
   if (right[i].length() >= ansright.length()) {
   ansright = right[i];
   }
   }

int p1 = ansleft.length();
   int p2 = ansright.length();
   
   bool poss = true;
   if (ls >= 2) {
   for (int i = 0; i <= ls - 1; ++i) {
   string s = left[i];
   int m = s.length();
   if (m == 0) {
   continue;
   }
   for (int j = 0; j < min(m, p1); ++j) {
   if (s[j] != ansleft[j]) {
   poss = false;
   break;
   }
   }
   if (poss == false) {
   break;
   }
   }
   }
   if (rs >= 2) {
   for (int i = 0; i <= rs - 1; ++i) {
   string s = right[i];
   int m = s.length();
   if (m == 0) {
   continue;
   }
   for (int j = 0; j < min(m, p2); ++j) {
   if (s[m - j - 1] != ansright[p2 - j - 1]) {
   poss = false;
   break;
   }
   }
   if (poss == false) {
   break;
   }
   }
   }
   string res;
   if (!poss) {
   res = "*";
   } else {
   res = ansleft;
   res += mid;
   res += ansright;
   }
   //*/
   cout << "Case #" << case_no << ": " << res << endl;
}

int main() {
   FAST_IO;

int t;
   cin >> t;

for (int id = 1; id <= t; ++id) {
   solve(id);
   }
   
   return 0;
}

Unable to find the mistake in the code, please help.

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/42b9728b-7866-4551-826d-0195e2368bf0%40googlegroups.com.

[gcj] Commented Solutions for Round 1A - C++

[Matt Fenlon]

Check out the link below if you'd like to review solutions and explanations 
to the problem set from Round 1A. Writing the explanations felt a lot like 
reiterating the Analysis section of each problem, but it was helpful to 
restate them in my own words so that I could ensure that I understood the 
solutions. I might mix it up next time.
https://github.com/mfenlon/Google-Code-Jam-Archive-Solutions/tree/master/2020/r1a

-- 
You received this message because you are subscribed to the Google Groups 
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/google-code/846e7c4d-7c7b-4020-a381-e1da3f4ba575%40googlegroups.com.

[gcj] Re: Square Dance from Round 1A: Cannot figure out correct solution

[Bohdan Dovhan]

Can anyone suggest anything here?

понеділок, 13 квітня 2020 р. 19:07:56 UTC+3 користувач Bohdan Dovhan 
написав:
>
> During Round 1A I wasn't able to submit correct solution in time.
> When round finished, I have submitted solution which shown in Practice 
> Correct result for 3A and TLE for 3B.
>
> I read Analysis and wrote an "optimized" version but instead of receiving 
> both Correct results, I received TLE for 3A.
>
> Can anyone help to understand why optimized version written by solution 
> analysis guideline doesn't work?
>
> This is my code without optimisation
>
> import sys, copy;
> debug = False
> def pem(a):
> for i in range(len(a)):
> print  >> sys.stderr, ' '.join(map(str, a[i]))
> 
> def verify(r,c,i,j,s):
> if debug:
> print  >> sys.stderr, ' i ', i, ' j ', j
> 
> k = i-1
> comp = []
> while k >= 0:
> if s[k][j] > 0:
> comp.append(s[k][j])
> if debug:
> print  >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]- ', s[k
> ][j], ' comp ', comp
> break
> k-=1
> k = i+1
> while k < r:
> if s[k][j] > 0:
> comp.append(s[k][j])
> if debug:
> print  >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]+ ', s[k
> ][j], ' comp ', comp
> break
> k+=1
>
>
> l = j-1
> while l >= 0:
> if s[i][l] > 0:
> comp.append(s[i][l])
> if debug:
> print  >> sys.stderr, ' i ', i, ' l ', l, ' s[il]- ', s[i
> ][l], ' comp ', comp
> break
> l-=1
> l = j+1
> while l < c :
> if s[i][l] > 0:
> comp.append(s[i][l])
> if debug:
> print  >> sys.stderr, ' i ', i, ' l ', l, ' s[il]+ ', s[i
> ][l], ' comp ', comp
> break
> l+=1
> if debug:
> print  >> sys.stderr, ' #competitors ', len(comp)
> if len(comp) > 0:
> print  >> sys.stderr, ' average ', float(sum(comp))/len(comp)
> return False if len(comp) == 0 else float(sum(comp))/len(comp) > s[i][
> j]
> def solve(r,c,s):
> eliminationHappens = True
> su = 0
> while eliminationHappens:
> su += sum([sum(s[i]) for i in range(r)])
> eliminationHappens = False
> cop = copy.deepcopy(s)
> for i in range(r):
> for j in range(c):
> if s[i][j] > 0:
> if verify(r,c,i,j,cop):
> s[i][j] = 0
> eliminationHappens = True
> if debug:
> print  >> sys.stderr, 's ' 
> pem(s)
> return str(su);
>
>
> t = int(raw_input())
> for i in range(1, t + 1):
> r,c = map(int,raw_input().split())
> s = [map(int,raw_input().split()) for j in range(r)]
> print "Case #" + str(i) + ": " + solve(r,c,s)
>
>
>
> and this is the optimized version
>
> import sys, copy;
> debug = False
> def pem(a):
> for i in range(len(a)):
> print  >> sys.stderr, ' '.join(map(str, a[i]))
> def buildLinkedList(r,c,s):
> return [[buildLLI(r,c,i,j,s) for j in range(c)] for i in range(r)]
>  
> def buildLLI(r,c,i,j,s):
> upper = None
> lower = None
> left = None
> right = None
> k = i-1
> while k >= 0:
> if s[k][j] > 0:
> upper = {'x':k,'y':j,'s':s[k][j]}
> break
> k-=1
> k = i+1
> while k < r:
> if s[k][j] > 0:
> lower = {'x':k,'y':j,'s':s[k][j]}
> break
> k+=1
>
>
> l = j-1
> while l >= 0:
> if s[i][l] > 0:
> left = {'x':i,'y':l,'s':s[i][l]}
> break
> l-=1
> l = j+1
> while l < c :
> if s[i][l] > 0:
> right = {'x':i,'y':l,'s':s[i][l]}
> break
> l+=1
> return {'x':i,'y':j,'s':s[i][j],'u':upper,'lo':lower,'le':left,'r':
> right}
>
>
> def ver(item):
> dirs = ['u','lo','le','r']
> if debug:
> print  >> sys.stderr, ' item ', item, ' dirs ', [ d for d in dirs 
> if item[d]!=None]
> comps = [item[d]['s'] for d in dirs if item[d]!=None]
>
>
> return False if len(comps) == 0 else float(sum(comps))/len(comps) > 
> int(item['s'])
>  
> dirs = ['u','lo','le','r']
> def opp(d):
> return 'lo' if d == 'u' else 'u' if d == 'lo' else 'le' if d == 'r' 
> else 'r'
> def solve(r,c,s):
> ll = buildLinkedList(r,c,s)
> if debug:
> print  >> sys.stderr, ' ll ', ll
> su = sum([sum(s[i]) for i in range(r)])
> lost = [ll[i][j] for j in range(c) if ver(ll[i][j]) for i in range(r)]
> 
> while len(lost) > 0:
> check = []
> for l in lost:
> if debug:
> print  >> sys.stderr, ' l ', l
> print  >> sys.stderr, ' l[x] ', l['x'], ' l[y] ', l['y']
> 
> s[l['x']][l['y']] = 0
> ll[l['x']][l['y']] == None
> for d in dirs:
>