• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 09:08
CET 15:08
KST 23:08
  • 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 #235[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 over2Dark 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
Dark completes military service, returns to SC2 Weekly Cups (Nov 9-15): Clem and herO take over Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon No more SC2 streamers on team liquid?
Tourneys
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) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
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 BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion 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
Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads The PlayStation 5
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
US Politics Mega-thread Trading/Investing Thread Artificial Intelligence Thread Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
TeamLiquid Health and Fitness Initiative For 2023 Football (Soccer) Thread
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
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 10042 users

The Big Programming Thread - Page 886

Forum Index > General Forum
Post a Reply
Prev 1 884 885 886 887 888 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 23:18 GMT
#17701
On June 01 2017 07:58 travis wrote:
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

No, you're right. It's not as trivially reduceable to the maximum congruent subarray problem as I thought. The fact that it's circular allows you to do stuff that cannot simply be replicated by making repeating the array. I guess to use this approach, you'd have to simultaneously find the longest stretch you can within your current subarray with a value less or equal to 0. And then do some magic at the end, if necessary.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
May 31 2017 23:23 GMT
#17702
If you want to spoil an elegant solution for yourself, I expect you will enjoy it's simplicity like I did

http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
May 31 2017 23:26 GMT
#17703
I don't understand that solution *at all*, anyone have an explanation?
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-05-31 23:39:26
May 31 2017 23:35 GMT
#17704
The solution covers 2 cases. The first case is that we can use the normal algorithm (the one blisse linked). We can use this algorithm if we don't have to worry about "wrapping around" our circular array.

A couple examples of that are {5, 5, 5} or {-3, 7, 8, 9} or {-2, 6, 3, -1, 7, -5}

In all of those we do not need to wrap to find our subarray. We now have a way to handle this case, so we can include it in our code - we don't need to worry about it anymore.


However there are cases where we do need to wrap around to find our subarray. Examples could be: {7, -2, 7 } or {1, 2, 3, 4, -5, 6, 7 } etc. These are cases where we need to remove negative stuff from the inside but still use both the ends of the array (since if it was a real necklace the end would connect to the beginning).

For those cases we know we have positive elements on the ends, because it is wrapping. So, we know that the subarray that we are removing is NOT wrapping - it's inside the array - not on the ends.
Because we know the subarray to be removed is inside, we can make all our positives negative, and all our negatives positive.

Then we find the greatest sum with this new array, which is actually the part to be removed because the signs were flipped. So our "start position" will be at the end of this subarray(the one that has the part we need to remove), and our "end position" will be just before it begins.


To cover both cases we need to run both algorithms in our code, and compare to see which gives us the greater sum - and that is the one that we will use.
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
Last Edited: 2017-05-31 23:40:00
May 31 2017 23:39 GMT
#17705
Aahh so the trick is flipping the sign bit so that one loop through will get a max value. But you will also have to solve problem where you find "snip points", so that will add a little more complexity.

E: These kind of tricky problems are frustrating. Good job working through it man
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-05-31 23:45:56
May 31 2017 23:45 GMT
#17706
Sorry, I don't understand why running my originally suggested algorithm with the array 2x and max N wouldn't work.

Changing {7, -2, 7} to {7, -2, 7, 7, -2, 7} would get you the maximum sequence {7, 7}.
Changing {1, 2, 3, 4, -5, 6, 7 } to {1, 2, 3, 4, -5, 6, 7, 1, 2, 3, 4, -5, 6, 7 } would get you the maximum sequence {6, 7, 1, 2, 3, 4}.
There is no one like you in the universe.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
May 31 2017 23:51 GMT
#17707
In both of those cases the maximum sequence would be the full 2x arrays. {7, -2, 7, 7, -2, 7} has a higher value than {7, 7}
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
Last Edited: 2017-05-31 23:52:43
May 31 2017 23:52 GMT
#17708
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-05-31 23:54:16
May 31 2017 23:53 GMT
#17709
On June 01 2017 08:51 travis wrote:
In both of those cases the maximum sequence would be the full 2x arrays. {7, -2, 7, 7, -2, 7} has a higher value than {7, 7}


> ... with the array 2x and max N wouldn't work.

Should've specified max length N, oops.
There is no one like you in the universe.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-06-01 00:10:32
May 31 2017 23:58 GMT
#17710
edit: actually let me make sure I know what I am saying is correct

edit2: My brain is starting to get a bit worn out so I can't prove it but I think you lose linear time efficiency by doing what you are saying. I think that every time you reach "n" length subarray you would have to start over, 1 index from where you started last time, over and over again.
Well I guess there might be other ways but it definitely isn't simple


and if you tried to do it using the algorithm you originally posted, you would have to "snip" the subarray it found to shorten it to N length, which would mean you would have to go through all the N-length subarrays within the subarray that it found
Acrofales
Profile Joined August 2010
Spain18502 Posts
Last Edited: 2017-06-01 06:58:45
June 01 2017 06:58 GMT
#17711
On June 01 2017 08:23 travis wrote:
If you want to spoil an elegant solution for yourself, I expect you will enjoy it's simplicity like I did

http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Yup. More elegant by far than trying to deal with the wrap-around case by snipping out the middle, although it's essentially the same algorithm. It just looks neater that way
dsyxelic
Profile Joined May 2010
United States1417 Posts
Last Edited: 2017-06-02 04:13:01
June 02 2017 04:11 GMT
#17712
so after taking a break from that really weird c project I brought up in this thread a while ago, I've been working on it all day today to figure out the kinks before the due date tomorrow at midnight

I managed to finish it just now and wow it was pretty frustrating

so basically what I did originally was for the most part fine, it's just that the mips simulator completely bugs out unless I follow some rules:

1) has to be in that old C style the professor used. I rewrote my code according to how he wrote his code
2) must define empty __main() function since the simulator calls for it and gives an error if it's not defined
3) must define empty dummy function and call it in each function I am using pointers to access the stack
4) cannot use printf, must use a separate string printing function the professor defined
5) when compiling it into the needed .s file the .c file used must be the same as the .s file. (did not know this and took hours)

also had to change frame pointer along with return address

if people are still interested in the final code I'll post tomorrow after the due date since I'd rather not chance (albeit hilariously small) someone comes across and copies it before the due date. or PM ing is fine

it's basically what I posted before with all those rules followed above. just save the address of the return address and frame pointer in the setjmp function and have the return address and frame pointer in longjmp function be changed to that of the one from setjmp. doesn't work when I write it like how modern human beings write C code. only in that archaic form does it work in the simulator. top 5 stupidest assignments i've had so far in my life not because of the content but because of the horrible guidelines and directions. And so much effort needed for trying to teach something rather simple.
TL/SKT
Manit0u
Profile Blog Joined August 2004
Poland17875 Posts
June 02 2017 07:04 GMT
#17713
On June 02 2017 13:11 dsyxelic wrote:
so after taking a break from that really weird c project I brought up in this thread a while ago, I've been working on it all day today to figure out the kinks before the due date tomorrow at midnight

I managed to finish it just now and wow it was pretty frustrating

so basically what I did originally was for the most part fine, it's just that the mips simulator completely bugs out unless I follow some rules:

1) has to be in that old C style the professor used. I rewrote my code according to how he wrote his code
2) must define empty __main() function since the simulator calls for it and gives an error if it's not defined
3) must define empty dummy function and call it in each function I am using pointers to access the stack
4) cannot use printf, must use a separate string printing function the professor defined
5) when compiling it into the needed .s file the .c file used must be the same as the .s file. (did not know this and took hours)

also had to change frame pointer along with return address

if people are still interested in the final code I'll post tomorrow after the due date since I'd rather not chance (albeit hilariously small) someone comes across and copies it before the due date. or PM ing is fine

it's basically what I posted before with all those rules followed above. just save the address of the return address and frame pointer in the setjmp function and have the return address and frame pointer in longjmp function be changed to that of the one from setjmp. doesn't work when I write it like how modern human beings write C code. only in that archaic form does it work in the simulator. top 5 stupidest assignments i've had so far in my life not because of the content but because of the horrible guidelines and directions. And so much effort needed for trying to teach something rather simple.


Wow...

What class is that? C? Embedded systems?

Also, to anyone familiar with mips: do you really have to use old syntax for it and some non-standard functions or is it just this weird simulator that enforces this?

Super weird assignment. I feel your pain and am glad you made it work.
Time is precious. Waste it wisely.
CecilSunkure
Profile Blog Joined May 2010
United States2829 Posts
June 02 2017 07:08 GMT
#17714
I'll take a look! I write C/C++ professionally so I'd be pretty interested in peeking.
Nesserev
Profile Blog Joined January 2011
Belgium2760 Posts
Last Edited: 2017-06-02 08:13:22
June 02 2017 07:58 GMT
#17715
--- Nuked ---
dsyxelic
Profile Joined May 2010
United States1417 Posts
Last Edited: 2017-06-02 21:02:59
June 02 2017 14:06 GMT
#17716
Yup nesserev got it. Thats the book we use and thats what the class is called. I agree hand writing this in assembly would have taught the same thing with less trouble.

@cecil ill pm you after work! Or just post here since its due around then anyways.

And respect to those who work in c, this language hurts me

edit:

here's the code

+ Show Spoiler +

int *ra; //return address
int *fp; //frame pointer
main()
{
int r;
r = setjmp(r);
if(r==0)
{
fun1();
return(0);
}
else
{
print_str("error\n");
return(2);
}
}
__main()
{
return(0);
}
dummy(v)
int v;
{
return(0);
}
setjmp(v)
int v;
{
int *p = &v;
ra = *(p-1);
fp = *(p-2);
dummy(v);
return(0);
}
longjmp(v)
int v;
{
int *p;
p = &v;
*(p-1) = ra;
*(p-2) = fp;
dummy(v);
return(1);
}
fun1()
{
print_str("start fun1\n");
fun2();
return(0);
}
fun2()
{
int d;
print_str("start fun2\n");
longjmp(d);
return(0);
}
print_str(str)
char *str;
{
int code;
code = 4;
asm(
"add $a0, %1, $zero\n\t"
"add $v0, %0, $zero\n\t"
"syscall"
:
: "r" (code), "r" (str));
return(0);
}
//output is:
//start fun1
//start fun2
//error
TL/SKT
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-06-03 16:27:46
June 03 2017 16:25 GMT
#17717
I was wondering if any of you could glance over my homework solutions for this week's "NP-Completeness" homework. It's really short - but I haven't done stuff quite like this and I am liable to screw it up (and some of it is a bit confusing for me)

Here is a link to the homework
http://www.cs.umd.edu/class/summer2017/cmsc351/hwk-np.pdf

this week we do only part 1 - sorting
so the questions I am wanting checked over is questions 2 and questions 3 of part 1

here are my solutions

http://www.filedropper.com/scan0001_2

(I had to click to download it twice before it actually downloaded it)

If you can't tell - my answer for 3a was to "put all the elements of all lists into a linked list" - or I guess that if they already were linked lists (it's not specific) - then link them all together.


note: if you are worried about helping me "cheat", it's not like that for this class. We can work together and review each other's stuff, we just need to write our solutions ourselves. Also, 87% of our grade is our one midterm and final so homework doesn't matter too much. I mostly just care about it so I will be better on the 2 exams.
Nesserev
Profile Blog Joined January 2011
Belgium2760 Posts
June 03 2017 17:38 GMT
#17718
--- Nuked ---
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-06-03 18:13:41
June 03 2017 18:09 GMT
#17719
On June 04 2017 02:38 Nesserev wrote:
Show nested quote +
On June 04 2017 01:25 travis wrote:
I was wondering if any of you could glance over my homework solutions for this week's "NP-Completeness" homework. It's really short - but I haven't done stuff quite like this and I am liable to screw it up (and some of it is a bit confusing for me)

Here is a link to the homework
http://www.cs.umd.edu/class/summer2017/cmsc351/hwk-np.pdf

this week we do only part 1 - sorting
so the questions I am wanting checked over is questions 2 and questions 3 of part 1

here are my solutions

http://www.filedropper.com/scan0001_2

(I had to click to download it twice before it actually downloaded it)

If you can't tell - my answer for 3a was to "put all the elements of all lists into a linked list" - or I guess that if they already were linked lists (it's not specific) - then link them all together.


note: if you are worried about helping me "cheat", it's not like that for this class. We can work together and review each other's stuff, we just need to write our solutions ourselves. Also, 87% of our grade is our one midterm and final so homework doesn't matter too much. I mostly just care about it so I will be better on the 2 exams.

Your answers for 2 are correct, but you seem to leave out some steps, which is annoying.

In 3a, you seem to have missed that you're also supposed to split that big list back up into all those separate lists afterwards in linear time. How will you do that?

The answer 3a will affect your answers for 3b, 3c and 3d, because you have to add the preprocessing and postprocessing times.


Hmm ok, I will be more meticiulous about 2.
As for 3 - are you sure I need to do that? I guess that does make sense, but it doesn't explicitly say it.

As for how I would do it - I honestly have no idea. That sounds impossible. I could separate it into lists of the original sizes, but the elements would be all wrong for each list.

Did the math for what I actually did look correct?

Thank you btw, appreciate your time.


edit: oh quick note, the homework says: "In order to get exact results, for the remaining problems in this section, ignore the cost of preparing the lists for input into the sorting package or processing the results (assuming those costs are within reason)."
Nesserev
Profile Blog Joined January 2011
Belgium2760 Posts
Last Edited: 2017-06-03 18:30:30
June 03 2017 18:29 GMT
#17720
--- Nuked ---
Prev 1 884 885 886 887 888 1032 Next
Please log in or register to reply.
Live Events Refresh
Next event in 1h 52m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
TKL 169
ProTech132
Codebar 35
StarCraft: Brood War
Britney 49433
Calm 5158
Bisu 2142
Horang2 818
Light 578
EffOrt 506
Larva 449
actioN 245
Stork 236
Rush 212
[ Show more ]
ggaemo 170
hero 155
Soulkey 128
firebathero 115
Mind 101
Barracks 84
Pusan 69
Last 68
PianO 61
ToSsGirL 34
Killer 24
Sharp 24
Classic 23
soO 22
sorry 19
Shinee 18
zelot 18
Movie 17
Hm[arnc] 16
910 14
sOs 13
ajuk12(nOOB) 11
Rock 9
Icarus 6
Terrorterran 6
Dota 2
Gorgc6483
Dendi986
XcaliburYe104
syndereN94
Counter-Strike
olofmeister927
byalli668
markeloff83
jkaem80
Heroes of the Storm
crisheroes280
Trikslyr42
Other Games
singsing1577
B2W.Neo830
Lowko290
RotterdaM222
mouzStarbuck89
Chillindude10
Liquid`RaSZi0
[ Show 11 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• ChaeLyn 8
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• TFBlade703
Other Games
• WagamamaTV113
Upcoming Events
OSC
1h 52m
Replay Cast
8h 52m
University League
19h 52m
GSL
21h 22m
Maru vs Dark
Patches Events
23h 52m
OSC
1d 1h
Replay Cast
1d 8h
KCM Race Survival
1d 19h
Ultimate Battle
1d 21h
ZerO vs Bisu
RSL Revival
2 days
[ Show More ]
BSL
3 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
3 days
IPSL
4 days
Ret vs ggnore13
nOmaD vs Aether
BSL
4 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
4 days
WardiTV Weekly
4 days
Kung Fu Cup
5 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
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.