[Problem Solving #2] Sharing is Caring

[Ciccioo]

Hmm interesting, changing everything to %d works. but the z modifier was added in c99 wasn't it? I'll just blame it on Windows.

 

I use Python 3.3, the input function changed a bit in 3.0 but anything 3+ should work.

I googled a bit and it seems like yes, %z modifiers are a C99 addition, so i'm not sure what's going on here. It's supposed to be portable though (at least on gcc, as MSVC wants %I instead)

I'll try later to understand this specifier thing and to run your code, can't try it right now

[Nuluvius]

BLAST!! That's the second time I have neglected the final return...

[Ciccioo]

improved version of my previous code:

more than 90% of the execution time was taken away by the reading routine, so i implemented a faster function than scanf to parse the input

the reading routine is now about 7x faster, so is the whole program

 

edit: fixed the memory leak as well

 

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef enum{    false,    true}bool;typedef struct{    bool visited;    size_t nFriends;    size_t* friends;}person;size_t fastRead(char* buffer){    static char* str = NULL;    if(buffer)        str = buffer;    char c;    size_t val = 0;    while((c = *str++) && c >= '0' && c <= '9')        val = val * 10 + c - '0';    return val;}person* readInput(size_t* P, size_t* David){    const int SBSize = 10;    char smallBuffer[sBSize];    fgets(smallBuffer, SBSize, stdin);    *P = fastRead(smallBuffer);    person* facebook = malloc(*P * sizeof *facebook);    size_t BBSize = *P * 10;    char* bigBuffer = malloc(BBSize * sizeof *bigBuffer);    size_t i;    for(i = 0; i < *P; i++){        facebook[i].visited = false;        fgets(bigBuffer, BBSize, stdin);        facebook[i].nFriends = fastRead(bigBuffer);        facebook[i].friends = malloc(facebook[i].nFriends * sizeof(size_t));        size_t j;        for(j = 0; j < facebook[i].nFriends; j++)            facebook[i].friends[j] = fastRead(NULL);    }    free(bigBuffer);    fgets(smallBuffer, SBSize, stdin);    *David = fastRead(smallBuffer);    facebook[*David].visited = true;    return facebook;}void freeInput(person* facebook, size_t P){    while(P--)        free(facebook[P].friends);    free(facebook);}int main(){    size_t P, David;    person* facebook = readInput(&P, &David);    size_t maxSharingDay = 0;    size_t maxSharing = 0;    size_t friendsLeft = P;    size_t queueSize = facebook[David].nFriends;    size_t* queue = malloc(queueSize * sizeof *queue);    memcpy(queue, facebook[David].friends, queueSize * sizeof *queue);    size_t sharingDay = 0;    while(queueSize && friendsLeft > maxSharing){        sharingDay++;        size_t i, friendsToQueue = 0;        for(i = 0; i < queueSize; i++)            if(!facebook[queue[i]].visited)                friendsToQueue += facebook[queue[i]].nFriends;        size_t sharing = 0;        size_t* newQueue = malloc(friendsToQueue * sizeof *newQueue);        size_t queuePosition = 0;        for(i = 0; i < queueSize; i++){            person* guy = facebook + queue[i];            if(!guy -> visited){                guy -> visited = true;                friendsLeft--;                sharing++;                memcpy(newQueue + queuePosition, guy -> friends, guy -> nFriends * sizeof *newQueue);                queuePosition += guy -> nFriends;            }        }        free(queue);        queue = newQueue;        queueSize = friendsToQueue;        if(sharing > maxSharing){            maxSharing = sharing;            maxSharingDay = sharingDay;        }    }    free(queue);    freeInput(facebook, P);    printf("%zu\n%zu\n", maxSharing, maxSharingDay);    return 0;}

[Ciccioo]

Hmm interesting, changing everything to %d works. but the z modifier was added in c99 wasn't it? I'll just blame it on Windows.

 

I use Python 3.3, the input function changed a bit in 3.0 but anything 3+ should work.

i can compile my code with gcc under linux even with -std=c89, without even warnings. dunno how, dunno why

i tried to compile it in windows but i just can't get code::blocks to switch to C99, even using -std=c99 (and checking the build log to be sure that it was put as a parameter to mingw-gcc) it still uses c89. i just tableflipped and left

 

using Python 3.3 worked

[MikeD]

Not much to be said...

Except that, once again, my code is not well organized and variable names could have been chosen better!

 

 

#include <stdio.h>#include <stdlib.h>typedef struct queue_t {  int id;  struct queue_t *next;} Queue;typedef struct {  int knows;  int nfriends;  int *friends;} Person;void queue_insert(Queue **q, int id) {  Queue *aux;  Queue *new = malloc(sizeof(Queue));  new->id = id;  new->next = NULL;  if(*q == NULL)    *q = new;  else {    aux = *q;    while(aux->next != NULL)      aux = aux->next;    aux->next = new;  }}int queue_remove(Queue **q) {  int ret;  Queue *aux;  if(*q == NULL)    return -1;  else {    ret = (*q)->id;    aux = (*q)->next;    free(*q);    *q = aux;  }  return ret;}int main() {  int p, d, maxsize = 0, maxday = 0;  Person *people;  Queue *q = NULL;  int i, j, today, size, day = 0, person, currPerson;  scanf("%d\n", &p);  people = malloc(sizeof(Person) * p);  for(i = 0; i < p; i++) {    people[i].knows = 0;    scanf("%d ", &(people[i].nfriends));    people[i].friends = malloc(sizeof(int) * people[i].nfriends);    for(j = 0; j < people[i].nfriends; j++)      scanf("%d", &(people[i].friends[j]));  }  scanf("%d\n", &d);  people[d].knows = 1;  queue_insert(&q, d);  today = 1;  while(q != NULL) {    day++;    size = 0;    for(i = 0; i < today; i++) {      person = queue_remove(&q);      for(j = 0; j < people[person].nfriends; j++) {        currPerson = people[person].friends[j];        if(!people[currPerson].knows) {          people[currPerson].knows = 1;          queue_insert(&q, currPerson);          size++;        }      }    }    if(size > maxsize) {      maxsize = size;      maxday = day;    }    today = size;  }  printf("%d\n%d\n", maxsize, maxday);  for(i = 0; i < p; i++)    free(people[i].friends);  free(people);  return 0;} 

[Nuluvius]

I haven't forgotten to post my code; just don't have time with work atm (needs a refactor) plus I wanted to see if I could accomplish the same thing using LINQ. Basically I process all 5 files at once

[Maximation]

Sigh. I have spent a whole day trying to solve this problem, but I still have not found the correct solution. I have made some good progress though. There are still some weird things I do not understand going on. My brain gave up, I should probably do something else for a few hours. If someone would want to review the code I have written so far, go ahead, maybe you can find a way to help me, that would be nice. Also, please give suggestions on how to improve my code, I assume it is not that well written.

 

import java.util.*;public class Main {	private static int cardinality;	private static int indexDavid;	private static int[][] adjacency;	private static List<Integer> queue = new ArrayList<Integer>();	private static boolean [] isVisited;	private static int maxShares = 0;	private static int firstDayMaxShares;	private static int day = 0;	private static int shares = 0;	public static void main(String[] args){		Scanner in = new Scanner(System.in);		/*		 *	gets the size of david's social network (first integer on the first line)		 */		cardinality = in.nextInt();				/*		 *	sets size of the social network and isVisited arrays to the amount of people in the social network		 */		adjacency = new int[cardinality][];		isVisited = new boolean[cardinality];		/*		 *	stores all friends of the people in the social network in an array in an array		 */		for (int i = 0; i < cardinality; i++) {			int degree = in.nextInt();			int[] friends = new int[degree];			for (int j = 0; j < friends.length; j++)				friends[j] = in.nextInt(); 			adjacency[i] = friends;		}		/*		 *	gets last integer of the input file (index of David)		 */		indexDavid = in.nextInt();		setAllFalse();		startSharing();		System.out.println("Max shares : " + maxShares);		System.out.println("First day to achieve max shares : " + firstDayMaxShares);	}	private static boolean startSharing() {		if (adjacency[indexDavid].length == 0)			return true;		addAdjacentVerticesToQueue(indexDavid);		while (doesEveryoneKnow() == false){			day++;			shares = 0;			int queueSize = queue.size();			for (int i = 0; i < queueSize; i++){				System.out.println(queueSize);				if (isVisited[i] == false)					shareWithAdjacentVertex(queue.get(i));				addAdjacentVerticesToQueue(queue.get(i));			}			for (int j = 0; j < queueSize; j++)				queue.remove(j);			if (shares > maxShares) {				maxShares = queueSize;				firstDayMaxShares = day;			}		}		return true;	}	private static void shareWithAdjacentVertex(int index) {		for (int i = 0; i < adjacency[index].length; i++) {			isVisited[adjacency[index][i]] = true;			shares++;		}	}	private static void addAdjacentVerticesToQueue(int index) {		for (int i = 0; i < adjacency[index].length; i++) {			queue.add(adjacency[index][i]);		}	}	private static boolean doesEveryoneKnow() {		for (int i = 0; i < isVisited.length; i++) 			if (isVisited[i] == false) return false;		return true;	}	private static void setAllFalse() {		for (int i = 0; i < isVisited.length; i++)			isVisited[i] = false;	}	}

[Nuluvius]

Sigh. I have spent a whole day trying to solve this problem, but I still have not found the correct solution. I have made some good progress though. There are still some weird things I do not understand going on. My brain gave up, I should probably do something else for a few hours. If someone would want to review the code I have written so far, go ahead, maybe you can find a way to help me, that would be nice. Also, please give suggestions on how to improve my code, I assume it is not that well written.

 

 

Without getting into the logic an obvious architectural improvement would be to use a class/structure to represent a Person (Vertex):

import java.util.*;public class Main {	private static int cardinality;	private static int indexDavid;	private static int[][] adjacency;	private static List<Integer> queue = new ArrayList<Integer>();	private static boolean [] isVisited;	private static int maxShares = 0;	private static int firstDayMaxShares;	private static int day = 0;	private static int shares = 0;	public static void main(String[] args){		Scanner in = new Scanner(System.in);		/*		 *	gets the size of david's social network (first integer on the first line)		 */		cardinality = in.nextInt();				/*		 *	sets size of the social network and isVisited arrays to the amount of people in the social network		 */		adjacency = new int[cardinality][];		isVisited = new boolean[cardinality];		/*		 *	stores all friends of the people in the social network in an array in an array		 */		for (int i = 0; i < cardinality; i++) {			int degree = in.nextInt();			int[] friends = new int[degree];			for (int j = 0; j < friends.length; j++)				friends[j] = in.nextInt(); 			adjacency[i] = friends;		}		/*		 *	gets last integer of the input file (index of David)		 */		indexDavid = in.nextInt();		setAllFalse();		startSharing();		System.out.println("Max shares : " + maxShares);		System.out.println("First day to achieve max shares : " + firstDayMaxShares);	}	private static boolean startSharing() {		if (adjacency[indexDavid].length == 0)			return true;		addAdjacentVerticesToQueue(indexDavid);		while (doesEveryoneKnow() == false){			day++;			shares = 0;			int queueSize = queue.size();			for (int i = 0; i < queueSize; i++){				System.out.println(queueSize);				if (isVisited[i] == false)					shareWithAdjacentVertex(queue.get(i));				addAdjacentVerticesToQueue(queue.get(i));			}			for (int j = 0; j < queueSize; j++)				queue.remove(j);			if (shares > maxShares) {				maxShares = queueSize;				firstDayMaxShares = day;			}		}		return true;	}	private static void shareWithAdjacentVertex(int index) {		for (int i = 0; i < adjacency[index].length; i++) {			isVisited[adjacency[index][i]] = true;			shares++;		}	}	private static void addAdjacentVerticesToQueue(int index) {		for (int i = 0; i < adjacency[index].length; i++) {			queue.add(adjacency[index][i]);		}	}	private static boolean doesEveryoneKnow() {		for (int i = 0; i < isVisited.length; i++) 			if (isVisited[i] == false) return false;		return true;	}	private static void setAllFalse() {		for (int i = 0; i < isVisited.length; i++)			isVisited[i] = false;	}	}

    class Vertex    {        public bool Visited { get; set; }        public List<int> Edges { get; set; }    }

[wolfsinner]

Sigh. I have spent a whole day trying to solve this problem, but I still have not found the correct solution. I have made some good progress though. There are still some weird things I do not understand going on. My brain gave up, I should probably do something else for a few hours. If someone would want to review the code I have written so far, go ahead, maybe you can find a way to help me, that would be nice. Also, please give suggestions on how to improve my code, I assume it is not that well written.

 

I can tell you were reading up on graph theory considering your variable naming terminology. That's awesome.

I could tell you what is wrong with your code, but instead I'll tell you how to make it better, simpler, and more of a breadth-first search implementation. You don't need most of your functions.

 

The general form for BFS is the following:

Queue queue = createQueue();boolean [] visited = new boolean[vertexCount];root = vertexOrigin();queue.push(root);visited[root] = true; while(!queue.isEmpty()){    Vertex v = queue.pop();    TREAT(v);    foreach(Vertex w in v.outAdjacentVertices()) //in this case, the outAdjacentVertices would be that person's friends        if(!visited[w]){            queue.push(w);            visited[w] = true;        }}

The TREAT(vertex) area is where you would work your magic. There are two ways to do this: you would either do 1 day for each iteration of the loop by fully emptying the queue and counting that, then filling the queue again with new vertices, which I personally find less pretty, or you would create some lightweight structure that could identify in which day that person was told of the blueprint. Since Queue is a FIFO (First In, First Out) structure, you would get them in order and could easily count the people for each day.

 

P.S. - There is a Queue<T> interface for representing a queue, and you can use a LinkedList<T> as the concrete type:

Queue<T> queue = new LinkedList<T>();queue.add(T); //pushes an element to the queuequeue.remove(); //pops an element from the queue

Hopefully that helps. If you really want to keep working on your current code, your main problems are:

• There may not be a path from the root to every other Node, and in such a case doesEveryoneKnow() will never return true.
• You're adding adjacent vertices to the queue regardless of whether they've been visited or not.
• You're counting David.
• In line 68 you might mean queue.get(i).

But I'd recommend you change it.

By the way, my code in Java, for reference, is the following:

import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; class Main {     public static void main(String [] args) throws IOException{                    Scanner in = new Scanner(System.in);          int p = in.nextInt();          ProblemGraph t = new ProblemGraph(p);          int [] tmp;          for(int i = 0 ; i < p ; i++){               int n = in.nextInt();               tmp = new int[n];               for(int k = 0 ; k < n ; k++){                    tmp[k] = in.nextInt();               }               t.addFriends(i, tmp);          }                         int david = in.nextInt();          in.close();          tmp = t.solve(david);          System.out.println(tmp[0]);          System.out.println(tmp[1]);               }} class ProblemGraph {     private int [][] matrix;     private int numVertices;          public ProblemGraph(int vertices) {          this.numVertices = vertices;          this.matrix = new int[vertices][];     }          public void addFriends(int id, int[] friends){          this.matrix[id] = friends;     }          public int[] solve(int source){          int [] ret = new int[2];          this.bfs(ret, source);          return ret;     }          private void bfs(int [] ret, int source){          boolean seen[] = new boolean[this.numVertices];          Queue<Person> queue = new LinkedList<Person>();          int currDay = 0;          int dayCount = 0;          queue.add(new Person(source, 1));          Person p;          do{               p = queue.remove();               int index = p.id;               if(p.day > currDay){                    if(dayCount > ret[0]){                         ret[0] = dayCount;                         ret[1] = currDay;                    }                    currDay++;                    dayCount = 0;               }               for (int i = 0; i < this.matrix[index].length; i++){                    if (!seen[this.matrix[index][i]]){                         queue.add(new Person(this.matrix[index][i], currDay+1));                         seen[this.matrix[index][i]] = true;                         dayCount++;                    }               }           } while (!queue.isEmpty());     }               class Person {          public int id;          public int day;          public Person(int id, int day){               this.id = id;               this.day = day;          }     }} 

[Nuluvius]

An observation about the raw data: Two pieces of redundant information; the Vertex count and the Edge count. I actually striped these out once I had read in the raw text.

 

While I know full well they help for speed, my point is they can be inferred.

[Nuluvius]

Well I didn't use TDD for this one (I was naughty). I did have two lists but I liked the queue better All 5 files are hit at once.

 

AddResult is simply reentrant to the UI context thread where it add the object to an ObservableCollection for the view.

        private void ProcessFiles()        {            IsBusy = true;            UpdateCommands();            Task.Run(                () => Task.WaitAll(Directory.GetFiles(InputDirectory, "*.txt").Select(f => Task.Run(() =>                    {                        var sharingCount = 0;                        var sharingDay = 0;                        var queue = new Queue<Vertex>();                        var result = new Result { Index = f };                                                var graph = ParseRawFile(f, _cs.Token);                         queue.Enqueue(graph.First(v => v.Visited));                                                                       while (queue.Count > 0)                        {                            _cs.Token.ThrowIfCancellationRequested();                            var vertix = queue.Dequeue();                            if (vertix.DayVisited > sharingDay)                            {                                if (sharingCount > result.MaximumSharingDay)                                {                                    result.MaximumSharingDay = sharingCount;                                    result.FirstDayOfMaximumSharing = sharingDay;                                }                                sharingDay++;                                sharingCount = 0;                            }                            foreach (var linkVertix in vertix.Edges.Select(edge => graph[edge]).Where(linkVertix => !linkVertix.Visited))                            {                                _cs.Token.ThrowIfCancellationRequested();                                linkVertix.Visited = true;                                linkVertix.DayVisited = sharingDay + 1;                                queue.Enqueue(linkVertix);                                sharingCount++;                            }                        }                        AddResult(result);                    }, _cs.Token)).ToArray()), _cs.Token).ContinueWith(                        _ =>                            {                                IsBusy = false;                                UpdateCommands();                            });        } 

        private static List<Vertex> ParseRawFile(string fileName, CancellationToken token)        {            token.ThrowIfCancellationRequested();            var rawLines = File.ReadAllText(fileName).Trim().Split(new[] { Environment.NewLine }, StringSplitOptions.None).ToList();            var rootIndex = Convert.ToInt32(rawLines.Last());            // Remove dave's index            rawLines.RemoveAt(rawLines.Count - 1);            // Remove people count            rawLines.RemoveAt(0);            var vertices = new List<Vertex>();            for (var i = 0; i < rawLines.Count; i++)            {                token.ThrowIfCancellationRequested();                var network = rawLines[i].Split(' ').Select(int.Parse).ToList();                // Remove sub people count                network.RemoveAt(0);                var root = i == rootIndex;                vertices.Add(new Vertex { Edges = network, Visited = root, DayVisited = root ? 1 : 0 });            }            return vertices;        } 

    class Vertex    {        public int DayVisited { get; set; }        public bool Visited { get; set; }        public List<int> Edges { get; set; }    } 

[wolfsinner]

An observation about the raw data: Two pieces of redundant information; the Vertex count and the edge count. I actually striped these out once I had read in the raw text.

 

While I know full well they help for speed, my point is they can be inferred.

 

I like redundancy, when appropriate, for the sake of structure. Especially in problem solving. You'll be seeing redundancy in every problem's input, sorry.

[Maximation]

My solution now provides plausible numbers as an output, it however appears those numbers are incorrect. But I have no idea what makes them incorrect (maybe I have submitted them in the wrong way again).

Here are my solutions :

output 1

0

0

output 2

46

3

output 3

74

2

output 4

1458

8

output 5

1473

11

 

And here is my code :

(it is a mess, imo)

import java.util.*;public class Main {	private static int cardinality;	private static int indexDavid;	private static int[][] adjacency;	private static Queue<Integer> queue = new LinkedList<Integer>();	private static boolean [] isVisited;	private static int maxShares = 0;	private static int firstDayMaxShares;	private static int currentDay = 0;	private static int sharesCurrentDay;	public static void main(String[] args){		Scanner in = new Scanner(System.in);		/*		 *	gets the size of david's social network (first integer on the first line)		 */		cardinality = in.nextInt();				/*		 *	sets size of the social network and isVisited arrays to the amount of people in the social network		 */		adjacency = new int[cardinality][];		isVisited = new boolean[cardinality];		/*		 *	stores all friends of the people in the social network in an array in an array		 */		for (int i = 0; i < cardinality; i++) {			int degree = in.nextInt();			int[] friends = new int[degree];			for (int j = 0; j < friends.length; j++)				friends[j] = in.nextInt(); 			adjacency[i] = friends;		}		/*		 *	gets last integer of the input file (index of David)		 */		indexDavid = in.nextInt();		setAllFalse();		bfs();		System.out.println("Max shares : " + maxShares);		System.out.println("First day to achieve max shares : " + firstDayMaxShares);	}	private static void bfs() {		Queue<Integer> tmp = new LinkedList<Integer>();		queue.add(indexDavid);		isVisited[indexDavid] = true;		while (!queue.isEmpty()) {			currentDay++;			sharesCurrentDay = 0;			for (int i = 0; i < queue.size(); i++) {				isVisited[queue.peek()] = true;				for (int j = 0; j < adjacency[queue.peek()].length; j++) {						sharesCurrentDay++;						}				tmp.add(queue.remove());			}			while (!tmp.isEmpty()) {				if (tmp.size() > 1) {					for (int k = 0; k < adjacency[tmp.peek()].length; k++) {						if (adjacency[tmp.peek()].length != 0) {							if (!isVisited[adjacency[tmp.peek()][k]])			 					queue.add(adjacency[tmp.peek()][k]);			 				tmp.remove();			 			} 			 			else 			 				tmp.remove();					}				}				else if (tmp.size() == 1) {					if (adjacency[tmp.peek()].length != 0) {						if (!isVisited[adjacency[tmp.peek()][0]])							queue.add(adjacency[tmp.peek()][0]);						tmp.remove();					}					else 						tmp.remove();				}			} 			if (sharesCurrentDay > maxShares){				maxShares = sharesCurrentDay;				firstDayMaxShares = currentDay;			}		}	}	private static void setAllFalse() {		for (int i = 0; i < isVisited.length; i++)			isVisited[i] = false;	}	}

[wolfsinner]

My solution now provides plausible numbers as an output, it however appears those numbers are incorrect. But I have no idea what makes them incorrect (maybe I have submitted them in the wrong way again).

Here are my solutions :

output 1

0

0

output 2

46

3

output 3

74

2

output 4

1458

8

output 5

1473

11

 

And here is my code :

(it is a mess, imo)

 

Only your first output is correct. You are making a few things wrong. It's pretty close though.

• You're setting isVisited to true when you remove from queue. You actually should do it when you add to the queue, or else you may end up counting people more than once (especially in the sneaky case of people being friends to themselves haha).
• You're always counting every friend as a "person shared with", even if they've already been visited. Count them in the same place where you set isVisited of that person to true.
• I recommend you don't use peek() of the Queue<T> interface, unless it is necessary (very rarely it is). The NullPointerException it was probably producing confused you and led you to write the else at line 85. Use the following general form when emptying stacks:

  while(!queue.isEmpty()){     elem = queue.remove();    //from here on out use elem to refer to the element at the head of the queue}

Hopefully that helped. I'd recommend you try to apply those notes, and understand them (if you don't understand one of the notes please tell me). Here's a version of your bfs() code which should work:

private static void bfs() {      Queue<Integer> tmp = new LinkedList<Integer>();      queue.add(indexDavid);     isVisited[indexDavid] = true;      while (!queue.isEmpty()) {          currentDay++;          sharesCurrentDay = 0;          while(!queue.isEmpty()) {               tmp.add(queue.remove());          }           int n;          while (!tmp.isEmpty()) {               n = tmp.remove();               for (int k = 0; k < adjacency[n].length; k++) {                    if (!isVisited[adjacency[n][k]]){                         isVisited[adjacency[n][k]] = true;                         queue.add(adjacency[n][k]);                         sharesCurrentDay++;                    }               }          }          if (sharesCurrentDay > maxShares){               maxShares = sharesCurrentDay;               firstDayMaxShares = currentDay;          }     }}

[Maximation]

Only your first output is correct. You are making a few things wrong. It's pretty close though.

• You're setting isVisited to true when you remove from queue. You actually should do it when you add to the queue, or else you may end up counting people more than once (especially in the sneaky case of people being friends to themselves haha).
• You're always counting every friend as a "person shared with", even if they've already been visited. Count them in the same place where you set isVisited of that person to true.
• I recommend you don't use peek() of the Queue<T> interface, unless it is necessary (very rarely it is). The NullPointerException it was probably producing confused you and led you to write the else at line 85. Use the following general form when emptying stacks:

  -snip-

Hopefully that helped. I'd recommend you try to apply those notes, and understand them (if you don't understand one of the notes please tell me). Here's a version of your bfs() code which should work:

 

Thanks to everyone who helped me out, I solved the problem. I am learning so much from these exercises, they are amazing!

Thank you very much @wolfsinner , the problems you submit and the great tips you give make me learn a whole lot!

 

Here is my final code :

 

 

EDIT: Hey, I could submit it to the "under 100 line challenge", it is 97 lines

-snip-

import java.util.*;public class Main {	private static int cardinality;	private static int indexDavid;	private static int[][] adjacency;	private static Queue<Integer> queue = new LinkedList<Integer>();	private static boolean [] isVisited;	private static int maxShares = 0;	private static int firstDayMaxShares;	private static int currentDay = 0;	private static int sharesCurrentDay;	public static void main(String[] args){		Scanner in = new Scanner(System.in);		/*		 *	gets the size of david's social network (first integer on the first line)		 */		cardinality = in.nextInt();				/*		 *	sets size of the social network and isVisited arrays to the amount of people in the social network		 */		adjacency = new int[cardinality][];		isVisited = new boolean[cardinality];		/*		 *	stores all friends of the people in the social network in an array in an array		 */		for (int i = 0; i < cardinality; i++) {			int degree = in.nextInt();			int[] friends = new int[degree];			for (int j = 0; j < friends.length; j++)				friends[j] = in.nextInt(); 			adjacency[i] = friends;		}		/*		 *	gets last integer of the input file (index of David)		 */		indexDavid = in.nextInt();		setAllFalse();		bfs();		System.out.println("Max shares : " + maxShares);		System.out.println("First day to achieve max shares : " + firstDayMaxShares);	}	private static void bfs() {		Queue<Integer> tmp = new LinkedList<Integer>();		queue.add(indexDavid);		isVisited[indexDavid] = true;		while (!queue.isEmpty()) {			currentDay++;			sharesCurrentDay = 0;						while (!queue.isEmpty()) {				tmp.add(queue.remove());			}			int indexRemoved;			while (!tmp.isEmpty()) {				indexRemoved = tmp.remove();				for (int i = 0; i < adjacency[indexRemoved].length; i++) {					if (!isVisited[adjacency[indexRemoved][i]]) {						queue.add(adjacency[indexRemoved][i]);						isVisited[adjacency[indexRemoved][i]] = true;						sharesCurrentDay++;					}				}			}			if (sharesCurrentDay > maxShares){				maxShares = sharesCurrentDay;				firstDayMaxShares = currentDay;			}		} 	}	private static void setAllFalse() {		for (int i = 0; i < isVisited.length; i++)			isVisited[i] = false;	}	}

[gauvinic]

Hmm... So I tried the first problem, but have yet to submit an answer as the execution time is ~1 hr. at 10,000,000.

It does solve the example (10,000) correctly, though. Will post code in appropriate thread shortly.

 

With this one, my first submission was wrong due to incorrect interpretation of the input file. After addressing that,

it still gave me incorrect results. Code below (in C++):

#include <vector>#include <fstream>#include <string>#include <sstream>#include <iostream>using namespace std;int main(void) {	vector<vector<int>> personArray;	vector<int> days;	vector<int> toldOnDay;	vector<bool> told;	bool done = false;	int max = 0;	int day = 0;	int pos = 0;	int size = 0;	int David = 0;	int justFoundOut = 0;	char c;	string file = "";	string s = "";	string d = "";	string inputFile = "";	cout << "Enter file to be read here (with ext): ";	cin >> inputFile;	fstream in(inputFile, fstream::in);	// This section reads the file, and generates a vector of vectors that represents the needed information of the file.	while(in.get(c)) 		file += c;	in.close();	for(int i = 0; file[i] != '\n'; i++) {		s += file[i];		pos++;	}	istringstream(s) >> size;	for(int i = 0; i < size; i++) {		vector<int> p;		personArray.push_back(p);		string line = "";		pos++;		for(int k = pos; file[k] != '\n'; k++) {			line += file[k];			pos++;		}		for(int j = 0; j < line.size(); j++) {			string num = "";			int person = 0;				while(j < line.size() && line[j] != ' ' && j < line.size()) {				num += line[j];				j++;			}			istringstream(num) >> person;			if(num != "")				personArray[i].push_back(person);		}	}	for(int i = pos; i < file.size(); i++) 		d += file[i];	istringstream(d) >> David;	for(int i = 0; i < personArray.size(); i++) {		for(int c = 0; c < personArray[i].size() - 1; c++) 			personArray[i][c] = personArray[i][c+1];	}	for(int i = 0; i < personArray.size(); i++) 		personArray[i].pop_back();	// This section stores the number of newly told people in the days vector at position (day - 1).		for(int i = 0; i < size; i++) 		told.push_back(false);	if(David < size) 		told[David] = true;		for(int i = 0; i < personArray[David].size(); i++) {		if(personArray[David][i] != David) {			toldOnDay.push_back(personArray[David][i]);			told[personArray[David][i]] = true;			justFoundOut++;		}	}	days.push_back(justFoundOut);	if(personArray[David].size() == 0 || justFoundOut == 0)		done = true;	if(!done) {		do{						vector<int> temp;			justFoundOut = 0;			for(int i = 0; i < toldOnDay.size(); i++) {				for(int c = 0; c < personArray[toldOnDay[i]].size(); c++) {					if(personArray[toldOnDay[i]][c] < told.size()) {						if(!told[personArray[toldOnDay[i]][c]]) {							justFoundOut++;							temp.push_back(personArray[toldOnDay[i]][c]);							told[personArray[toldOnDay[i]][c]] = true;						}					}				}			}			days.push_back(justFoundOut);			int notTold = 0;			for(int i = 0; i < told.size(); i++) {				if(!told[i])					notTold++;			}			if(notTold == 0)				done = true;			toldOnDay.clear();			toldOnDay = temp;		}while(!done);	}	// Finally, this section searches for the day with the most newly-told people.	for(int c = 0; c < days.size(); c++) {		if(days[c] > max) {			max = days[c];			day = c + 1;		}	}	cout << "Maximum: " << max << endl;	cout << "First Day: " << day << endl;		system("pause");}

[Ciccioo]

-snip-

the algorithm seems right to me

are you sure that the file is parsed correctly? did you submit your results in the correct form? you must only submit the two numbers (max and day) and both of the two lines must end with a carriage return

[gauvinic]

the algorithm seems right to me

are you sure that the file is parsed correctly? did you submit your results in the correct form? you must only submit the two numbers (max and day) and both of the two lines must end with a carriage return

Yup. Manually entered them, hitting enter after each line. Actually though, I could've misread. Will try one more time.

 

Edit: Huh... after 2 resubmissions it worked. All were entered right except last one. Not sure why, all I did between

submissions was take all variable declarations and move them to the top. (Between submission 2 & 3).