โŒ

Normal view

There are new articles available, click to refresh the page.
Before yesterdayMain stream

Overcounting Issue in solution Implementation

I was trying to solve [this][1] question.

I tried to come up with the following approach.

First sort all the numbers then iterate from large to small while doing these steps, Suppose the number we are currently iterating is num. Find how many factors of the number num are there in the array. Suppose it is x, then we have Select at least one factor of num total ways to have the number num as the maximum, also we have the remaining (n-x) numbers, which can give Left numbers other choices.

We multiply these two and get the total ways we will get the number num as our answer. So, for each number a[i](from max to min), we have Final Answer for each array element as contribution to answer.

But I am getting wrong answer in Sample Test Case 3 this way. I think I am overcounting somewhere. Here is my code.

#include <bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define MULTI int _T; cin >> _T; while(_T--)
#define el '\n'
#define yes cout<<"YES"<<el
#define no cout<<"NO"<<el
#define f(i,a,b) for(ll i = a; i <= b; i++)
#define fr(i,a,b) for(ll i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)(x).size())

typedef tree<int, null_type, less<int>, rb_tree_tag, 
tree_order_statistics_node_update> pbds; // find_by_order, 
order_of_key
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const ll mod = 998244353;

ll powmod(ll a, ll b, ll p){
   a %= p;
   if (a == 0) return 0;
   ll product = 1;
   while(b > 0){
   if (b&1){    // you can also use b % 2 == 1
        product *= a;
        product %= p;
        --b;
    }
    a *= a;
    a %= p;
    b /= 2;    // you can also use b >> 1
}
    return product;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

ll n;
cin>>n;
vector<ll> a(n);
vector<vector<ll>> factor(1e5+1);
vector<ll> b(1e5+1,0),c(1e5+1,0);
f(i,0,n-1)
{
    cin>>a[i];
    ++c[a[i]];
}
sort(all(a));
f(i,1,1e5)
{
    for(int j=i;j<=1e5;j+=i)
    {
        if(c[j] && c[i])
            factor[j].pb(i);
    }
}
ll z =0;
ll ans = 0;
fr(i,n-1,0)
{
    while(i>=1 && a[i]==a[i-1])
    {
        --i;
    }
    ll temp = 0;
    for(auto it:factor[a[i]])
    {
        if(c[it])
        {
            temp+=c[it];
            c[it]=0;
        }
    }
    z+=temp;
    ans = (ans+((powmod(2,temp,mod)-1)*(powmod(2,n-z,mod)))*(a[i]))%mod;
}
cout<<ans<<el;
}

Where am I overcounting?

I will be thankful for any help!

How do I get all possible orderings of 9 zeros and 9 ones using Python?

I want to end up with a list with 48 620 nested lists, containing 9 zeros and 9 ones in different orders.

from itertools import permutations

print(list(permutations('000000000111111111', r=18)))

I assume the code above works, but every 0 and 1 is treated like an individual symbol, so for every ordering I get tons of repeats:

('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
('0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1')
...

So, basically, how do I shuffle a list in every possible way, excluding repeats?

I tried to use every method from itertools, but I didn't find one that specifically does what i need.

Algorithm to assign balls to baskets

I have a problem in mind and I am sure there is an efficient way to solve it without using brute force. Here is my problem:

I have X balls placed in a room and Y baskets also placed in the room. Each basket have room for an amount of balls in it, can differ from basket to basket. I want to find the combination that minimises the sum of the distances from each ball to its basket.

As an example:

3 Balls (B1-B2-B3), 2 Baskets (Bk1-Bk2) and Bk1 has 2 slots (room for 2 balls) and Bk2 has 1 slot. Combinations possible are: (Bk1[B1-B2] Bk2[B3]) (Bk1[B1-B3] Bk2[B2]) (Bk1[B2-B3] Bk2[B1]). So we can compute the distances: Bk1->B1, Bk1->B2, Bk1->B3, Bk2->B1, Bk2->B2, Bk2->B3. And for each combination we can compute the sum of distance and pick the smallest.

But is this problem a variant of a well known one? With a neat solution already existing? I hope so, and that someone could point me to it.

MYSQL - How can i check if there is one possible combination of value that fits a range

I am trying to run an algorithm to include / exclude a number of appartments depending if there is a total amount of square meters to fit a criteria.

Here's an example with a set of data :

CREATE TABLE lot
( `id` int(11), `surface_dispo` int(11));


INSERT INTO lot
    (`id`, `surface_dispo`)
VALUES
    ('1', '550'),
    ('2', '700'),
    ('3', '850');

Let's say that I want to find every possible combination that would fit between 1500 and 2000 square meters. In that example I should be able to retrieve the combination of lot Nยฐ 2 and 3, but not 1 2 and 3

I have read some topics about recursive fonctions in MYSQL but I couldn't get to convert examples I found because they were too specifically about string concatenation, and not SUM.

Please also note that the SUM of those lots could be with N numbers involved, let's say that i want to find all of the available surfaces between 2000 AND 2500, I should retrieve 1 + 2 + 3.

Thank you in advance for your help, I will provide any further information needed.

loop combination two columns Sums in R

I try to make a column combination by sum in R. It needs to analyse for association order in warehouse.

For example

Raw_table

Order |  SKU  | QTY
\#1    | Banana | 1
\#1    | Apple  | 2
\#1    | Pear   | 1
\#1    | Cherry | 2
\#2    | Banana | 4
\#2    | Apple  | 1
\#2    | Grape  | 1
\#3    | Banana | 2
\#3    | Pear   | 1

Transform table by outbound frequency

Order | Banana | Apple | Pear | Cherry | Grape
\#1    |   1    |   1   |  1   |  1     |
\#2    |   1    |   1   |      |        |  1
\#3    |   1    |       |  1   |        |

make a pair to highest SKU

SKU1   | SKU2  | Free
Banana | Apple | 2
Banana | Pear  | 2
Banana | Cherry| 1
Banana | Grape | 1
Apple  | pear  | 1
Apple  |Cherry | 1
Apple  |Grape  | 1
Pear   |Cherry | 1

Banana pair needs to concentrate to batch or located in warehouse.

I'm a beginner in loop , try to map in purrr, for text, pairwise anything else. i can not find information

i want to know how to solve this pair

I'm used to treat over 10,000 SKU usually

Purrr , pairwise, whatever method i don't mind , i want to solve this matrix

Frequency count and all combination analysis in R?

The following code generates data (source):

# Set the seed for reproducibility
set.seed(123)

# Generate random data
n <- 490
PTSD <- sample(c(1, 2, NA), n, replace = TRUE) #class(PTSD) = "numeric"
ANX <- sample(c(1, 2, NA), n, replace = TRUE) #class(ANX) = "numeric"
DEP <- sample(c(1, 2, NA), n, replace = TRUE) #class(DEP) = "numeric"

# Create the data frame
df <- data.frame(PTSD, ANX, DEP) #class(df) = "data.frame"

# Label the values: 1 = Low, 2 = High
expss::val_lab(df$PTSD) = expss::num_lab("1 Low
                                        2 High")
expss::val_lab(df$ANX) = expss::num_lab("1 Low
                                        2 High")
expss::val_lab(df$DEP) = expss::num_lab("1 Low
                                        2 High")

# Create a list of tables for each variable to count 1s, 2s, and NAs
count_results <- list(
  PTSD = table(df$PTSD, useNA = "ifany"),
  ANX = table(df$ANX, useNA = "ifany"),
  DEP = table(df$DEP, useNA = "ifany")
)

This portion of the code does some frequency count and summarises data:

# Combine the count tables into a single table
count_table <- do.call(rbind, count_results)

# Initialize empty vectors to store results
variable_names <- character()
sample_sizes <- numeric()

# Loop through the test results and extract relevant information
for (variable_name in names(count_results)) {
  sample_sizes <- c(sample_sizes, sum(count_results[[variable_name]]))
  variable_names <- c(variable_names, variable_name)
}

# Create summary data frame
summary_df <- data.frame(
  Variable = variable_names,
  N = sample_sizes
)

# Combine the count table and chi-squared summary table by columns
final_result <- cbind(count_table, summary_df)

# Remove Variable column in the middle of the table
final_result <- subset(final_result, select = -c(Variable))

This portion of the code does what I call "combination analysis" (it is one of the answers of the above mentioned SO thread):

t3 <- c("PTSD","ANX","DEP")

combs <- map(seq_along(t3),\(n)combn(t3,n,simplify = FALSE)) |> flatten()

filts <- parse_exprs(map_chr(combs,\(x)paste0(x ,'== 2',collapse=' & ')))
filtsnames <- parse_exprs(map_chr(combs,\(x)paste0(x ,collapse=' + ')))
names(filts) <- filtsnames

out2 <- map_int(filts,\(x){
  df %>%
    mutate(id = row_number())%>%
    filter(!!(x))%>%
    summarise(
      n = n())
} |> pull(n)
)

enframe(out2)

The last command generates this (which is what was requested by the author of the question):

# A tibble: 7 ร— 2
  name             value
  <chr>            <int>
1 PTSD               167
2 ANX                156
3 DEP                156
4 PTSD + ANX          56
5 PTSD + DEP          52
6 ANX + DEP           51
7 PTSD + ANX + DEP    23

However, when looking into it, the number of combinations is higher than that, namely:

Combination                     n
---------------------------------
PTSD High                      51
PTSD High, ANX Low              1
PTSD High, DEP Low              8
PTSD High, ANX High            48
PTSD High, DEP High            41
PTSD High, ANX Low, DEP Low     1
PTSD High, ANX High, DEP Low    7
PTSD High, ANX Low, DEP High    0
PTSD High, ANX High, DEP High  41
    
ANX High                      245
ANX High, PTSD Low            197
ANX High, DEP Low             100
ANX High, DEP High            145
ANX High, PTSD Low, DEP Low    93
ANX High, PTSD Low, DEP High  104
    
DEP High                      181
DEP High, PTSD Low            140
DEP High, ANX Low              36
DEP High, PTSD Low, ANX Low    36

My question:

  • Assuming there are no missing combinations in the table above, what would be the R code in order to obtain all the combinations and the pertaining frequencies?
โŒ
โŒ