• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 08:58
CET 14:58
KST 22:58
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2310[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over4Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
No more SC2 streamers on team liquid? Team Liquid Map Contest #23 Weekly Cups (Nov 9-15): Clem and herO take over Dark completes military service, returns to SC2 StarCraft open world shooter announced at BlizzCon
Tourneys
soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
List of top players active on ShieldBattery Light introduces ShieldBattery on his YouTube BW General Discussion BGH Auto Balance -> http://bghmmr.eu/ NaDa's Body
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [Megathread] Daily Proleagues [BSL23] Ro16 Group D - Sunday 21:00 CET [BSL23] Ro16 Group B - Saturday 21:00 CET
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
The PlayStation 5 Stormgate/Frost Giant Megathread Warcraft III: The Frozen Throne Nintendo Switch Thread Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
The Big Programming Thread US Politics Mega-thread Trading/Investing Thread Artificial Intelligence Thread Russo-Ukrainian War Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Customize Sidebar...

Website Feedback

Closed Threads



Active: 12229 users

The Big Programming Thread - Page 885

Forum Index > General Forum
Post a Reply
Prev 1 883 884 885 886 887 1032 Next
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.
Acrofales
Profile Joined August 2010
Spain18502 Posts
May 31 2017 17:00 GMT
#17681
On June 01 2017 01:00 Hanh wrote:
What would an algorithmic solution be?


What the guys above you did.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 19:40:32
May 31 2017 19:38 GMT
#17682
Ok we've been given homework #1.

It is okay for me to post homeworks, and to discuss them. I figure you guys will probably find this fun so I am posting it, I'll post my attempt before I read any solutions.


Assume you have a necklace of stones. Some of the stones have positive value and some
have negative value. You have the opportunity to snip the necklace in two places (creating two
bands) and weld the endpoints of one of the two bands back into a necklace. You would like
your new necklace to be as valuable as possible. You can assume the necklace has n stones
with values v[0], v[1], . . . , v[n − 1].


ah, so we have a circular connecting necklace and you snip it in 2 places, using one of the new bands to make a new necklace


(a) Give an algorithm to find the value of the new necklace. If all of the stones have negative
value your answer should be 0. Make your algorithm as clean and elegant as possible.



(b) Give an algorithm to determine where you should snip the original necklace (not just its
value). Make your algorithm as clean and elegant as possible. If all of the values are
positive you should not snip and your algorithm should print:
Do not snip.
If all of the values are negative you should not snip and your algorithm should print:
Throw necklace away.
If possible the algorithm should determine these two situations without explicitly checking
for them.

CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
Last Edited: 2017-05-31 19:50:55
May 31 2017 19:49 GMT
#17683
What the heck kind of homework question is that lol. My eyes glaze over trying to read the paragraphs. Sounds like a pretty hard problem. Looks like a linked list, or an array kind of problem. Linked list would probably be the easiest to write code for.

"Some have positive, some have negative", why can't we say signed integers? It's just signed integers.

It sounds like one of those "maximal subset" problems. I hate those problems man. Actually this problem here is my least favorite programming question I have ever heard, and sounds pretty similar to yours.

Edit: When it says clean and elegant, what do those terms even mean. Those are really subjective terms. It sort of sounds like "try to find the trick that makes this problem easy to solve", like the trick in the wikipedia page.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
May 31 2017 19:57 GMT
#17684
When he says clean and elegant I imagine he is hinting that there is at least one efficient solution that will not be super complicated, and he wants that solution.

I think that interestingly enough this question is almost the opposite of question 1 of the 3 questions I posted back a little bit ago.

For the sake of familiarity I would view the necklace as a circular array (just "decide" that the ends connect)
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-05-31 20:07:10
May 31 2017 20:05 GMT
#17685
Overcomplicating it a bit, the problem simply boils down to the maximum subarray problem.

Of course, part of the course is learning how to decipher word problems.
There is no one like you in the universe.
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2017-05-31 20:14:16
May 31 2017 20:05 GMT
#17686
Sounds like dynamic programming to me. Did you learn dynamic programming yet?

E: re Blisse
+ Show Spoiler +

Yeah. That. Just have to make sure you copy the values twice, so you get the fact that the first and last element are connected. Alternatively you could loop an extra time at the end until your previous value is greater or equal to the newest one.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 20:23:18
May 31 2017 20:21 GMT
#17687
It isn't the same problem though, I think. I haven't started it yet but I think for this one we actually need to find the minimum subarray. Finding the maximum could give us an incorrect result.

For example if our necklace is:

5 7 -2 5 -2
and then we return back the whole necklace - we are wrong. (or if you don't like this example, replace with much bigger more complicated examples)


I know of dynamic programming but I haven't really done much of it in practice. I think I will be okay though since I know the premise behind it.
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
May 31 2017 20:29 GMT
#17688
What's wrong with returning the whole array?
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
May 31 2017 20:32 GMT
#17689
in the example above the correct answer would be to remove an instance of negative 2 and return everything else, ie: 5 7 5 -2
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
Last Edited: 2017-05-31 20:35:42
May 31 2017 20:34 GMT
#17690
Minimum subarray means lowest value, so -2. Maximum means 5 7 -2 5, for value of 15 (like you correctly pointed out).
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2017-05-31 20:39:51
May 31 2017 20:38 GMT
#17691
On June 01 2017 05:29 CecilSunkure wrote:
What's wrong with returning the whole array?

In that example? It doesn't maximize the value. By just returning [5, 7] you get a value of 12. If you add negative values, your value isn't maximal.

@Travis: you don't want a minimal length. You don't want maximal length. You want maximal value, which is what blisse's link describes.

E: I read -5 for the second 5 :p. But even so you don't want to return the whole array
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 20:46:18
May 31 2017 20:43 GMT
#17692
I didn't actually realize he had posted a link, it seems to be the exact same color as normal text for me. I thought he was referring to a problem I had posted yesterday.

Which, actually is that problem. But making it circular changes it a bit.

I know we don't want maximal or minimal length, but I am now seeing there really is no difference between looking for minimum subarray or looking for maximum subarray.
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
May 31 2017 20:44 GMT
#17693
Yep that's right, maximum and minimum subarrays can have any length, because the values are what determine max/min, not the element indices or how many elements the subarray has.

And yeah... TL links seem to have lost their luster. It's impossible to see them.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 20:59:09
May 31 2017 20:53 GMT
#17694
okay now that I am actually working on this it is a bit harder than what I thought it was.

I don't think Blisse's link does it justice - the trouble for me is in handling that it is circular.

edit: I looked up an answer and it's really cute - you guys were underselling this problem

a hint is that my intuition was right that I needed to find the maximum negative subarray, but there is more to it than that.
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
May 31 2017 21:37 GMT
#17695
lol well i'm glad you're enjoying it. You model student you
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2017-05-31 23:02:58
May 31 2017 21:54 GMT
#17696
Pretty sure you can solve it just fine as follows:

+ Show Spoiler +


neckarray = 2*necklace

maxstart = 0
maxend = 0
maxval = 0

tempstart = 0
tempval = 0

for index, value in neckarray:
tempval = max(value, tempval + value);
if tempval == value:
tempstart = index

maxval = max(tempval, maxval)
if maxval == tempval:
maxstart = tempstart
maxend = index +1

if maxend - maxstart > len(necklace):
print "Don't cut"
elif maxval == 0:
print "Trash"
else:
maxend = maxend%len(necklace)
maxstart = maxstart%len(necklace)
print("cut at", maxstart, maxend, "for a necklace with value", maxval)

Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 22:19:45
May 31 2017 22:14 GMT
#17697
edit2:

I don't know what language that is, but I am guessing what you are doing is

1.) make an array that repeats the original array once
2.) find the maximum continuous subarray.
3.) if the maximum continuous subarray is greater in length than the original array, don't cut

{5, 5, -1, 5, -1, 5} would return "don't cut", which would be wrong because the correct answer would remove an instance of -1
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-05-31 22:43:40
May 31 2017 22:39 GMT
#17698
@travis, haven't walked through, but arcofales's code repeats the original array twice, and performs the maximal subarray code on that repeated array.

Seems to be missing a check to ensure that the selected maximum subarray is only of length N though.

edit: oo, neat lol
There is no one like you in the universe.
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2017-05-31 22:44:50
May 31 2017 22:40 GMT
#17699
On June 01 2017 07:14 travis wrote:
edit2:

I don't know what language that is, but I am guessing what you are doing is

1.) make an array that repeats the original array once
2.) find the maximum continuous subarray.
3.) if the maximum continuous subarray is greater in length than the original array, don't cut

{5, 5, -1, 5, -1, 5} would return "don't cut", which would be wrong because the correct answer would remove an instance of -1


It is pseudopython. Mostly python, but too lazy to make it properly. And yeah, completely interested code.

Unless I made a mistake somewhere, it'd return 5, 4 as the start and end for your cut, which is what you'd want. The loop would end with 5, 10 as the maxstart, maxend. Those would then be adjusted (just the maxend in this case) to not be greater than the necklace's length.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 23:01:11
May 31 2017 22:58 GMT
#17700
Can you explain why it would return 5, 10 as max start and end instead of 0, 10 ?

I thought I had a clue reading that code but maybe I don't, lol
Prev 1 883 884 885 886 887 1032 Next
Please log in or register to reply.
Live Events Refresh
GSL
20:30
GSL CK 7
IntoTheiNu 990
Maru 148
SHIN 111
CranKy Ducklings SOOP102
Classic 67
Zoun (SOOP) 65
ByuN (SOOP) 57
Solar (SOOP)34
Rex19
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
OGKoka 208
Maru 148
ProTech144
LamboSC2 124
SHIN 111
Classic 67
Zoun (SOOP) 65
ByuN (SOOP) 57
Solar (SOOP) 34
Rex 19
TKL 2
StarCraft: Brood War
Britney 33891
Shuttle 2497
EffOrt 922
BeSt 681
Light 517
Larva 402
Rush 402
FanTaSy 314
Snow 204
Stork 203
[ Show more ]
ggaemo 191
Mini 189
Hyuk 188
Last 154
Leta 137
hero 118
Mind 99
Zeus 92
Sea.KH 61
Pusan 48
Barracks 44
Movie 44
sorry 42
ToSsGirL 38
Sharp 37
Sacsri 20
zelot 18
Terrorterran 17
910 14
ajuk12(nOOB) 11
Free 11
sOs 10
Icarus 8
Dota 2
Gorgc4862
qojqva2029
Dendi895
XaKoH 346
BananaSlamJamma322
420jenkins212
syndereN23
League of Legends
Reynor103
Counter-Strike
jkaem94
Heroes of the Storm
crisheroes273
Trikslyr32
Other Games
singsing3886
B2W.Neo982
olofmeister492
hiko451
Lowko393
Fuzer 119
DeMusliM57
ArmadaUGS37
QueenE26
[ Show 11 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• iopq 3
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV552
League of Legends
• TFBlade506
Upcoming Events
Patches Events
2m
OSC
2h 2m
Replay Cast
9h 2m
KCM Race Survival
20h 2m
Ultimate Battle
22h 2m
ZerO vs Bisu
RSL Revival
1d 21h
BSL
2 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
2 days
IPSL
3 days
Ret vs ggnore13
nOmaD vs Aether
BSL
3 days
Bonyth vs Doodle
Kyrie vs Jimin
[ Show More ]
Replay Cast
3 days
WardiTV Weekly
3 days
Kung Fu Cup
4 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
5 days
The PondCast
6 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.