1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
mamaluj [8]
3 years ago
12

You are hired by a game design company and one of their most popular games is The Journey. The game has a ton of quests, and for

a player to win, the player must finish all the quests. There are a total of N quests in the game. Here is how the game works: the player can arbitrarily pick one of the N quests to start from. Once the player completes a quest, they unlock some other quests. The player can then choose one of the unlocked quests and complete it, and so on.
For instance, let's say that this game had only 4 quests: A, B, C, and D. Let's say that after you complete
• quest A, you unlock quests [B, D). .
• quest B, you unlock quests [C, D).
• quest C, you unlock nothing [ ].
• quest D, you unlock quest [C].
Is this game winnable?
Yes, because of the following scenario:
The player picks quest A to start with. At the end of the quest A, the unlocked list contains [B, D). Say that player chooses to do quest B, then the unlocked list will contain [C, D). Say that player chooses to complete quest C, then the unlocked list will contain quest [D]. Finally, player finishes quest D.
Note that if the player had started with quest C instead of quest A, they would have lost this game, because they wouldn't have unlocked any quest and would be stuck. But the game is still winnable, because there is at least one starting quest which makes the player win. The Journey has N quests, enumerated as {nj, N2, . ng}. We construct a directed graph G for the game, where each node in G represents a quest. If completing quest n; will unlock quest n; then there is a directed edge from n; to n; in the graph. Suppose the total number of edges in the graph is M. (1) We call a quest as a lucky quest if starting from this quest will allow the player to win the game. In the example above, quest A is a lucky quest. Show that (a) All lucky quests are in the same strongly connected component of G, and that (b) Every quest in that component is a lucky quest. [We are expecting a short but rigorous proof for both claims] (2) Suppose there is at least one lucky quest. Give an algorithm that runs in time O(N+M) and finds a lucky quest. You may use any algorithm we have seen in class as subroutine. [We are expecting pseudocode or a description of your algorithm, and a short justification of the runtime]
Computers and Technology
2 answers:
zalisa [80]3 years ago
4 0

Answer:

okay cool brainlest plzzz

Explanation:

Kamila [148]3 years ago
3 0

Answer:

Explanation:

Let's describe the connected part for the very first time.

Component with good connections:-

A semi in any graph 'G' is defined by a way to align element if this can be crossed from the beginning of any link in that pixel or if this can be stated that there is a path across each organized node pair within this subgram.

Consecrated pair means (ni, nj) and (nj, ni) that 2 different pairs would be regarded.

In point a:

We're going to be using contradictions for this segment. They start with the assumption that two lucky journeys are not even in the same strongly interconnected component.

For instance, qi and qj are providing special quests that were not in the very strongly linked element and which implies that, if we start to cross from qi or qi, then qj cannot be approached if we begin to move through qj and as we established if qi or qj is fortunate contests, we may reach any other hunts. Which implies qj from qi or conversely should be reachable. Or we might claim that qi is part of the strongly linked portion of qj or vice versa with this situation.

Consequently, we would not be capable of forming part of a different and strongly linked element for two successful scientists; they must have the same strongly related to the element.

In point b:

Its definition of its strong, line segment indicates that all other searches within such a strongly coordinate system can be made possible from any quest. Because if all quests are accessible from any quest then a lucky search is named, and all other quests can be accessed from any quest in a very coordinated system. So, all contests are fortunate contests in a strongly connected element.

Algorithm:

Build 'n' size range named 'visited' wherein 'n' is the number of graphic nodes that keep records of nodes already frequented.  Running DFS out of every unknown vertex or mark all edges as seen.  The lucky search will be the last unexplored peak.

Psuedo-Code:

Requires this functionality to also be called Solution, it requires 2 reasons as an input, V is a set of objects in graph 'G' and 'G' is a chart itself.

Solution(V, G):

visited[V] = {false}//assign value

for v: 0 to 'V'-1:  //using for loop

if not visited[v]:  //use if block

DFS(v, visited, V, G)  //use DFS method

ans = v //holding value

return ans //return value

You might be interested in
When Twitter is used to gather a large group for a face-to-face meeting it is called
Verdich [7]
The answer is flash mob. They called it flash mob when a large number of people in twitter gather in group for a centralized face to face meeting. In flash mob, people are gathering to be able to create a community that is helping each other or even just talking to each other.
8 0
3 years ago
1. Assume that word is a variable of type String that has been assigned a value . Assume furthermore that this value always cont
s2008m [1.1K]

Answer:

1.word = "George slew the dragon"

startIndex = word.find('dr')

endIndex = startIndex + 4

drWord = word[startIndex:endIndex]

2. sentence = "Broccoli is delicious."

sentence_list = sentence.split(" ")

firstWord = sentence_list[0]

Explanation:

The above snippet is written in Python 3.

1. word is initialized to a sentence.

Then we find the the occurence of 'dr' in the sentence which is assign to startIndex

We then add 4 to the startIndex and assign it to endIndex. 4 is added because we need a length of 4

We then use string slicing method to create a substring from the startIndex to endIndex which is assigned to drWord.

2. A string is assigned to sentence. Then we split the sentence using sentence.split(" "). We split based on the spacing. The inbuilt function of split returns a list. The first element in the list is assigned to firstWord. List uses zero based index counting. So. firstWord = sentence_list[0] is use to get first element.

4 0
3 years ago
What is the difference between a learner’s license and a driver’s license?
kirill115 [55]

privilege to operate a motor vehicle-drivers License

Able to get when 15. Valid for 1 yr. Allows you to drive with a parent in the car. $15. Bring social security and birth certificate to the DLD. Have for 6 months (and do 40 hrs) before getting license.-Learner Permit

4 0
2 years ago
HOWDOYOUDOASPACE?<br><br><br><br> I can't figure out how to make a space on my computer?
e-lub [12.9K]
Depending on the type of keyboard, all spacebars are at the bottom middle of your keyboard and is the largest part of the keyboard.
6 0
3 years ago
Read 2 more answers
#Create a class called Name. Name should have two attributes
prisoha [69]

Answer:

//class Name

class Name {

// attributes gave you 3

String first_name;

String last_name;

int length = 0;

//constructor with 2 parameters

Name(String first_name, String last_name){

}

//methods

public String find_printed_name(){

return first_name + " " + last_name;

}

public void find_sortable_name(){

return last_name + ", " first_name.charAt(0);

}

public static void main(String[] args){

// instantiate the class

Name test_name = new Name("David", "Joyner");

System.out.println(test_name.first_name);

System.out.println(test_name.last_name);

System.out.println(test_name.find_printed_name());

System.out.println(test_name.find_sortable_name());

}

Explanation:

You didn't specify a language so I did it in Java.

You should know how to declare methods in Python.

3 0
3 years ago
Other questions:
  • You should use html elements instead of server controls when
    11·1 answer
  • Ada lovelace designed the first computer
    7·1 answer
  • What is the full form of bcc please tell​
    15·2 answers
  • What are the top and side margins for a letter typed in standard format?
    5·1 answer
  • John Cleaver is the CEO of Tech World, which is a retail store that sells computers, monitors, cameras, televisions and many oth
    6·1 answer
  • Write out the base sequence that is added directly after the primer. In order for Moodle to correctly grade this question, write
    11·1 answer
  • The two major types of system software programs are utility programs and the ________. Select one: A. user interface B. supervis
    13·1 answer
  • What is the advantage of maintaining a list of keywords while creating a design blueprint?
    13·2 answers
  • In windows 10, where would you save the template so it is available in the available templates list in backstage view?.
    10·1 answer
  • Which is true for comments? Group of answer choices The compiler does not generate machine code for comments. The compiler conve
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!