Creating new topic as I did not find one for ‘OneWay City’ puzzle

For ‘Megapolis’ testcase - it says expected ‘Nothing’ - any clues?

Failure

Found: 3375715115287449357506276695064…726014538258316337554755849302820688331524472512613578509997274

Expected: Nothing

My complete answer is –

337571511528744935750627669506434248838060777255175561517910550780489905968124804562017354099174540336233599275767389009210547173333585270616695653031256733448728248255814658743274199733546547200929609258125133961382810722609225060931306661232015028185829053411607083130319808125013980911296374139939995694487720361335354009565632785551307253894009225188372943476261394613761332350053033862682544035976935437069175106904747221053997560780850398839559532570832402246987519140784907596916473540026727391887623344830748713701583693744640548995316198606772450647037362379871564404676147603823621817950447438749562574141967581742006067273505837938190967560305589910219367443065406884717487785297753203972355344791144609965850943893242914859682393583584237322257184059663888812648548161431523982244138189896876883838976859461836139273820266685132374047250047121319162282893506703805687463113881379834142982384933932956414272690604011859991068147260145382583163375547558493028206883315244725126135785099972748669810043228877657663817767007759059673835807071710260295225051495081120729539947185334438627246041122667578392885315441329242351579019799239611055127698776683811905726439448929400393492686072835975978331556420635681244311113778971903479219109204447752778760042970242690943088701054676733157964040374336380419946433197070597298525507419501582576927444773621069687613286374537763104395277366568727213888805305810728487448084490632468988788496928630068553319359005645356304547857608238105940006848219663045336405018805179712537119668639265938806139450551999054636425798500526622526220491394577665076161901065684538266031322751316909847595225741319522414421179486500114827894975354850999368425817062207498844223293227280868725129997893905372462734008320411481712411195021006219098977499531357504317571028655312072252551058508879741689810441385421373554638923818839923125315896225002615611698035617113627112683735816107892142388061674782251362407209266175573780371723893107276641826897592603034223054799026055306145489818335217023566454165323029695739174171336693785975950910220503129192740729334212461345005567846770853631274013283361138305068228856539134607180053427642992350255097543776456719057191335032877798382102920778332366953160032058488693593265163269693125758664320129420626574825205032528024316700339678813094963624707816987543732101089848875293249704648824902172175105762173717785901496508267931795529158519507925230840407485316788664260758361372335077899982705418252344896520000

RTFM…

“Actually, the numbers can get so big that your program’s output should only contain the first 1000 digits of the solution.”

So your answer is correct but you write just too much things, but i agree that this “expected: nothing” is annoying sometimes

Thanks Frankich - my bad - let me try and find the manual now.

[Edited] it works fine with 1000 limit!

I think there is an error in the description where it says (M) is the number of west-east *roads* and (N) is the number of north-south *roads*. Is it the number of roads? Or the number of buildings in that dimension of the grid? (M) west-east buildings is (M - 1) west-east roads.

The first test case is 4 x 4 with an expected result of 20 and, from what I can tell, 20 routes happens in a grid with 4 west-east *buildings* and 4 north-south *buildings*, not roads.

Either way, I’m having trouble figuring out the formula for this one. Any hints would be appreciated.

Update: I figured out the solution but I still think the description is incorrect.

So the minimum would be 2 roads east-west and two roads north-south. I think of that visually as a square - and there are two routes - either east or south. The example of 4x4 is a grid that is 4 lines across and 4 lines down (so, I think that’s like the 3x3 buildings concept you mention). I started by drawing it out and starting from the base case and building it up from there and that’s how I found the pattern I needed.

Oops - didn’t see you update when I replied

Ohhhh ok. I was thinking “roads” as in a grid dimension where a path between two buildings is one road. I see what they mean now.

I still think “buildings” is more accurate. Look at the 2nd test case of 7 by 1. There are not 7 north-south roads, there are zero.

I think it was 7 west-east roads and 1 north-south (doesn’t really matter though - it’s the same logic)

This quick attempt at a diagram might look like six different west to east roads - but it’s supposed to represent one long road. It could also be along the top instead of the bottom.

There’s only one route from the top left to the bottom right.

|**|**|**|**|**|**|

I agree that the first paragraph of explanation isn’t as clear as it could be.

Yeah you’re right it doesn’t matter which dimension is which, but let’s just say the 7x1 city is represented how the puzzle says, the diagram would be rotated vertically, with 7 roads going east-west, and one long road going north-south, which is essentially zero east-west roads, because what are the roads connecting? Nothing.

7 x 1 *buildings* on the other hand would be accurate. I’m being way too particular here, I know, lol

OK - I see what you’re saying.

I’m reading it differently, so I’ll change the scale to explain myself.

Imagine that there’s more than one building per road and it’s a big city/town.

I’ll represent each building with an X. And for the roads, I’ll use a line of R’s.

And I’ll just do it for a 3x1 (so the diagram isn’t huge).

X X X X X X X X X X

X RRRRRRRRRRR X

X R X X X X X X X X

X R X

X R X X X X X X X X

X RRRRRRRRRRR X

X R X X X X X X X X

X R X

X R X X X X X X X X

X RRRRRRRRRRR X

X X X X X X X X X X

Now, to get from the building in the top left to the building in the bottom right - there’s only one route.

Note, according to the rules, the roads are one-way, so on this example you can get from the ‘main road’ to any of the buildings, but you can’t get from the dead end of the one-way roads back to the main road.

Ok now you lost me. The first line of the puzzle is, “Your city is a rectangular grid of buildings with streets joining them vertically and horizontally.” That diagram is definitely not that.

You’re totally right. Sorry if I’ve confused you. I can’t seem to explain now how I made sense of it and came to the right solution so quickly. I guess I just abstracted it to a path problem and didn’t think about the buildings at all.

I am having a problem with OneWay City by Anst. I am able to get the first few test to pass but it fails on Conurbation and Megalopolis.

For Conurbation

I get

1400749509083708812240837853009143626989568

and it should be

1400749509083708812152608657850239525991600

Was anyone able to solve this problem correctly?

Yes, I solved it.

It’s very strange. At first I thought about overflow but in this case problem should have been with high digits.

My solution correctly pass all tests but in Megalopolis test it exceeds time limit and I have no idea how to improve the performance.

I did it! ))

Here is the beef of my code where I think I am having problems.

if (i > 0)

arr[i][j + 1] = arr[i][j] + arr[i - 1][j + 1];

// does the math for the next cell to the right by adding the current cell and the one on the top to the right of the current cell

I have two for loops that go through and create the outer rims so like for the 4x4 square the loop already has the ones when doing the if statement above.

1111

1

1

1