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)

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



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;








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()









share|improve this question











$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

















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()









share|improve this question











$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













1












1








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()









share|improve this question











$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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 15 mins ago









Jamal

30.6k11121227




30.6k11121227










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
















  • $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










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








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$













    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


















    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









    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








    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$

















      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








      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$















        0












        0








        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








        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/







        share|improve this answer








        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.









        share|improve this answer



        share|improve this answer






        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




        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.



























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

            Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

            Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar