Urik's twin Cookie Monster (dead now)
BAN USERWhy not shrink your idea to 1 person who takes the bottles in some predefined order at time intervals of 10 min. (or any < 15 min.) ?
- Urik's twin Cookie Monster (dead now) October 31, 2013Many pruning opportunities available too, if your problem size grows too much.
But that would make the code messy for a "starter" solution.
Aligned better for careercup:
uint cutoff, max; //cutoff: upperbound for valid product (e.g., 1000 if N=3)
void _func(uint O, uint prod, uint prev)
{
if(O==0) {
if(cutoff/10<=prod && prod<cutoff && prod>max) max=prod; return;
}
for(int i=9; i>=prev; i--) _func(O-1, prod*i, i);
}
uint func(uint N, uint O)
{
for(cutoff=1; N>;0; cutoff *=10, N--) ;
max=-1, _func(O, 1, 2); //last "2" controls min. digit
return max;
}
Let uint be some unsigned integer (or plain integer in Java).
Backtrack but without repeating ways of creating same product (redundant).
e.g. 2*3 same as 3*2. So create products in increasing order only...
uint cutoff, max; //cutoff is upperbound for valid product (e.g., 1000 if N=3)
void _func(uint O, uint prod, uint prev)
{
if(O==0) { if(cutoff/10<=prod && prod<cutoff && prod>max) max=prod; return; }
for(int i=9; i>=prev; i--) _func(O-1, prod*i, i); //try digits greater than previous
}
uint func(uint N, uint O)
{
for(cutoff=1; N>0; cutoff *=10, N--) ;
max=-1, _func(O, 1, 2); //last "2" controls min. digit
return max;
}
@anonymous
You need to buzz off dude. I'm reading my post and its repliesbecause I love teaching/talking about problems (hope to be a prof. some day) so I'm checking replies to it.
The guy who uses an anonymous handle and who was up-voting himself with an alternate account and was dropping corny jokes for no reason (that sounded like insults because he used "you/your") now claiming the high ground of staying on topic and keeping careercup pure.
"Oh all I was doing is making fun of myself over and over as replies to your code, didn't you notice?"
"Hey stop, we need to keep this on topic."
anonymous, someone named "com" is upvoting your comments
specifically the ones which "debate" me
could be your fan or someone who is both aligned strongly with your debate points and is also following your activity on short time frames
doesn't matter at all to me
What is my main instrument? Your point about "only one hammer see nail yada yada" is actually a point against people who think in one or few languages.
In other words, using "hash table" covers many hammers, while using "HashSet" is the few hammer approach.
Why are you arguing main instrument and blah blah over 1 min. coding exercises?
@Andy, you are better off % down to table size.
What if you have IP addresses from around the world (e.g. Amazon web stats for a day) ? What if you are top level router/gateway/switch located on the island of Atlantis?
:) Very nice game tree pruning.
- Urik's twin Cookie Monster (dead now) October 30, 2013And why do you keep upvoting your own comments?
- Urik's twin Cookie Monster (dead now) October 30, 2013@anonymous
That's true. Awwww I feel for you man. To solve that problem I'd suggest you expose yourself to more languages to become more eclectic. Try perl, python, bash/sh scripting, lisp/scheme, and best of all a metalanguage called "write pedagogical pseudo-code so as get your point across."
Is it not that obvious that h.exists() and h.insert() make it clear that we need a hash table which at minimum has some boolean nature internally?
The operations define the required D.S.
language independence my friend
- Urik's twin Cookie Monster (dead now) October 30, 2013Treat it as a 32 bit unsigned integer, and use some famous hash (google one).
Or design an unsigned integer hash as per your algorithms text.
i=0, j=s.length-1;
do {
while( i < s.length && s[i]==' ') i++;
while( 0 <= j && s[j]==' ') j--;
if( i>=j ) return true;
if(s[i++] != s[j--]) return false;
} while(true);
Is the question a joke? Amazon? Memory constrained environment? :S
- Urik's twin Cookie Monster (dead now) October 30, 2013Yeah. O(range).
Complain @S.Developer :)
Nice discussion folks (forced some thinking).
I am trying to salvage is 1 to 4 list:
S.Dev's solution #1)
----------------------------
I think we can do it with O(n) extra space.
Declare class/struct like this:
struct {
Type or Type* item; //store or point to element in array
unsigned int index; //index of item in original;
};
Then fill out a linked list (or array list) of structures like defined above to mirror the array.
Now we can
a) Sort on the indices (doesn't need to be stable)
b) Stable sort on the item's (so can't use quicksort because it is unstable)
Now we traverse the list and remove duplicate links.
Then
c) We sort it on indices again.
We should have the result in the linked list (or array list) now.
Confirm please.
His solution #4) {This assumes integer items though}
----------------------
a) On first pass find max and also min.
b) then declare:
bool tab[max - min + 1] ={0};
c) then use this no-collision hash:
#define h(x) ((x)-min)
d) then run regular hash scheme:
for(to=from=0; from < a.length; from++) {
if( tab[ h(a[from]) ] ) continue;
else tab[ h(a[from]) ]=true, a[to++] = a[from];
}
a.length=to;
Space is O(range) though, but no pain in the neck % and collisions.
Off by one errors? :)
Manually like this.
Whenever you think of "have I seen it before" problems, think "hash tables."
h is hash table for elements in your array.
for(to=from=0; from < a.length; from++)
if( h.exists(a[from]) ) continue; //if seen before, don't copy backwards
else h.insert(a[from]), a[to++] = a[from]; //else mark it seen, and copy back
a.length=to; //<-- mutable object with public field for convenience
Should work.
- Urik's twin Cookie Monster (dead now) October 29, 20137 element array
and an index into it to keep track of current (or previous) day
Notice Jielei's answer right there in the initial post.
int doit(Node x){ if(x) return max((doit(x.left), doit(x.right)) + x.val; return 0; }
@bossAjeet, bail this thread man.
This similar to each and everyone proving some different statement on the premise of a contradiction.
So by design decision, the range you output is ]x, y] . That's cool. Same thing.
:)
My interpretation of your question. QA it Mr. "Solve Me Some Quadratic Equations" (code 123).
ideone.com/cfGilp
#include <stdio.h>
typedef enum {false, true} bool;
int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)
/* mutually recursive functions our_move and opp_move return true
if 'we' are guaranteed a win with the right choices from that state;
can do this win 1 function (track "depth" recursion even vs. odd),
but mentally easier for me to think of 2 players*/
bool our_move();
bool opp_move()
{
bool opp_wins=false; //can opp. win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( !our_move() ) opp_wins=true; //opp. can win
boxes[i] += j;
if(opp_wins) return false; //we are not guaranteed win
}
}
return true; //boxes already empty, or we always win
}
bool our_move()
{
bool our_wins=false; //can we win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( opp_move() ) our_wins=true; //we "can" win
boxes[i] += j;
if(our_wins) return true; //we are guaranteed win
}
}
return false; //boxes already empty, or all choices lose
}
int main(void) {
int i, j;
/* we make our possible first moves and see if they guarantee win
(i.e, guarantee opp. loss ) */
for(i=0; i<N; i++)
for(j=1; j<=boxes[i]; j++)
{
boxes[i] -= j;
printf("First move <remove %d sticks from box %d>"
"can%s guarantee win\n",
j, i+1, (opp_move())?"":"not");
boxes[i] += j;
}
return 0;
}
#include <stdio.h>
typedef enum {false, true} bool;
int boxes[] = {1,1,2,1}; //boxes of sticks
#define N sizeof(boxes)/sizeof(*boxes)
/* mutually recursive functions our_move and opp_move return true
if 'we' are guaranteed a win with the right choices from that state;
can do this win 1 function (track "depth" recursion even vs. odd),
but mentally easier for me to think of 2 players*/
bool our_move();
bool opp_move()
{
bool opp_wins=false; //can opp. win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( !our_move() ) opp_wins=true; //opp. can win
boxes[i] += j;
if(opp_wins) return false; //we are not guaranteed win
}
}
return true; //boxes already empty, or we always win
}
bool our_move()
{
bool our_wins=false; //can we win from this state?
int rem_items, i, j;
for(i=0; i<N; i++) {
rem_items=boxes[i];
for(j=1; j<=rem_items; j++) {
boxes[i] -= j; //remove j sticks from box i as a move
if( opp_move() ) our_wins=true; //we "can" win
boxes[i] += j;
if(our_wins) return true; //we are guaranteed win
}
}
return false; //boxes already empty, or all choices lose
}
int main(void) {
int i, j;
/* we make our possible first moves and see if they guarantee win
(i.e, guarantee opp. loss ) */
for(i=0; i<N; i++)
for(j=1; j<=boxes[i]; j++)
{
boxes[i] -= j;
printf("First move <remove %d sticks from box %d>"
"can%s guarantee win\n",
j, i+1, (opp_move())?"":"not");
boxes[i] += j;
}
return 0;
}
u added an example now, but you still have "final move"
change that to "first move"
true saying boss
- Urik's twin Cookie Monster (dead now) October 29, 2013@RAM, what do you mean?
Sort "positions" into the file (line positions) ?
And why char *data for the second/ field (they are just small integers)?
If you are sorting positions of records in the original file, once you sort these structures, you might have to seek all around the file to actually print the results.
Y?
- Urik's twin Cookie Monster (dead now) October 29, 2013Find the last move for the win?
That would be:
All boxes empty except one, and last move being emptying last box.
Done. No coding needed?
+1 Nice.
Maybe I'm wrong, but do you have an off by one error on finding the real start of the range?
How about handling case of the array [ 0 1 7 7 7 ] ?
Reviewed own code: Overflow bug for "sum" :)
Exercise: Small change to fix that.
agree with the comment (not the swearing :P ).
- Urik's twin Cookie Monster (dead now) October 28, 2013unsigned int mod7(int x)
{
int r;
return (r = x%7)>=0 ? r : r+7 ;
}
void findlongest7(int a[])
{
struct { bool seen; int first; int last; } h[7]; //special "direct" hash
int i, sum=0, p; //p: prefix sum mod down to {0,...,6}
int maxp, maxlen; //used in 2nd for loop
h[0].seen=true, h[0].first=-1;
for(i=0; i<a.length; i++) {
sum+=a[i], p=mod7(sum);
if(h[p].seen) h[p].last=i; //seen before, current is last seen
else h[p].seen=true, h[p].first=i; //seen for first time
}
//find max. len. subarray (only ~C*7, not O(N))
maxlen=0, maxp=-1;
for(i=0; i<7; i++)
if(h[i].seen && (h[i].last - h[i].first) > maxlen )
maxp=i, maxlen=(h[i].last-h[i].first);
//results announced
if(maxp==-1) { printf("No such subarray found\n"); return; }
printf("Subarray of maximal length %d found at [%d : %d]",
maxlen, h[maxp].first+1, h[maxp].last);
}
How it works:
**) define s[i] as prefix sum of array <= index i
If a subarray from a[x:y] has sum divisible by 7, then
sum(a[x:y]) = s[y] - s[x-1] is divisible by 7
But a[x:y] is divisible by 7 means exactly that mod7(sum(a[x:y]))==0
Translate it onto above equation:
0== mod7( sum(a[x:y]) ) = mod7( s[y] - s[x-1] )
= mod7( s[y] ) - mod7( s[x-1] ) == 0
last line true if and only if (take to other side)
mod7( s[y] ) == mod7( s[x-1] )
So we do not have to care about prefix sums, but only prefix sums mod7 (i.e., "p" in the code above). This makes it easy, because there are only 7 possible values for mod7_prefix_sums, in {0,...,6}.
Question is ambiguous.
"Message" come on stdin (line buffered) ? Or it's already in a single string (with \n embedded)? Or array of 3 strings?
"Should read it as" means what?
I don't usually use % with negatives on either side, but I looked up a version of C standard, related to a%b :
" If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined. "
[ from ISO14882:2003(e) is no longer present in ISO14882:2011(e) ]
And we are guaranteed:
" (a/b)*b + a%b == a "
[The earlier statement has to be compared against this guarantee]
So it seems, for example, -9%4 can return -1 or 3 depending on compiler.
So we would need to create our own "mod7" wrap around %7 to make sure it always gives something in range 0, ..., 6 on different compilers:
unsigned int mod7(int x)
{
return (r = x%7)>=0 ? r : r+7 ;
}
Now which version of the problem are we solving?
1) Test for existence true/false
2) Test and return any evidence of existence
3) Test and find longest subarray with that property?
1) to 2) to 3) are only incremental modifications of code.
void succ(Node *x, int key)
{
static bool found;
if(x==NULL) return ;
succ(x->left);
if(x->val == key) found=true;
else if(found) cout<<x.val or x<< "is successor", found=false, return;
succ(x->right);
}
In search trees, you can cut the complexity by following the actual path down, noting the last "possible" successor ancestor, then try diving below the target node to find a successor, else use the ancestor.... (works on paper)... but blah blah blahhhhhhhhhhhhhhhhhhh that's boring.
- Urik's twin Cookie Monster (dead now) October 28, 2013This should do the job (or the bugless version of it)....
void succ(Node x, int key)
{
static bool found;
if(x==nil) return;
succ(x.left);
if(x.val == key) found=true;
else if(found) printf(x.val or x), found=false, return;
succ(x.right);
}
Rename tryfromleft to findindex and delete the rest (the original findindex and the tryfromright).
That's 1 linear pass., still O(n).
Then try binary searching to get it down to lg n.
2 linear passes worst case. Which is O(n).
But if you coded it correctly, either
1) Try from left will give you an index found. OR
2) Both try from left and try from right will fail and return -1
In other words, try from right would be redundant.
Ahh ic. The question is funky in wording. "Set" and Nth element just do not work together in terms of definition.
Why wouldn't an _idiot_ posting this question give an example at least?
input
0 1 2 20 21 22
10 11 12 14 15 59
output
"What's the order" of this "set of pairs/sums" ?
Guess what, writing the example with automatically give the idiot the algorithm. So let him/her do that? Not my decision.
Are you sure comparing a[i+1] with b[j+1] enough?
Do you need a counter? Running loop on condition i+j < N should be enough.
Nevertheless, for this specific problem size (fixed problem),
It is simply a permutation of the 6 nondiagonal spots.
So you can hard code 7 writes/copies using 1 temp variable if you like.
No loops needed.
code123 must be in grade 9
- Urik's twin Cookie Monster (dead now) October 28, 2013oh yeah? does it blow up in black smoke on that case?
- Urik's twin Cookie Monster (dead now) October 28, 2013Transpose then swap 2 elements:
for(i=0; i<3; i++)
for(j=i+1; j<3; j++)
swap(a[i][j], a[j][i]); //transpose
swap(a[0][1], a[2][1]); //extra swap
bool seen[7];
sum=0;
seen[0]=true;
for(i=0; i < a.length; i++)
{
sum += a[i];
if( seen[sum%7] ) return true; //found
seen[sum%7] = true;
}
return false; //not found
Minor change (a line or two) if you want to return indices of array
struct {bool flag; int index; } seen[7];
sum=0;
seen[0].index=-1, seen[0].flag=true;
for(i=0; i < a.length; i++)
{
sum += a[i];
if( seen[sum%7].flag )
printf("found here a[%d : %d]\n", seen[sum%7].index +1, i), return;
seen[sum%7].flag = true, seen[sum%7].index=i;
}
printf("Not found\n"), return;
Not compiled nor tested.
Probably totally wrong lol.
"For getting holes info" doesn't describe any problem to me.
Time to bail on this thread.
Huh? That's brute force obvious.
We should be able to use information just from the corners
@Matt, the last return statement funnels it upstream.
@Anon, your code will never go past the second return statement (the first naked out, meaning not surrounded by if statement).
spring loaded boxing glove aimed at backside while sleeping
- Urik's twin Cookie Monster (dead now) October 28, 2013what library call on linux, for example?
- Urik's twin Cookie Monster (dead now) October 28, 2013
Repgladysloweg, Brokerage clerk at Bell Markets
I am Gladys from Defiance city . I am working as a Brokerage clerk with tasks associated with securities such as ...
The link you posted has no leeway in terms of time, so the answer is log_2 (1000) => rounded up 10 humans needed. (Many ways to reason this)
- Urik's twin Cookie Monster (dead now) October 31, 2013The problem this fellow posted has degree of freedom in terms of time, so we can compress all the secret information onto one human and let the information seep out sequentially and visibly on the other side of 60 min.