u/marcorubini301

Ifndr, the sizeof expression does not depend on the lambda, otherwise this is legal and works.

I don't use networkx, but looking at the documentation of edge_disjoint paths, it seems like it can take as a parameter any flow solver, and by default it uses "edmonds_karp". Try to pass "network_simplex" as weighted flow solver, and make sure that the graph is weighted and such. Sorry if this is not helpful.

Edge/node disjoint s-t paths found using unweighted flow solvers aren't necessarily "short". An unweighted flow solver will only maximize the number of s-t paths.

So you need to define some other metric you want to minimize, after maximizing the total number of paths.

Some candidates are the number of node/edges taken, or the total length of all paths (if the graph is weighted), or the length of the longest s-t path.

For the first two, just use a weighted flow solver, and assign weights to nodes/edges. For the third metric, it should be NP hard, search "disjoint s-t paths with length constraints"

<semaphore> è stato aggiunto allo standard tramite questo paper http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1135r6.html Essendo un header, per sapere se è stato implementato da un compilatore devi controllare lo stato di implementazione della sua libreria standard, non delle feature core. Per GCC lo trovi qui https://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2020

GCC implementa tutte le feature core di C++20 (eccetto i moduli), ma mancano ancora alcune cose nella libreria. Il sito dice che P1135R6 non è implementato. In realtà, su gcc trunk che ho compilato qualche giorno fa l'header esiste e compila, ma probabilmente è ancora sperimentale.

E' sabato e fino a prova contraria dfv è tra chi ha sbancato di più con i soldi di chi è entrato a 200 $. Sei tra i pochi che fa notare l'ironia della situazione.

Matching moving objects, page 467 of Ahuja, Magnant, Orlin. It easily works if the two node sets have the same cardinality, otherwise you have some more work to do, but it should be a good start

Il problema di oggi è equivalente alla parte 2 del day 16.

Il tuo algoritmo funziona sempre, perchè un grafo bipartito (che ammette un perfect matching) ha un unico perfect matching se e solo se il grafo è un sottografo dell'half graph https://en.wikipedia.org/wiki/Half_graph.Quindi esiste sempre un campo che accetta solo una colonna di ticket, perchè assumiamo che la soluzione sia unica, ed eliminando quel campo ti rimane un altro grafo bipartito con un solo perfect matching, etc.

La mia soluzione in C++.Costruisco un grafo dove ogni vertice è una linea di codice. Due vertici sono collegati con un arco direzionato se è possibile andare dal primo al secondo con un jump oppure nop o incr.

Il costo di un arco è 0 se corrisponde a una istruzione del programma, mentre è 1 se corrisponde a una istruzione flippata (jmp -> nop e viceversa).

Il mio algoritmo trova un percorso dalla istruzione 0 alla N, con costo al massimo 1 (solo un arco usa una istruzione flippata), e aggiunge tutti gli incrementi all'accumulatore man mano che segue il percorso.

#include <deque>
#include <iostream>
#include <vector>

struct edge
{
  int to, acc, cost;
};

auto parse()
{
  auto graph = std::vector<std::vector<edge>>();
  std::string code;
  int value;
  while(std::cin >> code >> value) {
    auto curr = graph.size();
    graph.emplace_back();
    if(code == "jmp" || code == "nop") {
      graph[curr].emplace_back(curr + value, 0, code != "jmp");
      graph[curr].emplace_back(curr + 1, 0, code != "nop");
    } else {
      graph[curr].emplace_back(curr + 1, value, 0);
    }
  }
  return graph;
}

// Finds the shortest path from source to dest, given a graph with weighted edge, and
// edge weighs are binary (0-1).
auto bfs(auto & graph, int source, int dest)
{
  struct node
  {
    int curr;
    int accumulator;
  };
  auto queue01 = std::deque<node>();
  queue01.emplace_back(source, 0);
  while(!queue01.empty()) {
    auto [curr, acc] = queue01.front();
    queue01.pop_front();

    if(curr == dest)
      return acc;

    for(auto [next, incr, cost] : graph[curr]) {
      if(cost == 0)
        queue01.emplace_front(next, acc + incr);
      else
        queue01.emplace_back(next, acc + incr);
    }
    // instead of using a visited set, just erase used edges.
    graph[curr].clear();
  }
  throw std::invalid_argument("dest not reachable");
}

int main()
{
  auto graph = parse();
  std::cout << bfs(graph, 0, graph.size()) << std::endl;
}

Definire e comparare "stili di scrittura" è molto difficile, potresti iniziare facendo una ricerca sulla stilometria https://en.wikipedia.org/wiki/Stylometry.

Più fattibile è comparare il contenuto di due o più testi, gli algoritmi antiplagio usano varianti di w-shingling e locality sensitive hashing. In breve separi i testi in sillabe o brevi parole, e approssimi la distanza di jaccard dei due insiemi di sillabe/parole. Su wikipedia trovi i dettagli

This problem is similar to the "Matching moving objects" problem, which can be solved using minimum cost bipartite matching. It is explained in "Application 12.7 Matching Moving Objects" page 467 of Network Flow Theory, Algorithms and Applications of Ahuja Magnanti Orlin (AMO)

Construct a complete bipartite graph, connect every location of the first set to every location of the second set with a weighted edge (equal to the squared euclidean distance between the two points). The optimal assignment minimizes the sum of the edge weights in the matching. Iterate all edges in the matching with a cost less or equal to a fixed threshold, and merge the two locations.

If you give up the constraint on K, you are looking for a minimum cost 2-factorization. There are different definitions of 2-factor, simple k-factors don't allow taking an edge in multiple subgraphs.

The reduction from simple k-factoring to bipartite matching is explained here https://doi.org/10.1016/j.ipl.2009.02.013

The paper cites previous work on degenerate k-factoring, if you want to allow taking an edge multiple times.

If you assign costs to edges and solve minimum cost bipartite matching instead, you should be able to find a minimum cost 2-factorization. I remember implementing the paper and trying exactly that and it seemed to work.

Working with the K constraint will be hard because it generalizes TSP like other redditors said.

Se a qualcuno interessa il modello matematico, si chiama diagramma di Voronoi, esiste tanta ricerca a riguardo e ha tantissime applicazioni

Esatto, lo studio riguarda la correlazione tra fumo di cannabis / cannabis+tabacco e malattie polmonari. I fumatori di cannabis che non usano il joint sono esclusi, per avere una variabile in meno.

Some authors have suggested an additive effect of tobacco as a cause of lung damage or pneumothorax in cannabis smokers [10,12]. This suggestion is reasonable, given that tobacco smoking increases the risk of pneumothorax up to 20-fold, in a dose-dependent manner [13]. Again, very few studies have explored this association.

​

No distinction was made between marijuana and hashish. Subjects who smoked cannabis in a form other than a joint (e.g. pipes or bongs) were excluded, as well as those who disclosed abuse of inhaled substances other than cannabis or tobacco.

Link al paper: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0230419

Viene analizzata anche l'interazione tra fumo di tabacco e cannabis.

Just brainstorming: since very few of all the 10^n configurations will be used by the user, and I assume they will be mostly similar, you could answer a user query with the target configuration, followed by many other configurations that have low hamming distance from the query. Following queries that don't completely change the configuration will be cached.

You can parameterize the hamming distance based on the total number of possible configurations, and the cost of sending the data. You can also optimize server side calculations by storing the hamming graph of the configuration space.

Il famoso TSP...

g(n) computes log2(n) in O(log2(n))

f3(n) computes g(x) for 0<=log2(x)<n which is the same as 0 <= x < 2^n

so O(f3) = 1 + log2(1) + log2(2) + ... + log2(2^n) = log2((2^n)!) ~ (2^N) * n = O(2^n)

Very cool, thanks for sharing. I love projects involving graph theory

What did the project do? Sounds very interesting

Depending on the constraints and preferences, this problem can be easly solved by flow algorithms (tuple selection problem), or can be NP.

For example, this is how you would solve the problem of assigning courses to (time, room) tuples satisfying that every course exhaustes its duration, every (room, time) tuple is used only once, and taking in consideration (course, room) and (course, time) preference pairs using flow graph modeling

https://hastebin.com/acehaxadox.cpp

Note that I used a variant of Edmonds Karp algorithm to find the minimum cost maximum flow, which is not optimal, this is just a quick example. Key topics to research: maximum flow, minimum cost maximum flow, tuple selection, assignment problem. I suggest studying them on Jeffe's book freely avaiable on http://jeffe.cs.illinois.edu/teaching/algorithms/

It's hard to answer this question. If you host your source code on github, you agree to github's DMCA takedown policy https://help.github.com/en/github/site-policy/dmca-takedown-policy

You are using the wrong approach, dynamic programming is not fast enough (number of elements up to the nth row of the pascal triangle is quadratic).

You need to use Lucas's Therem's corollary that tells you the necessary and sufficient condition for a binomial coefficient (n, m) to be divisible by a prime p. Then you can find the number of elements in the nth row of pascal's triangle that are divisible or not divisible by p in O(1)

Let's say assume that N is a power of 2 for simplicity

N + N/2 + N/4 + N/8 + ... + N/N = 2N

the answer is 14, it is called egg dropping problem