• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 06:09
CEST 12:09
KST 19:09
  • 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
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall11HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles7[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL78
StarCraft 2
General
RSL Revival patreon money discussion thread The GOAT ranking of GOAT rankings Weekly Cups (June 30 - July 6): Classic Doubles Server Blocker RSL Season 1 - Final Week
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo) $25,000 Streamerzone StarCraft Pro Series announced
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ Flash Announces Hiatus From ASL [ASL19] Finals Recap: Standing Tall BW General Discussion A cwal.gg Extension - Easily keep track of anyone
Tourneys
[Megathread] Daily Proleagues 2025 ACS Season 2 Qualifier Small VOD Thread 2.0 Last Minute Live-Report Thread Resource!
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Russo-Ukrainian War Thread US Politics Mega-thread Things Aren’t Peaceful in Palestine The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 776 users

The Big Programming Thread - Page 860

Forum Index > General Forum
Post a Reply
Prev 1 858 859 860 861 862 1031 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.
Nesserev
Profile Blog Joined January 2011
Belgium2760 Posts
March 10 2017 19:52 GMT
#17181
--- Nuked ---
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-03-10 20:40:39
March 10 2017 20:16 GMT
#17182
Haha, I'm glad people enjoyed that question. It was memorable to me because I was annoyed about the time limit as well when I was doing it the first time and didn't finish.

In hindsight I think it's a good question: it has a lot of pretty straightforward coding sections like palindrome, lends itself well to breaking down into parts, has lots of areas for optimizations, and then the short time limit adds a nice intensity given I think most people could find an okay solution in 30 minutes.

This takes me 4 minutes to code, but I have the advantage of knowing the question and my previous attempt :p

mfw trying to read slmw's O(n) solution... lol

+ Show Spoiler +

bool is_palindrome(string s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}

int longest_palindrome(vector<string> text) {
int max_length = 0;
for (string s: text) {
for (int i = 0; i < s.length(); i++) {
for (int j = s.length() - 1; j > i && (j - i + 1) > max_length; j--) {
if (s[i] == s[j] && is_palindrome(s.substr(i, j - i + 1))) {
max_length = max(max_length, j - i + 1);
}
}
}
}
return max_length;
}

int main() {
vector<string> text = {
"carracecar",
"aabbaa",
"aabbbabab"
};

for (string s: text) {
cout << is_palindrome(s) << endl;
}

cout << longest_palindrome(text) << endl;

return 0;
}
There is no one like you in the universe.
Fwmeh
Profile Joined April 2008
1286 Posts
March 11 2017 09:39 GMT
#17183
I'm not sure that I understand the complexity analysis of that proposed O(n) solution. I would treat a for-loop with a nested while bound by the length (and half the length is still bound by the length) of the string as O(n^2).

Best I could do, certainly more than 5 minutes. https://ideone.com/M4tVmS. O(n^2), but reasonably good constants.
A parser for things is a function from strings to lists of pairs of things and strings
meatpudding
Profile Joined March 2011
Australia520 Posts
March 11 2017 09:55 GMT
#17184
I guess it's really O(nm) where n is the word length and m is the palindrome length.
Be excellent to each other.
slmw
Profile Blog Joined October 2010
Finland233 Posts
Last Edited: 2017-03-11 12:54:34
March 11 2017 12:53 GMT
#17185
The algorithm in question is Manacher's algorithm. The idea is that we maintain the currently rightmost palindrome, which means that we can look up some of the answers from the left side of the current palindrome since it's simply a mirrored case. The while loop will fail on the first iteration any time we are inside a larger palindrome and don't update the rightmost palindrome. If we need to expand the current palindrome, we update the rightmost palindrome. That means on each iteration we either move the current rightmost palindrome further or do an O(1) copying of a value. The rightmost palindrome can move only at most N times, so the whole algorithm is O(N) per string.

If you try every substring (N^2) in a string and check if it is a palindrome you get an O(N^3) algorithm. That is what Fwmeh's and many others' solution is doing. If you try every midpoint and expand until it is no longer a palindrome, you get an O(N^2) algorithm. This is what travis's solution was doing for odd palindromes.
Manit0u
Profile Blog Joined August 2004
Poland17247 Posts
Last Edited: 2017-03-13 14:14:27
March 13 2017 14:08 GMT
#17186
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect]);
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);

Time is precious. Waste it wisely.
BluzMan
Profile Blog Joined April 2006
Russian Federation4235 Posts
Last Edited: 2017-03-13 15:56:57
March 13 2017 15:54 GMT
#17187
On March 13 2017 23:08 Manit0u wrote:
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect];
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);


Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did.

Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc.

Throwing working code away and rewriting from scratch is almost never a good idea.

One of my favorites:

list($rows, $columns) = array($columns, $rows);


That is a pretty creative way to do a swap one-liner Can you implement cpp-style swap with references in php? Don't remember the exact way they work.
You want 20 good men, but you need a bad pussy.
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2017-03-13 17:27:20
March 13 2017 17:26 GMT
#17188
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.
Acrofales
Profile Joined August 2010
Spain17975 Posts
March 13 2017 17:50 GMT
#17189
I think your answer is fine. Whether your teacher agrees i don't know...
tofucake
Profile Blog Joined October 2009
Hyrule19034 Posts
March 13 2017 17:51 GMT
#17190
Depends on how strict the grader is. Your answer is correct, but it's not a mathematical proof.
Liquipediaasante sana squash banana
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
March 13 2017 18:05 GMT
#17191
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?
Biolunar
Profile Joined February 2012
Germany224 Posts
March 13 2017 18:15 GMT
#17192
There is no such thing as a “mathematical proof”. A proof is a proof, if it is correct independent of how it was proven.
Same goes of following example: ℕ = { n ∈ ℤ | n ≥ 0 } is not more “mathematically” than ℕ = { n ∈ ℤ | n is greater or equal to zero }, although the former is more formal.
What is best? To crush the Zerg, see them driven before you, and hear the lamentations of the Protoss.
Manit0u
Profile Blog Joined August 2004
Poland17247 Posts
March 13 2017 21:35 GMT
#17193
On March 14 2017 00:54 BluzMan wrote:
Show nested quote +
On March 13 2017 23:08 Manit0u wrote:
Does anyone here know any resources where I can dig up some imposition calculation algorithms for printing presses?

I've got new assignment today: rewrite old PHP library as new Ruby gem. Sounds simple enough, but then there's a couple of problems:

  • no documentation
  • no tests
  • entire library is a single class that's 4k lines long (basically no empty lines)
  • at the top of class the error reporting is being disabled (which doesn't bode well)
  • there's plenty of magic arbitrary numbers and overall code readability is on par with assembler
  • loops nested 6 deep with other control statements spread throughout
  • 2k lines of configuration
  • large arrays in global variables, which are being manipulated in different ways by different functions (reversed, reversed with reindexing, values moved around and changed etc. etc.)


After nearly 7 hours of sifting through it I simply gave up trying to understand what's going on in there and I'm looking to simply write this shit from scratch. So, if you know of any resources or ready libraries (any language) that deal with this kind of stuff, please help...

+ Show Spoiler [sample] +


function build_collect_placement_array($sect=1){
$count_pairs = count($this->grid_build_used[$sect];
$inc = 1;
for ($x = 1; $x <= $count_pairs; $x++){ // build an array for each of the two pair numbering patterns
if ($inc > 0) {
if ($x == 1) {
$add_a = 1; // first instance
} else {
$add_a = $arr_b[$x-1] + $inc;
}
if ($add_a==$count_pairs){
$add_b = $add_a;
$inc = -2;
} else {
$add_b = $add_a + $inc;
}
if (($add_b==$count_pairs)&&($add_a!=$count_pairs)){
$inc = 0;
}
} else {
if ($inc == 0) {
$add_b = $arr_b[$x-1];
$inc = -1;
} elseif ($inc == -2) {
$add_b = $arr_b[$x-1] + $inc;
} else {
$add_b = $arr_a[$x-1] + $inc;
}
if ($inc == -2) {
$add_a = $add_b + 1;
} else {
$add_a = $add_b + $inc;
}
}
$arr_a[$x] = $add_a;
$arr_b[$x] = $add_b;
}
$place_arr_a = $arr_a;
$place_arr_b = $arr_b;

$keep_count=1;
for ($x = 1; $x <= 4; $x++){ // loop for each column
for ($y = 1; $y <= $count_pairs; $y++){ // create array for pair placement
$final_pr_arr[$y+($count_pairs*2*($x-1))] = $place_arr_a[$y];
$final_pr_arr[$y+($count_pairs*2*($x-1))+$count_pairs] = $place_arr_b[$y];
}
if (((($count_pairs % 2)==0)||($x==1)||($x==3))&&(($this->grid_cols != 2)||((($this->grid_cols == 2)&&($count_pairs % 2)==0)))){
$temp_arr = $place_arr_a;
$place_arr_a = $place_arr_b;
$place_arr_b = $temp_arr;
}
for ($y = 1; $y <= 2; $y++){ //
for ($z = 1; $z <= 2; $z++){ // build the sub-grid pattern
$inc=0;
if (($count_pairs % 2)==1){ // there is an odd number of pairs
if (($x == 1)||($x == 4)){
if (($y == 1)&&($z == 2)){
$inc=1;
}
if (($y == 2)&&($z == 1)){
$inc=1;
}
}
if (($x == 2)||($x == 3)){
if (($y == 1)&&($z == 1)){
$inc=1;
}
if (($y == 2)&&($z == 2)){
$inc=1;
}
}
if (($this->grid_cols == 2)&&($x == 2)){ // different sub-grid pattern for 4-up
if ((($y == 1)&&($z == 2))||(($y == 2)&&($z == 1))){
$inc=1;
} else {
$inc=0;
}
}
}
for ($a = 1; $a <= (ceil($count_pairs/2)-$inc); $a++){ // create array for sub-grid placement
$final_sg_arr[$keep_count] = $x*2-(2-$z);
$keep_count++;
}
}
}
}
if(is_array($final_pr_arr)) {
foreach ($final_pr_arr as $key => $final_pr_val){
$final_arr[$key]["pair"] = $final_pr_val;
$final_arr[$key]["subgrid"] = $final_sg_arr[$key];
}
ksort($final_arr);
return $final_arr;
}
return null;
}


One of my favorites:

list($rows, $columns) = array($columns, $rows);


Looks like regular production code to me, also pretty well-formed. At least this doesn't have 20 global declarations at the start of each function like our code did.

Based on the sample you provided I would definitely try to reuse it, deep control structure nesting does not necessarily imply redundancy, it might just be that the field is actually that difficult. In that was the case, rewriting it from scratch would be a pretty stupid thing to do. Maybe start with writing tests for the parts you understand and slowly increase the coverage as your understanding grows? Could also refactor obvious subroutines into functions, etc.

Throwing working code away and rewriting from scratch is almost never a good idea.

Show nested quote +
One of my favorites:

list($rows, $columns) = array($columns, $rows);


That is a pretty creative way to do a swap one-liner Can you implement cpp-style swap with references in php? Don't remember the exact way they work.


It doesn't have 20 global declarations at each function. It has 60 at the top of the file though. Swap one-liner is clever, but it comes out of the blue and is buried deep in other logic (also with functions that span several hundred lines it's easy to miss).

I have to pretty much rewrite it anyway since I have to do it in another language. I've started with various utility functions around the code, but it's hard to implement some of the larger methods since no documentation or anything and magic numbers are bad (also, pi with 5 digit precision jumped at me out of nowhere, no explanation why 5 digits or how important it is...). I've been reading some books from 1895 on imposition, also some Rockwell patents I found on Google. It's damn complicated stuff
Time is precious. Waste it wisely.
Liebig
Profile Joined August 2010
France738 Posts
March 13 2017 21:44 GMT
#17194
On March 14 2017 02:26 travis wrote:
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.

I think it's fine, but I would play it safe if it was in the first few questions of the exam and just answer like that

We can assume without loss of generality that b=a+1, c=a+2, d=a+3.
If a=0[4] then a*b*c*d is clearly a multiple of 4
If a=1[4] then d=0[4] and etc

Atreides
Profile Joined October 2010
United States2393 Posts
March 13 2017 21:51 GMT
#17195
On March 14 2017 02:26 travis wrote:
I am studying for my discrete math midterm. Here is a question that an old exam asks:

Prove:
If a, b, c and d are consecutive integers, 4 | abcd.

*please note that this is under the heading "formal proofs"


So my answer is:

+ Show Spoiler +

Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. Therefore 4 can be factored from a*b*c*d. Therefore 4|abcd.


Here is what the answer key says:

+ Show Spoiler +

Without loss of generality, assume that a is an even number. From a known theorem in class, we know that consecutive integers have opposite parity, which means that b is odd, and c is even. By the definition of even parity, this means that there exist integers k_1, k_2 such that a = 2k_1 and c = 2k_2 . Therefore, a · b · c · d = (2k_1) · b · (2k_2) · d = (4k_1k_2)bd = 4 (k_1k_2bd) m∈Z = 4m ⇔ 4|abcd.


So I guess my question is, does my answer suffice for a "formal" proof?
Also this question is dumb.


Every math professor in the world here is just looking for you to say there is two even numbers bla bla bla. It's ez to formalize.

Jumping straight to divisible by four is obviously doable but slightly harder to formalize. For a question like that the entire thing is formalizing something intuitively obvious so I can't imagine any prof giving full credit for your answer.
Hanh
Profile Joined June 2016
146 Posts
Last Edited: 2017-03-14 01:26:41
March 14 2017 01:10 GMT
#17196
On March 14 2017 03:05 travis wrote:
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?


You can only use theorems and axioms that were given to you during your class, so I wouldn't call your answer a formal proof.

Edit:
1. Use the canonical injection to go from N to Z/4Z.
2. By definition, you get 4 different equivalent classes of Z/4Z.
3. Z/4Z has cardinality 4. Therefore one of the classes must be 0.
4. the product is 0
5. Therefore the product is a multiple of 4.
Prillan
Profile Joined August 2011
Sweden350 Posts
March 14 2017 18:33 GMT
#17197
On March 14 2017 03:05 travis wrote:
So technically to make it a mathematical proof I would need to do what? State step one mathematically and then prove the other steps by mathematically manipulating what I start with?

You need to state why the things you do are true. Ask "why?" until you reach an already proved result.
To get you started:
Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4.

Why?
TheBB's sidekick, aligulac.com | "Reality is frequently inaccurate." - Douglas Adams
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2017-03-15 02:10:03
March 14 2017 22:49 GMT
#17198
To add onto everyone's answers, I believe the problem is you're not rigorous enough with your terminology. A formal proof has a certain structure because the structure makes reasoning very clear. In your answer, you've skipped those structures, but the proof is still mostly comprehensible because the domain is pretty straight-forward. But it's likely that the purpose of these exercises is to teach you these concepts in preparation for later proofs - eventually having the concepts translate to programming logic - so skipping these structures kind of misses the point of the lesson.

Now to go over your answer. Correct me if I am wrong, but "multiple" and "factor" are not words in the theorems you've been taught. They are obvious mathematical definitions and results of the theorems, and maybe part of some related, unpresented corollary due to those definitions, but they essentially aren't part of your set of premises. The goal of these exercises is to have you conceptualize how to infer the result, given the premises. Using these "unrelated" concepts and jumping from result to result is what is I meant by not being rigorous.


> Any 4 consecutive numbers (a,b,c,d) must contain a multiple of 4. (1)

Is this true? It looks like it's true, but how do I prove that? Is it so trivially true that it's unnecessary to show (1*n = n)? Is this the result of some theorem that I know (n|a-b => a === b mod n)? This result is intuitive, in that it's easy enough to convince yourself that this must be true, but how do you show that in writing?

> Therefore 4 can be factored from a*b*c*d. (2)

What did factored come from and what factored mean? Are you saying that "multiple of n" implies "factor out by n"?

> Therefore 4|abcd. (3)

Are you saying that "factor n from x" implies "n | x"?


I think you'd have to enumerate all the cases in (1) to show a proof of it.


Suppose a,b,c,d are consecutive numbers.
Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4.
<show that this is true>
Without loss of generality, suppose a is divisible by 4.
Therefore there exists n such that a = 4n. (2)
Therefore there exists n such that abcd = 4nbcd.
If x == nbcd, then abcd = 4x.
From definitions, a | b iff a*n = b.
Therefore 4 | abcd. (3)
There is no one like you in the universe.
netherh
Profile Blog Joined November 2011
United Kingdom333 Posts
March 15 2017 04:29 GMT
#17199
On March 15 2017 07:49 Blisse wrote:
Suppose a,b,c,d are consecutive numbers.
Any 4 consecutive numbers (a,b,c,d) must contain 1 number which is a multiple of 4.
<show that this is true>
Without loss of generality, suppose a is divisible by 4.
Therefore there exists n such that a = 4n. (2)
Therefore there exists n such that abcd = 4nbcd.
If x == nbcd, then abcd = 4x.
From definitions, a | b iff a*n = b.
Therefore 4 | abcd. (3)


Probably dumb questions:

What does the line in 4 | abcd mean?
What does "without loss of generality" mean, and why do you use it there?
tofucake
Profile Blog Joined October 2009
Hyrule19034 Posts
March 15 2017 04:35 GMT
#17200
4 | abcd means "4 divides abcd"
Liquipediaasante sana squash banana
Prev 1 858 859 860 861 862 1031 Next
Please log in or register to reply.
Live Events Refresh
RSL Revival
10:00
Season 1: Playoffs FINALS
Classic vs Clem
Tasteless3964
Crank 772
Rex64
IndyStarCraft 37
3DClanTV 32
IntoTheiNu 14
LiquipediaDiscussion
Sparkling Tuna Cup
10:00
Weekly #97
CranKy Ducklings34
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Tasteless 3964
Crank 772
Rex 64
IndyStarCraft 37
MindelVK 1
StarCraft: Brood War
Horang2 21367
Jaedong 918
Larva 628
firebathero 489
Pusan 371
PianO 341
BeSt 261
Leta 161
EffOrt 156
Sharp 115
[ Show more ]
Shinee 96
ToSsGirL 73
NaDa 30
Barracks 25
Last 15
GoRush 11
Hm[arnc] 8
yabsab 5
SilentControl 5
HiyA 4
Dota 2
XaKoH 470
XcaliburYe346
League of Legends
JimRising 521
Counter-Strike
Stewie2K523
x6flipin2
Heroes of the Storm
Khaldor290
Other Games
tarik_tv13194
gofns9687
shahzam413
Happy364
crisheroes274
DeMusliM190
SortOf160
Organizations
StarCraft 2
ComeBackTV 561
StarCraft: Brood War
lovetv 5
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 12 non-featured ]
StarCraft 2
• Berry_CruncH347
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2111
Upcoming Events
FEL
4h 51m
Elazer vs Spirit
Gerald vs MaNa
BSL20 Non-Korean Champi…
7h 51m
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
1d
Replay Cast
1d 23h
WardiTV European League
2 days
PiGosaur Monday
2 days
uThermal 2v2 Circuit
3 days
Replay Cast
3 days
The PondCast
3 days
Replay Cast
4 days
[ Show More ]
Epic.LAN
5 days
CranKy Ducklings
5 days
Epic.LAN
6 days
BSL20 Non-Korean Champi…
6 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
6 days
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
BSL20 Non-Korean Championship
CSLPRO Last Chance 2025
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
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 © 2025 TLnet. All Rights Reserved.