Solution to Codejam 2019's Pylons The 2019 Stack Overflow Developer Survey Results Are In ...
Does Parliament need to approve the new Brexit delay to 31 October 2019?
What information about me do stores get via my credit card?
What can I do if neighbor is blocking my solar panels intentionally?
Hiding Certain Lines on Table
Simulating Exploding Dice
Can smartphones with the same camera sensor have different image quality?
Can the prologue be the backstory of your main character?
I'm thinking of a number
Is there a writing software that you can sort scenes like slides in PowerPoint?
Semisimplicity of the category of coherent sheaves?
Does Parliament hold absolute power in the UK?
How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the colour of Green
The variadic template constructor of my class cannot modify my class members, why is that so?
Mortgage adviser recommends a longer term than necessary combined with overpayments
How to test the equality of two Pearson correlation coefficients computed from the same sample?
I could not break this equation. Please help me
does high air pressure throw off wheel balance?
When did F become S in typeography, and why?
Didn't get enough time to take a Coding Test - what to do now?
What is this lever in Argentinian toilets?
Road tyres vs "Street" tyres for charity ride on MTB Tandem
First use of “packing” as in carrying a gun
Windows 10: How to Lock (not sleep) laptop on lid close?
Relations between two reciprocal partial derivatives?
Solution to Codejam 2019's Pylons
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Make Depth First Search program more efficientSolution to Chef and Squares challenge, timing out in Java but not in C++Magic Trick (Google Code Jam 2014 QR Problem A) in PythonHackerrank: Prefix neighborsPiling Up with Python“Camera Purchase” challengeAccurate modular arithmetic with double precisionFinding non-self-intersecting paths of certain moves that touch all points in a gridCode to find the sums of building heightsProject Euler #11 Largest Product in a Grid | Cache-optimized + sliding window (C++14)
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$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
edited 29 mins ago
Jamal♦
30.6k11121227
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
$endgroup$
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
edited 29 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
edited 29 mins ago
Jamal♦
30.6k11121227
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
$endgroup$
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
python performance time-limit-exceeded
edited 29 mins ago
Jamal♦
30.6k11121227
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
edited 29 mins ago
Jamal♦
30.6k11121227
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
edited 29 mins ago
Jamal♦
30.6k11121227
edited 29 mins ago
Jamal♦
30.6k11121227
edited 29 mins ago
Jamal♦
30.6k11121227
30.6k11121227
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
asked 15 hours ago
Eugene YarmashEugene Yarmash
28329
28329
$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$
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
$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$
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$
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$
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
$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 Answer
1
active
oldest
votes
$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/
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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/
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/
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/
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$
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/
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
answered 9 hours ago
Shashank MishraShashank Mishra
1
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.
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.
Shashank Mishra is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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