EthOmus
BAN USERThe ranges of jumps are more or less mutually inclusive , the only necessary info to maintain is the furthest jump
then you search the furthest jump you can make the next step with in the range you can reach from the last jumps
#include<stdio.h>
#include<stdlib.h>
void f(int *ary, int size){
int bgn, end=-1;// inclusive end, exclusive bgn
int stp_cnt=0;
int leap_dst=0; //the furthest frog can jump next stp
int ary_end=size-1;
do{
bgn=end;
end=leap_dst;
int i;
stp_cnt+=1;
for(i=end;i>bgn;i--)
if(leap_dst<i+ary[i])
leap_dst=i+ary[i];
if(leap_dst==end){
printf("unreachable\n");
return;
}
}while(leap_dst<ary_end);
printf("%d\n",stp_cnt);
}
main(){
int ary1[]={1, 5, 4, 6, 9, 3, 0, 0, 1, 3};
int ary2[]={2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
f(ary1,10);
f(ary2,10);
}
#include<stdio.h>
struct jar{
int* candies;
int size;
};
typedef struct jar jar;
int candies_v[]={1,2,3,4,6}; //just for demo, use dynamic allocation in pratice
jar jars[3]={{&candies_v[0],2},{&candies_v[2],2},{&candies_v[4],1}};
main(){
jar *jar_p1, *jar_p2;
int *cnd_p1, *cnd_p2;//cnd for candy
for(jar_p1=jars;jar_p1<jars+3;jar_p1++)
for(cnd_p1=jar_p1->candies;cnd_p1<jar_p1->candies+jar_p1->size;cnd_p1++)
for(jar_p2=jar_p1+1;jar_p2<jars+3;jar_p2++)
for(cnd_p2=jar_p2->candies;cnd_p2<jar_p2->candies+jar_p2->size;cnd_p2++)
printf("%d(jar%d),%d(jar%d)\n",*cnd_p1,jar_p1-jars,*cnd_p2,jar_p2-jars);
}
@barcod : You are right that it is irrelevant .Yet although I said "list", I never suggested linked list , I say dynamically allocated arrays( arrays of pointers); there should be a small number of space statically given to each object("user" or "likeable") but the array could be reallocated to a longer array if certain indicators expect a huge number of "likes" for an item or "liked" for an user
- EthOmus January 23, 2013When a user click on an item object with a "like it" buttom
1. An variable associated with this item object is incremented.
2. An link(address) of the item object(or perhaps a picture as well) is copied from the object to a list of "likes" in the "user" object in question.
3. An link to the user is added to item object's list of users who "likes it"
The lists are implemented as arrays and dynamically expand themselves as need be
------------------------update on Jan/23----------
I rethought about the question
1.the thing about "likes" is that it could be any thing from 0 to billions. We probably don't have to store all the links in their complete form, after all ,who will ever exam all the millions of people who clicked on likes. We could probably code the links for storage and decode them only when necessary.
2. The essence of likes is but a combination (u,i) in which u is an user and i is a likeable item. Considering the huge number of likes, and the already accepted delayed speed of web, perhaps instead of storing this information in user object as well as in the "liked" object, we could centralize it and store this combinational relationship in one place, and search for it when the item or the user request information. Of course a great amount of searching will be necessitated, but we can arrange the information by date, and give precedence to more recent data. Judging by the characteristics of Facebook, I don't think many users would EVER request data from...say 5 years ago. So we don't search further than 5 years unless the user explicitly asks
By the way, the consideration that people will only actually look at a small amount of the data and most of the time only the very recent ones is why I had proposed lists instead of hash. The list is long, but you only need to traverse the begin part! the outdated data should be encoded and throw into archive, which should be expansive in size, efficient in storage organization but not necessarily speedy.
Hope I am not mistaken. but if the two arrays A,B are in ascending order, why not compare the first element of the two then the smallest k combonations will be the frist element added with elements of the other array?
int * f ( int [ ] A, int[ ] B, int k){
int min,* other_array;
if( A[0]>B[0]) {min=B[0]; other_array=A;}
else {min=A[0]; other_array=B;}
int i;
for(i=0;i<k;i++) other_array[i]+=min;
return other_array;
}
The question istself describes this algorithm with an example, it can't be so simple but I can' interpret the question other wise
- EthOmus January 18, 2013You are in effect copying a graph, which may be circular, say a node points to one of its predecessors in the list.
The one thing notable is that you have a path with covers every node in the graph for only once.So if the nodes aren't many, you can traverse the old linked list or the new "graph" to check what you have already copied(the latter presumably better for it has less nodes, yet the pointers may overlap each other and point to the same nodes multiple times,the overlapping being proportional to the number of pointers of each node, plus you need to deal with the possibility of circling) instead of using a full-blown hash table; I leave out the implementation.
we need two arrays ary1, ary2 ; both size of n, for positive values and negative values
The fact that ary1 and ary2 are built up as we read the target array from bgn to end guarantees that relative positions between values of the same sign would not change
- EthOmus August 24, 2013