duckladydinh's blog

An uneasy problem with Arithmetic Sequences?
By duckladydinh, history, 7 years ago, In English

Updated: Thank everyone for your helps, but it seems that I missed a certain condition of the problem, and my version maybe really just impossible to solve :v, the original problem with that condition is a thousand time easier than this and is straight-forward to CP coders like us (The original problem description was a bit confusing to me :'( )

Hi everyone,

today, I am stuck with a problem. I hope you can help me with it. I think this is a very interesting problem and I am not even sure there exists a deterministic solution to it. The problem is as follows:

" Given n (n <= 1000, but O(n^3) is also fine) distinct integers, group them into sets of at least 4 elements, and each set is an Arithmetic Sequences. "

Example:

Input: 1250, 3748, 6246, 8744, 2493, 4993, 7493, 9993, 2497, 4996, 7495, 9994, 2498, 4997, 7496, 9995, 2499, 4998, 7497, 9996

Output: (1250, 3748, 6246, 8744), (2493, 4993, 7493, 9993), (2497, 4996, 7495, 9994), (2498, 4997, 7496, 9995), (2499, 4998, 7497, 9996)

In this test, if you find the longest sequence first, then the rest will not form any valid sequence anymore.

(Assumption: For the given input, there always exists at least one solution that satisfies the constraints and no number is left)

I have spent hours working on this problem but unfortunately I cannot think of any ideas that will work well in general. What do you think?

Thank you.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What are the bounds on the distinct integers?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the order matter?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it does not matter. The only constraint is that each set is an Arithmetic Sequence of size at least 4.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 29   Vote: I like it -8 Vote: I do not like it

      Can you check the correctness of the following algorithm and the computational complexity of each step:

      1. Sort the distinct integers a[0..n-1].
      2. Use double loops to iterate on the sorted array using the array index pair (i,j), where 0 <= i < j <= n-1, and insert the pair (i,j) to a value set of pairs associated with a key = a[ j ]-a[ i ]. A map STL object map< int, set< pair< int, int > > b can be used. Since all integers are distinct, then all key values should be strictly positive.
      3. Remove from b all invalid entries whose size of the set of pairs is less than 3.
      4. For the remaining valid entries, check for each entry in the map if its value contains a chain of at least three pairs (u1,u2),(u2,u3),(u3,u4), such that u1, u2, u3, and u4 are not used by another chain generated from the other valid entries. Maximal-length chains in each valid entry, where the number of pairs is at least 3 should be candidate Arithmetic Sequences in the final solution.

      Example:

      Let n = 8, and a = { 12, 5, 9, 4, 7, 16, 8, 3 };

      The sorted array is a = { 3, 4, 5, 7, 8, 9, 12, 16 };

      The valid entries of b are:

      key = 1, value = { (0,1), (1,2), (3,4), (4,5) }

      key = 2, value = { (0,2), (2,3), (3,5) }

      key = 3, value = { (1,3), (2,4), (5,6) }

      key = 4, value = { (0,3), (1,4), (2,5), (4,6), (6,7) }

      key = 5, value = { (0,4), (1,5), (3,6) }

      Maximal-length chains:

      key = 2: { 0, 2, 3, 5 }

      key = 4: { 1, 4, 6, 7 }

      The final solution contains two Arithmetic Sequences:

      { 3, 5, 7, 9 }

      { 4, 8, 12, 16 }

      If each distinct integer should not appear in more than one sequence, then a maximal-length chain may not exist in the final solution if one of its members u exists in another chain of a different valid entry.

      A refined algorithm for generating valid entries and candidate sequences with improved computational complexity may exist.

      Hope that helps.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is a greedy, right? May you tried the above example? In my example, if you find the maximum chain that the remaining may not work anymore.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 5   Vote: I like it -8 Vote: I do not like it

          I have just added a note about maximal-length chains. Yes, the final solution may contain only a subset of each maximal-length chain if some distinct integer exists in more than one maximal chain in different valid map entries. In the example above, the maximal chains are disjoint. So, the final solution contains both chains.

          The following is the C++17 code used to compute the valid entries in the example above:

          #include<bits/stdc++.h>
 
 using namespace std;

typedef pair< int, int > pair_t;

typedef set< pair_t >     set_t;

typedef map< int, set_t > map_t;

typedef map_t::iterator   ptr_t;

int main()
{
    int n; cin >> n; int a[ n ]; map_t b; stack< ptr_t > invalid;
   
    for( int i = 0; i < n; i++ )
        cin >> a[ i ];
        
    sort( a, a + n );
    
    for( int j = 1; j < n; j++ )
        for( int i = 0; i < j; i++ )
            b[ a[ j ] - a[ i ] ].emplace( i, j );
            
    for( int i = 0; i < n; i++ )
        cout << a[ i ] << ' ';
            
    for( ptr_t it = b.begin(), iu = b.end(); it != iu; it++ )
        if ( it->second.size() < 3 )
            invalid.push( it );
            
    while( !invalid.empty() )
        b.erase( invalid.top() ), invalid.pop();
        
    for( auto p: b )
    {
        cout << endl << p.first << ": ";
        
        for( auto q: p.second )
            cout << "(" << q.first << "," << q.second << ") ";
    }
}
          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the answer for this test case? 10 1 2 4 8 16 32 64 128 256 612

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This test is not possible, because 612 (the biggest) — 256 (the second biggest) = 356 > any other number, which means it cannot belongs to any arithmetic sequence of length 4. So I guess the answer for it is not valid. (I did not mention, but let's assume that there always exists a partition for the input)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Appending an extra integer 22 to this test case makes it valid with only one possible arithmetic sequence:

    4 10 16 22

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the source of this problem?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was in a private event (not really CP, but rather software engineering, the tests were weak) in my city yesterday, so it is not possible to access it now, but after removing all the crazy engineering part, this is the hardest that I am clueless.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This might not really answer the question. But...

In the contest yesterday (I competed in Vienna), it was also possible that some numbers were actually not part in any sequence. The problem statement therefore was not really well defined, and it leaves room for multiple solutions. Since a number can be part in multiple arithmetic sequences. And it was not clear which sequence should we prefer. E.g. [1250, 2499, 3748, 4997, 6246, 7495, 8744, 9993] would also be a fine solution according to the problem statements.

So I just assumed that there is only one unique answer. Otherwise the statement would had explain how to handle multiple solutions. I just took every pair of numbers a and b, and checked if there is a sequence a, a + d, a + 2 * d, ... with d = b - a. If it was, then I removed it and continued searching. Complexity was .

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you, your assumption is actually correct and your answer is indeed the solution. I have reread the problem and seems that I missed a certain condition that the sequence will cover the whole [start, end].

    (All the time I thought they were having a checker like Codeforces :'( , cannot believe that I was almost stuck at that one, what a shame for me as a CP coder :'( ! )

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No worries. It is quite common in these contests that they are hard to understand and it is often hard to find all hidden information. This year was the first time that I did pretty good (2nd place in Vienna with 5 completed levels). In the last years I always performed way worse, because I also struggled a lot with some problem statements.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply