Ttykuu

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

How do you keep chess fun when your opponent constantly beats you?

Working through the single responsibility principle (SRP) in Python when calls are expensive

What's the point in a preamp?

does high air pressure throw off wheel balance?

Wall plug outlet change

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

Why can't devices on different VLANs, but on the same subnet, communicate?

Wolves and sheep

Do working physicists consider Newtonian mechanics to be "falsified"?

Can the prologue be the backstory of your main character?

Sort a list of pairs representing an acyclic, partial automorphism

What aspect of planet Earth must be changed to prevent the industrial revolution?

Reference for the teaching of not-self

The following signatures were invalid: EXPKEYSIG 1397BC53640DB551

How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the colour of Green

Road tyres vs "Street" tyres for charity ride on MTB Tandem

Are my PIs rude or am I just being too sensitive?

What are these Gizmos at Izaña Atmospheric Research Center in Spain?

Semisimplicity of the category of coherent sheaves?

First use of “packing” as in carrying a gun

Windows 10: How to Lock (not sleep) laptop on lid close?

Does Parliament hold absolute power in the UK?

Who or what is the being for whom Being is a question for Heidegger?

Solution to Codejam 2019's Pylons

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

1

$begingroup$

I'm trying to solve Pylons from the 2019's round 1A. The analysis suggests that a brute force approach should work. However, my Python 3 solution doesn't pass the 2nd test case. Can I make it faster without complicating the algorithm?

from itertools import repeat, product


def main():
 T = int(input()) # the number of test cases

 for case in range(1, T+1):
 R, C = map(int, input().split()) # the numbers of rows and columns

 grid = [[False]*C for _ in repeat(None, R)]
 stack = []

 for r, c in product(range(R), range(C)):
 g = [row.copy() for row in grid]
 g[r][c] = True
 stack.append((r, c, g, (' '.format(r+1, c+1),)))

 while stack:
 r, c, g, h = stack.pop()
 if len(h) == R*C:
 print('Case #: POSSIBLE'.format(case), *h, sep='n')
 break

 for row, col in product(range(R), range(C)):
 if not g[row][col] and row != r and col != c and r - c != row - col and r + c != row + col:
 g2 = [x.copy() for x in g]
 g2[row][col] = True
 stack.append((row, col, g2, h+(' '.format(row+1, col+1),)))
 else:
 print('Case #: IMPOSSIBLE'.format(case))


main()

python performance time-limit-exceeded

share|improve this question

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you share a link to the analysis you've mentioned? I have a strong doubts that the brute force may work. Meanwhile, the problem looks like a knight tour variation with an ability to make non-knight moves. Use Warnsdorff's rule, and break the dead ends with non-knight moves.
  $endgroup$
  – vnp
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Just follow the link and open the 'ANALYSIS' tab.
  $endgroup$
  – Eugene Yarmash
  10 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There is nothing about the brute force there. The do however mention the knight tour (I honestly didn't read that tab when making the above comment).
  $endgroup$
  – vnp
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you add a title that explains what the task is? This way reviewers can get some context.
  $endgroup$
  – 422_unprocessable_entity
  8 hours ago
  

  
  
  
  

add a comment | 

1

$begingroup$

I'm trying to solve Pylons from the 2019's round 1A. The analysis suggests that a brute force approach should work. However, my Python 3 solution doesn't pass the 2nd test case. Can I make it faster without complicating the algorithm?

from itertools import repeat, product


def main():
 T = int(input()) # the number of test cases

 for case in range(1, T+1):
 R, C = map(int, input().split()) # the numbers of rows and columns

 grid = [[False]*C for _ in repeat(None, R)]
 stack = []

 for r, c in product(range(R), range(C)):
 g = [row.copy() for row in grid]
 g[r][c] = True
 stack.append((r, c, g, (' '.format(r+1, c+1),)))

 while stack:
 r, c, g, h = stack.pop()
 if len(h) == R*C:
 print('Case #: POSSIBLE'.format(case), *h, sep='n')
 break

 for row, col in product(range(R), range(C)):
 if not g[row][col] and row != r and col != c and r - c != row - col and r + c != row + col:
 g2 = [x.copy() for x in g]
 g2[row][col] = True
 stack.append((row, col, g2, h+(' '.format(row+1, col+1),)))
 else:
 print('Case #: IMPOSSIBLE'.format(case))


main()

python performance time-limit-exceeded

share|improve this question

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you share a link to the analysis you've mentioned? I have a strong doubts that the brute force may work. Meanwhile, the problem looks like a knight tour variation with an ability to make non-knight moves. Use Warnsdorff's rule, and break the dead ends with non-knight moves.
  $endgroup$
  – vnp
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Just follow the link and open the 'ANALYSIS' tab.
  $endgroup$
  – Eugene Yarmash
  10 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There is nothing about the brute force there. The do however mention the knight tour (I honestly didn't read that tab when making the above comment).
  $endgroup$
  – vnp
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you add a title that explains what the task is? This way reviewers can get some context.
  $endgroup$
  – 422_unprocessable_entity
  8 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

I'm trying to solve Pylons from the 2019's round 1A. The analysis suggests that a brute force approach should work. However, my Python 3 solution doesn't pass the 2nd test case. Can I make it faster without complicating the algorithm?

from itertools import repeat, product


def main():
 T = int(input()) # the number of test cases

 for case in range(1, T+1):
 R, C = map(int, input().split()) # the numbers of rows and columns

 grid = [[False]*C for _ in repeat(None, R)]
 stack = []

 for r, c in product(range(R), range(C)):
 g = [row.copy() for row in grid]
 g[r][c] = True
 stack.append((r, c, g, (' '.format(r+1, c+1),)))

 while stack:
 r, c, g, h = stack.pop()
 if len(h) == R*C:
 print('Case #: POSSIBLE'.format(case), *h, sep='n')
 break

 for row, col in product(range(R), range(C)):
 if not g[row][col] and row != r and col != c and r - c != row - col and r + c != row + col:
 g2 = [x.copy() for x in g]
 g2[row][col] = True
 stack.append((row, col, g2, h+(' '.format(row+1, col+1),)))
 else:
 print('Case #: IMPOSSIBLE'.format(case))


main()

python performance time-limit-exceeded

share|improve this question

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

$endgroup$

from itertools import repeat, product


def main():
 T = int(input()) # the number of test cases

 for case in range(1, T+1):
 R, C = map(int, input().split()) # the numbers of rows and columns

 grid = [[False]*C for _ in repeat(None, R)]
 stack = []

 for r, c in product(range(R), range(C)):
 g = [row.copy() for row in grid]
 g[r][c] = True
 stack.append((r, c, g, (' '.format(r+1, c+1),)))

 while stack:
 r, c, g, h = stack.pop()
 if len(h) == R*C:
 print('Case #: POSSIBLE'.format(case), *h, sep='n')
 break

 for row, col in product(range(R), range(C)):
 if not g[row][col] and row != r and col != c and r - c != row - col and r + c != row + col:
 g2 = [x.copy() for x in g]
 g2[row][col] = True
 stack.append((row, col, g2, h+(' '.format(row+1, col+1),)))
 else:
 print('Case #: IMPOSSIBLE'.format(case))


main()

share|improve this question

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

share|improve this question

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

edited 15 mins ago

Jamal♦

30.6k11121227

edited 15 mins ago

Jamal♦

30.6k11121227

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

asked 15 hours ago

Eugene YarmashEugene Yarmash

28329

1 Answer
1

active

oldest

votes

0

$begingroup$

pylon can be solved in two ways. O(r*c) make 2*n,3*n split few case will fail have to hard code them in my case 4*4,4*6,6*4,6*6 https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round1a-pylon/

another way is to use dfs and backtracks for depth r*c https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round-1a-pylon-dfs-and-backtracking-approach/

share|improve this answer

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');

var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);

;
$window.on('scroll', onScroll);

);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217398%2fsolution-to-codejam-2019s-pylons%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

pylon can be solved in two ways. O(r*c) make 2*n,3*n split few case will fail have to hard code them in my case 4*4,4*6,6*4,6*6 https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round1a-pylon/

another way is to use dfs and backtracks for depth r*c https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round-1a-pylon-dfs-and-backtracking-approach/

share|improve this answer

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

0

$begingroup$

pylon can be solved in two ways. O(r*c) make 2*n,3*n split few case will fail have to hard code them in my case 4*4,4*6,6*4,6*6 https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round1a-pylon/

another way is to use dfs and backtracks for depth r*c https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round-1a-pylon-dfs-and-backtracking-approach/

share|improve this answer

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

pylon can be solved in two ways. O(r*c) make 2*n,3*n split few case will fail have to hard code them in my case 4*4,4*6,6*4,6*6 https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round1a-pylon/

another way is to use dfs and backtracks for depth r*c https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round-1a-pylon-dfs-and-backtracking-approach/

share|improve this answer

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this answer

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 9 hours ago

Shashank MishraShashank Mishra

1

New contributor

Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 9 hours ago

Shashank MishraShashank Mishra

1