Rrerku

Test whether all array elements are factors of a number

Is it important to consider tone, melody, and musical form while writing a song?

Python: next in for loop

What is the word for reserving something for yourself before others do?

Why do falling prices hurt debtors?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

What are these boxed doors outside store fronts in New York?

Writing rule stating superpower from different root cause is bad writing

The use of multiple foreign keys on same column in SQL Server

Prove that NP is closed under karp reduction?

Test if tikzmark exists on same page

How old can references or sources in a thesis be?

Is a tag line useful on a cover?

Theorems that impeded progress

What's the output of a record cartridge playing an out-of-speed record

How could an uplifted falcon's brain work?

What are the differences between the usage of 'it' and 'they'?

Minkowski space

Why do I get two different answers for this counting problem?

What do the dots in this tr command do: tr .............A-Z A-ZA-Z <<< "JVPQBOV" (with 13 dots)

Why doesn't H₄O²⁺ exist?

Is this a crack on the carbon frame?

Can I ask the recruiters in my resume to put the reason why I am rejected?

How is it possible to have an ability score that is less than 3?

Dynamic programming approach for finding perfect square subsequence

Deciding on Sub-Problems for Dynamic ProgrammingSubarray whose (sum × length) is maximumDynamic Programming ApproachDynamic programming: speed of top down vs bottom up approachesWhy is this problem listed as “Dynamic Programming”Are there Dynamic programming speedups for $dp[i]=min_j<i f(a_j, a_i)$Parenthesizing a product using dynamic programmingMaximum Equal Sum K SubsequencesMinimum Number of Integers From a List that Add up to N (Dynamic Programming)Maximum product of contiguous subsequence over $mathbbR$

0

$begingroup$

Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.

algorithms

share|cite|improve this question

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Use linear algebra instead.
  $endgroup$
  – Yuval Filmus
  18 hours ago
  

  
  
  
  

add a comment | 

0

$begingroup$

Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.

algorithms

share|cite|improve this question

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Use linear algebra instead.
  $endgroup$
  – Yuval Filmus
  18 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.

algorithms

share|cite|improve this question

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 19 hours ago

besmelbesmel

285

New contributor

besmel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 19 hours ago

besmelbesmel

285

1 Answer
1

active

oldest

votes

2

$begingroup$

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

---

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 cdot a_2 cdots a_i$. The subsequence $a_i,ldots,a_j$ multiplies to a perfect square iff $b_j/b_i-1$ is a perfect square, which happens if the vectors corresponding to $b_i-1$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,ldots,c_ell$. The answer is then $sum_i binomc_i2$.

share|cite|improve this answer

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

besmel is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106546%2fdynamic-programming-approach-for-finding-perfect-square-subsequence%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

---

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 cdot a_2 cdots a_i$. The subsequence $a_i,ldots,a_j$ multiplies to a perfect square iff $b_j/b_i-1$ is a perfect square, which happens if the vectors corresponding to $b_i-1$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,ldots,c_ell$. The answer is then $sum_i binomc_i2$.

share|cite|improve this answer

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

add a comment | 

2

$begingroup$

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

---

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 cdot a_2 cdots a_i$. The subsequence $a_i,ldots,a_j$ multiplies to a perfect square iff $b_j/b_i-1$ is a perfect square, which happens if the vectors corresponding to $b_i-1$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,ldots,c_ell$. The answer is then $sum_i binomc_i2$.

share|cite|improve this answer

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

add a comment | 

$begingroup$

Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.

---

Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 cdot a_2 cdots a_i$. The subsequence $a_i,ldots,a_j$ multiplies to a perfect square iff $b_j/b_i-1$ is a perfect square, which happens if the vectors corresponding to $b_i-1$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,ldots,c_ell$. The answer is then $sum_i binomc_i2$.

share|cite|improve this answer

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

share|cite|improve this answer

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349

answered 17 hours ago

Yuval FilmusYuval Filmus

196k15184349