previndexinfonext

code guessing, round #47 (completed)

started at ; stage 2 at ; ended at

specification

due to some contrived scenario we have to find a longest increasing subsequence of a sequence. submissions may be written in any language.

an increasing subsequence of a sequence is a subsequence where the values are strictly increasing:
4, 5, 2, 6, 3, 5

such a subsequence is a longest increasing subsequence if there is no other increasing subsequence that is longer. in the example above, both the bolded and non-bolded parts are longest increasing subsequences, being of length 3.

your challenge, given a sequence of nonnegative integers, is to return any longest increasing subsequence of that sequence. as any language is allowed, there is no fixed API.

results

  1. 👑 LyricLy +7 -2 = 5
    1. Leol22
    2. luatic
    3. Zaya (was mothiganofficial)
    4. Olivia
    5. olus2000
    6. kimapr
    7. TheQwertiest (was Zaya)
    8. Palaiologos
    9. mothiganofficial (was razetime)
    10. razetime (was TheQwertiest)
    11. mqyhlkahu
  2. luatic +7 -2 = 5
    1. Leol22
    2. mothiganofficial
    3. olus2000 (was Olivia)
    4. TheQwertiest (was olus2000)
    5. kimapr
    6. Olivia (was Zaya)
    7. Palaiologos
    8. razetime
    9. LyricLy
    10. Zaya (was TheQwertiest)
    11. mqyhlkahu
  3. kimapr +4 -2 = 2
    1. Leol22
    2. luatic
    3. LyricLy (was mothiganofficial)
    4. olus2000 (was Olivia)
    5. mothiganofficial (was olus2000)
    6. Olivia (was Zaya)
    7. Palaiologos
    8. mqyhlkahu (was razetime)
    9. razetime (was LyricLy)
    10. TheQwertiest
    11. Zaya (was mqyhlkahu)
  4. Olivia +3 -1 = 2
    1. kimapr (was Leol22)
    2. LyricLy (was luatic)
    3. TheQwertiest (was mothiganofficial)
    4. olus2000
    5. Zaya (was kimapr)
    6. mothiganofficial (was Zaya)
    7. Palaiologos
    8. luatic (was razetime)
    9. Leol22 (was LyricLy)
    10. razetime (was TheQwertiest)
    11. mqyhlkahu
  5. TheQwertiest +2 -1 = 1
    1. Leol22
    2. razetime (was luatic)
    3. mqyhlkahu (was mothiganofficial)
    4. Zaya (was Olivia)
    5. Olivia (was olus2000)
    6. luatic (was kimapr)
    7. olus2000 (was Zaya)
    8. Palaiologos
    9. mothiganofficial (was razetime)
    10. kimapr (was LyricLy)
    11. LyricLy (was mqyhlkahu)
  6. razetime +2 -1 = 1
    1. Leol22
    2. kimapr (was luatic)
    3. mqyhlkahu (was mothiganofficial)
    4. olus2000 (was Olivia)
    5. LyricLy (was olus2000)
    6. mothiganofficial (was kimapr)
    7. TheQwertiest (was Zaya)
    8. Palaiologos
    9. luatic (was LyricLy)
    10. Olivia (was TheQwertiest)
    11. Zaya (was mqyhlkahu)
  7. Zaya +1 -0 = 1
    1. kimapr (was Leol22)
    2. TheQwertiest (was luatic)
    3. LyricLy (was mothiganofficial)
    4. mqyhlkahu (was Olivia)
    5. mothiganofficial (was olus2000)
    6. razetime (was kimapr)
    7. Palaiologos
    8. olus2000 (was razetime)
    9. luatic (was LyricLy)
    10. Leol22 (was TheQwertiest)
    11. Olivia (was mqyhlkahu)
  8. olus2000 +2 -2 = 0
    1. Leol22
    2. Zaya (was luatic)
    3. luatic (was mothiganofficial)
    4. Palaiologos (was Olivia)
    5. TheQwertiest (was kimapr)
    6. razetime (was Zaya)
    7. kimapr (was Palaiologos)
    8. mqyhlkahu (was razetime)
    9. LyricLy
    10. Olivia (was TheQwertiest)
    11. mothiganofficial (was mqyhlkahu)
  9. mothiganofficial +0 -1 = -1
    1. olus2000 (was Leol22)
    2. Leol22 (was luatic)
    3. Zaya (was Olivia)
    4. TheQwertiest (was olus2000)
    5. razetime (was kimapr)
    6. Palaiologos (was Zaya)
    7. LyricLy (was Palaiologos)
    8. mqyhlkahu (was razetime)
    9. luatic (was LyricLy)
    10. kimapr (was TheQwertiest)
    11. Olivia (was mqyhlkahu)
  10. mqyhlkahu +0 -3 = -3
    1. Leol22 +0 -6 = -6
      1. kimapr (was luatic)
      2. LyricLy (was mothiganofficial)
      3. luatic (was Olivia)
      4. mothiganofficial (was olus2000)
      5. Palaiologos (was kimapr)
      6. olus2000 (was Zaya)
      7. mqyhlkahu (was Palaiologos)
      8. Olivia (was razetime)
      9. Zaya (was LyricLy)
      10. razetime (was TheQwertiest)
      11. TheQwertiest (was mqyhlkahu)
    2. Palaiologos +0 -7 = -7
      1. mqyhlkahu (was Leol22)
      2. TheQwertiest (was luatic)
      3. kimapr (was mothiganofficial)
      4. Leol22 (was Olivia)
      5. Olivia (was olus2000)
      6. Zaya (was kimapr)
      7. LyricLy (was Zaya)
      8. luatic (was razetime)
      9. olus2000 (was LyricLy)
      10. razetime (was TheQwertiest)
      11. mothiganofficial (was mqyhlkahu)

    entries

    you can download all the entries

    entry #1

    written by Leol22
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    Strictly Increasing Subsequence.sb2 Zip archive data, at least v1.0 to extract, compression method=deflate

    entry #2

    written by luatic
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    LIS.groovy Unicode text, UTF-8 text
      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    /*
        Efficient longest increasing subsequence finding.
        Written for Code Guessing Round 47 (https://cg.esolangs.gay/47/).
        Input: Sequence of integers delimited by spacing, ex.: 4 5 2 6 3 5
        Output: Subsequence in the same format, ex.: 4 5 6
    
        Code may contain minor inconsistencies;
        the author was initially trying to conceal their style (this was for code guessing, after all)
        but then effectively backpedaled on that too.
    
        The author recommends using at least a gigabyte of IDE bloat to have a half-decent Groovy experience.
     */
    
    class BigIntTree implements Iterable<Iterable<Integer>> {
        class Node {
            List<Integer> is
            Node left, right
        }
        Node root
    
        void set(BigInteger k, int i) {
            Node node = root ?= new Node()
            for (int j = k.bitLength() - 1; j > -1; --j)
                node = k.testBit(j) ? (node.right ?= new Node()) : (node.left ?= new Node())
            (node.is ?= []).add(i)
        }
        // Breadth-first traversal of the tree gives lets us traverse the keys in sorted order
        // in linear time in the total number of digits in the input
        @Override
        Iterator<Iterable<Integer>> iterator() {
            List<Node> lvl = root == null ? [] : [root]
            int i = 0
            return new Iterator<Iterable<Integer>>() {
                @Override
                boolean hasNext() {
                    return !lvl.isEmpty()
                }
    
                @Override
                Iterable<Integer> next() {
                    List<Integer> vs
                    do {
                        vs = lvl.get(i).is
                        if (++i >= lvl.size()) {
                            List<Node> nlvl = []
                            for (nd in lvl) {
                                if (nd.left != null) nlvl.add(nd.left)
                                if (nd.right != null) nlvl.add(nd.right)
                            }
                            lvl = nlvl
                            i = 0
                        }
                    } while (vs == null)
                    return vs
                }
            }
        }
    }
    
    class Subseq {
        class Node {
            int i
            Node prev
    
            Node(int i, Node prev) {
                this.i = i
                this.prev = prev
            }
        }
        int len
        Node root
        static Subseq EMPTY = new Subseq()
    
        Subseq() {}
    
        Subseq(Subseq p, int i) {
            len = (p == null ? 0 : p.len) + 1
            root = new Node(i, p.root)
        }
    
        BigInteger[] apply(BigInteger[] seq) {
            def res = new BigInteger[len]
            def node = this.root
            for (def i = len - 1; i > -1; i--) {
                res[i] = seq[node.i]
                node = node.prev
            }
            return res
        }
    }
    
    class SegmentTree {
        class Node {
            Subseq subseq = Subseq.EMPTY
            Node left, right
    
            Node(int n) {
                assert (n > 0)
                if (n == 1) return
                def mid = n >> 1
                left = new Node(mid)
                right = new Node(n - mid)
            }
            // Get best subseq s with max(s) <= n
            Subseq get(int w, int n) {
                assert n <= w
                if (w == n)
                    return subseq
                def mid = w >> 1
                if (n <= mid)
                    return left.get(mid, n)
                def ssl = left.subseq
                def ssr = right.get(w - mid, n - mid)
                return (ssr.len > ssl.len) ? ssr : ssl
            }
            // Set new best subseq s for max(s) <= n
            void set(int w, int n, Subseq ss) {
                assert n <= w
                if (w == n) {
                    if (ss.len > subseq.len)
                        subseq = ss
                    return
                }
                if (ss.len > subseq.len)
                    subseq = ss
                def mid = w >> 1
                if (n <= mid) {
                    left.set(mid, n, ss)
                    return
                }
                // Note: We can't install this for left, since left has a stricter bound
                right.set(w - mid, n - mid, ss)
            }
        }
        Node root
        int n
    
        SegmentTree(int n) {
            root = new Node(this.n = n)
        }
    
        Subseq get(int n) {
            return root.get(this.n, n)
        }
    
        Subseq set(int n, Subseq ss) {
            return root.set(this.n, n, ss)
        }
    }
    
    static BigInteger[] solve(BigInteger[] seq) {
        if (seq.length == 0) return new BigInteger[0]
        def t = new BigIntTree()
        for (int i = 0; i < seq.length; ++i)
            t.set(seq[i], i)
        // Remove gaps in the ordering.
        // This is important for achieving good time complexity.
        int o = 0
        def ordinals = new int[seq.length]
        for (is in t) {
            ++o
            for (i in is)
                ordinals[i] = o
        }
        // Do the "greedy" / "dynamic programming" solving
        // using a segment tree of best subsequences for upper bounds of the last element.
        def st = new SegmentTree(o)
        for (int i = 0; i < ordinals.length; ++i) {
            def n = ordinals[i]
            def ss = n == 1 ? Subseq.EMPTY : st.get(n - 1)
            st.set(n, new Subseq(ss, i))
        }
        return st.get(o).apply(seq)
    }
    
    static BigInteger[] read() {
        def sc = new Scanner(System.in)
        List<BigInteger> s = []
        while (sc.hasNext())
            s << new BigInteger(sc.next())
        return s.toArray(new BigInteger[s.size()])
    }
    
    static void write(BigInteger[] subseq) {
        print(subseq[0])
        for (int i = 1; i < subseq.length; i++) {
            print(" ")
            print(subseq[i])
        }
        println()
    }
    
    static void main(String[] args) {
        write(solve(read()))
    }
    
    /*
        Runtime analysis:
    
        Let the input be a sequence of n numbers encoded in some base
        (say, binary, or decimal, with at least one digit per number), delimited by some delimiter.
        Then the length of the input is O(m), where m is the total count of digits in the input (in any fixed base).
        Constructing the prefix tree to sort the numbers is O(m) then,
        as is traversing the prefix tree in level-order (breadth-first, left to right);
        replacing numbers with their ordinals is O(m) as well
        (incrementing the ordinal o would be amortized constant time even if o were a bigint).
    
        For each distinct ordinal, there needs to be a distinct number in the input.
        To encode k distinct numbers, you need Θ(log(k)) bits (on average) for each number.
        This implies an input length of Θ(n log(k)) (in bits, bytes, characters, whatever, as long as it's fixed size).
        (This also imposes an upper bound of O(log n) on the length of each ordinal in bits,
        which is why this implementation elects to represent ordinals as "just integers":
        larger sequences couldn't be represented using Java data structures anyways.)
    
        The next step maintains a "segment tree" which maps maxima to longest subsequences
        using only elements encountered so far (a prefix of the sequence).
        Since the largest value is the largest ordinal, this segment tree has depth log(k).
        For each element in the sequence, one get and set operation are issued.
        Since these operations can both easily be seen (*) to be O(log(k)),
        we obtain O(n log(k)), which is true linear time in the input size (in bits, not in integer registers).
    
        (*) For a simplified analysis, assume a perfect binary segment tree (that is, k is a power of two).
        We presume big integers (which this implementation does not use for aforementioned reasons,
        but which are nevertheless relevant for runtime analysis).
        Then the comparison `w == n` would not be constant time,
        but for each bit it has to compare, it saves having to dive a layer deeper, so it is fine.
        Since we split perfectly in the middle, `n <= mid` would only have to look at the most significant bit.
        `w - mid` / `n - mid` effectively just removes that most significant bit, thus is also constant time.
    
        A proof of correctness will be supplied when the author finds the time and motivation.
        For now, you will have to take the author's "trust me bro" for it.
    
        Exercises left to the reader:
    
        * Test this thoroughly to convince yourself of the correctness.
        * Constant-factor optimization of the binary tree / prefix tree:
          "Compress" long paths of multiple bits (trie -> patricia tree)
        * Constant-factor optimization of the segment tree:
          Store it in an array, avoids many heap allocations, improves cache locality.
        * Rewrite this in a "better" programming language.
     */
    

    entry #3

    written by mothiganofficial
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    longest increasing subsequence.js ASCII text, with CRLF line terminators
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    console.log("guess the api lmfao")
    
    a = prompt().split(" ");
    b = [];
    c = 0;
    
    while (c < a.length) {
    	if (a[c] != "") {
    		b.push(a[c]);
    	};
    	c++;
    };
    
    d = 0;
    e = [];
    
    while (d < b.length) {
    	f=Number(b[d]);
    	if (/^[0-9]*$/.test(f)) {
    		e.push(f);
    	};
    	d++;
    };
    
    var f = function(g) {
    	if (g.length == 0) {
    		return [[]];
    	} else if (g.length == 1) {
    		return [g];
    	} else {
    		h = f(g.slice(1));
    		i = 0;
    		j = [];
    		while (i < h.length) {
    			if (g[0] < h[i][0]) {
    				j.push([g[0]].concat(h[i]));
    			};
    			i++;
    		};
    		j.push([g[0]]);
    		return h.concat(j);
    	};
    };
    
    k = f(e);
    l = 0;
    m = 0;
    
    while (l < k.length){
    	if (k[l].length > m) {
    		m = k[l].length;
    	}
    	l++;
    }
    
    n = 0;
    o = [];
    
    while (n < k.length){
    	if (k[n].length == m) {
    		o.push(k[n]);
    	}
    	n++;
    };
    
    p = 0;
    while (p < o.length) {
    	q = 0;
    	while (q < o[p].length){
    		process.stdout.write(o[p][q].toString()+" ");
    		q++;
    	};
    	p++;
    	console.log("|");
    };
    

    entry #4

    written by Olivia
    submitted at
    2 likes

    guesses
    comments 0

    post a comment


    Lis.pdf version 1.5

    entry #5

    written by olus2000
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    entry.tfl ASCII text
    1
    2
    3
    4
    5
    DZ|SD|E|CDD
    r3_iEi|fiChtrf(fhi)t
    l2_ZE|Z_Z|SxSylxy|_EE|E_Z|C_xC_ylxy
    m2yx[1Zy|Ex](lxy)
    ^1xrCE(rmE(r[2naC(Cn(rmE(r[2Chta[1ZC(Cht)a|Ea](lhn)|aECEa]Ea)))a]Ex))
    

    entry #6

    written by kimapr
    submitted at
    2 likes

    guesses
    comments 0

    post a comment


    cpp.cpp.cpp ASCII text
      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
       #include <condition_variable>
     #include <scoped_allocator>
    #include <initializer_list>
    #include <source_location>
    #include <memory_resource>
     #include <unordered_map>
       #include <unordered_set>
          #include <system_error>
             #include <shared_mutex>
                #include <forward_list>
                    #include <string_view>
                         #include <type_traits>
                             #include <stacktrace>
                                  #include <inttypes.h>
                                       #include <stop_token>
                                           #include <filesystem>
                                                #include <spanstream>
                                                    #include <syncstream>
                                                       #include <functional>
                                                          #include <cinttypes>
                                                             #include <stdexcept>
                                                               #include <streambuf>
                                                                #include <execution>
                                                                #include <algorithm>
                                                                #include <semaphore>
                                                               #include <typeindex>
                                                             #include <exception>
                                                          #include <locale.h>
                                                       #include <limits.h>
                                                    #include <iterator>
                                                #include <wctype.h>
                                           #include <stdfloat>
                                       #include <charconv>
                                  #include <optional>
                             #include <signal.h>
                         #include <expected>
                    #include <assert.h>
                #include <setjmp.h>
             #include <concepts>
          #include <stdint.h>
       #include <stddef.h>
     #include <typeinfo>
    #include <stdarg.h>
    #include <valarray>
    #include <stdlib.h>
     #include <string.h>
       #include <iostream>
          #include <csetjmp>
             #include <cassert>
                #include <cwctype>
                    #include <compare>
                         #include <variant>
                             #include <cstdlib>
                                  #include <cstddef>
                                       #include <float.h>
                                           #include <ctype.h>
                                                #include <cstring>
                                                    #include <cstdarg>
                                                       #include <csignal>
                                                          #include <errno.h>
                                                             #include <sstream>
                                                               #include <fstream>
                                                                #include <stdio.h>
                                                                #include <utility>
                                                                #include <numeric>
                                                               #include <climits>
                                                             #include <codecvt>
                                                          #include <version>
                                                       #include <cstdint>
                                                    #include <barrier>
                                                #include <ostream>
                                           #include <wchar.h>
                                       #include <uchar.h>
                                  #include <numbers>
                             #include <istream>
                         #include <iomanip>
                    #include <complex>
                #include <clocale>
             #include <string>
          #include <cwchar>
       #include <vector>
     #include <limits>
    #include <locale>
    #include <cstdio>
    #include <cctype>
     #include <cuchar>
       #include <ranges>
          #include <random>
             #include <iosfwd>
                #include <format>
                    #include <atomic>
                         #include <bitset>
                             #include <cfloat>
                                  #include <chrono>
                                       #include <future>
                                           #include <math.h>
                                                #include <thread>
                                                    #include <time.h>
                                                       #include <cerrno>
                                                          #include <fenv.h>
                                                             #include <memory>
                                                               #include <mutex>
                                                                #include <cfenv>
                                                                #include <queue>
                                                                #include <ctime>
                                                               #include <stack>
                                                             #include <deque>
                                                          #include <latch>
                                                       #include <tuple>
                                                    #include <cmath>
                                                #include <array>
                                           #include <regex>
                                       #include <ratio>
                                  #include <list>
                             #include <span>
                         #include <bit>
                    #include <ios>
                #include <new>
             #include <set>
          #include <any>
       #include <map>
     using namespace std;
    // waiter waiter!
    // more sexual transmited dieseses please!!
    typedef struct
    { double val;
      int count;
      int prev;} Linky;
    extern int entry(double *input, int len, double **output)
    { vector<Linky>things={};
      things.push_back(Linky{0,0,0});
      vector<int>thing_index={};
      unordered_map<double,int>maxlens={};
      vector<int*>imaxlens={};
      for(int i=0;i<len;i++)
      maxlens[input[i]]=1;
      for(int i=0;i<len;i++)
      imaxlens.push_back(&maxlens[input[i]]);
      int counter=0;
      int nextgc=1;
      vector<Linky>thingbuf={};
      for(int ii=0;ii<len;ii++)
      { auto x=input[ii];
        thingbuf.push_back(Linky{x,1,-1});
        counter++;
        Linky v;
        things[0].val=x;
        int mid=upper_bound(thing_index.begin(),thing_index.end(),0,
        [&](int a, int b){return things[a].val>things[b].val;})-thing_index.begin();
        for(int i=mid;i<thing_index.size()&&(v=things[thing_index[i]],1);i++)
        { if(v.count+1>*imaxlens[ii])
          { thingbuf.push_back(Linky{x,v.count+1,thing_index[i]});
            *imaxlens[ii]=v.count+1;
            counter++; }}
        auto oldend=thing_index.size();
        sort(thingbuf.begin(),thingbuf.end(),[&](auto a,auto b){return a.val>b.val;});
        for(auto v: thingbuf)
        thing_index.push_back(things.size()),things.push_back(v);
        inplace_merge(thing_index.begin(),thing_index.begin()+oldend,thing_index.end(),
        [&](int a, int b){return things[a].val>things[b].val;});
        if(counter>nextgc)
        { thing_index.resize(remove_if(thing_index.begin(),thing_index.end(),
          [&](auto i){return things[i].count<maxlens[things[i].val];})-thing_index.begin());
          nextgc+=thing_index.size(); }
        #ifdef ENTRY_DEBUG
        cout<<x<<" -> "<<mid<<" {"<<endl;int n=0;for(auto i:thing_index)
        {auto v=things[i];cout<<"  "<<(n++)<<": ";;for(;;v=things[v.prev])
        {cout<<v.val<<" ";if(v.prev==-1)break;}cout<<"\n";}
        cout<<"}\n";
        #endif
        thingbuf.clear(); }
      Linky bestest=things[1];
      int bestest_len=bestest.count;
      for(auto it=things.begin()+2;it<things.end();it++)
      { if(it->count>bestest_len)
        bestest=*it,
        bestest_len=it->count; }
      double* out;
      int count=0;
      Linky outlinky=bestest;
      for(;;outlinky=things[outlinky.prev])
      { count++;
        if(outlinky.prev==-1)break; }
      out=(double*)malloc(sizeof(double)*count);
      *output=out;
      outlinky=bestest;
      for(int i=0;;outlinky=things[outlinky.prev],i++)
      { if(i>=count) abort();
        out[i]=outlinky.val;
        if(outlinky.prev==-1)break; }
      reverse(out,out+count);
      return count; }
    int main ()
    { vector<double>input=vector<double>();
      for(istream_iterator<double>it
         =istream_iterator<double>(cin);
      it!=istream_iterator<double>()
            ;it++)input.push_back(*it);
      double *out;
      int count=entry(input.data(),input.size(),&out);
      for(int i=0;i<count;i++)cout<<out[i]<<endl;
      free(out);
      return 0; }
    

    entry #7

    written by Zaya
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    code.pharo ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    findLongestIncreasingSubArray
    	| longest current |
    	longest := OrderedCollection new .
    	current := OrderedCollection new .
    	
    	1 to: self size do: [ :i |
    	self from: i to: self size do:
    		[ :n |
    			current isEmpty
    				ifTrue:
    					[ current add: n ]
    				ifFalse:
    					[ n > current last
    						ifTrue: [ current add: n ] ] ] .
    	longest size < current size
    		ifTrue: [ longest := current ] .
    	current := OrderedCollection new ] .
    	^longest
    
    playground.pharo ASCII text
    1
    { 4. 5. 2. 6. 3. 5. } findLongestIncreasingSubarray .
    

    entry #8

    written by Palaiologos
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    mysteriös.bz2 bzip2 compressed data, block size = 900k

    entry #9

    written by razetime
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    f.ts ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    let f1=function(F1:number[]):number[]{let f2:number[][]=[];
    let F2: number[]=[];for(let f3:number=0;f3<F1.length;f3++){
    ;const                                                  F3:
    number                                                    =
    F1[f3];
    let f4                                    :
    number                                   []
    =[];for(let f6=0;f6<f3;f6++){let F4=f2[f6];
    var f5=F1[f6];if(f5<F3&&F4.length>f4.length
    ){;;f4=                                  F4
    ;}};;f2                                   [
    +f3]=f4
    .concat
    ();;;f2
    [(f3)].
    push((
    F3));if
    (f2[f3]
    .length
    >((F2))
    .length
    ){F2=(f2)
    [((f3))];}}
    return (F2);};
    

    entry #10

    written by LyricLy
    submitted at
    0 likes

    guesses
    comments 0

    post a comment


    ans.rs ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    use std::env;
    use std::process::Command;
    
    static mut ZERO: usize = 0;
    
    fn diff<T: PartialEq + Clone>(x: &[T], y: &[T]) -> Vec<T> {
        let mut table: Vec<usize> = vec![0; x.len() * y.len()]; 
        let mut table_value = |i: usize, j: usize| unsafe {
            if i == usize::MAX || j == usize::MAX {
                &mut ZERO
            } else {
                &mut *(&mut table[j + i*y.len()] as *mut usize)
            }
        };
    
        for (j, b) in y.iter().enumerate() {
            for (i, a) in x.iter().enumerate() {
                *table_value(i, j) = if a == b {
                    *table_value(i-1, j-1) + 1
                } else {
                    *table_value(i-1, j).max(table_value(i, j-1))
                };
            }
        }
    
        let mut r = Vec::new();
        let mut i = x.len() - 1;
        let mut j = y.len() - 1;
        while i != usize::MAX && j != usize::MAX {
            if x[i] == y[j] {
                r.push(x[i].clone());
                i -= 1;
                j -= 1;
            } else if table_value(i, j-1) > table_value(i-1, j) {
                j -= 1;
            } else {
                i -= 1;
            }
        }
    
        r.reverse();
        r
    }
    
    pub fn lis(x: &[u32]) -> Vec<u32> {
        let mut v = x.to_owned();
        v.sort();
        v.dedup();
        diff(x, &v)
    }
    
    fn main() -> std::io::Result<()> {
        if cfg!(debug_assertions) {
            // shit.
            Command::new("rustc")
                .arg("-O")
                .arg(file!())
                .spawn()?
                .wait()?;
            Command::new("./ans")
                .args(env::args_os().skip(1))
                .spawn()?
                .wait()?;
            return Ok(());
        }
    
        let input: Vec<u32> = env::args().skip(1).map(|x| x.parse().unwrap()).collect();
        println!("{:?}", lis(&input));
        Ok(())
    }
    

    entry #11

    written by TheQwertiest
    submitted at
    1 like

    guesses
    comments 0

    post a comment


    dir f..fowty seven whispers to self
    wongestincweasingsubsequence.rb Unicode text, UTF-8 text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    uwuifier = [31,14,15,92,65,35,89,79,32,
                38,46,26,43,38,32,79,50,28]
    
    eval $WHATSTHIS          =          %q(
          TIME               =           0;
          LOOP               =            {
          HOST               = uwuifier.com
          ISO_CODE           =           BI
          NATION             =            (
          TIME               =           ).
          COLLECT                        {|
              1. OwO                     |[
              2. OwO                      ,
              3. OwO                      .
          EACH               =            _
          CONS               =         (2).
          ALL                =          ?{|
              1. UwU                      ,
              2. O_O                      |
              3. UwU                      <
              4. O_O                   }]}.
          SELECT             =           {|
              1. U_U                      |
              2. U_U                      .
          LAST               =           };
    
          IF(HOST.EMPTY?) THEN; BREAK; END;
          $RESPOND = HOST.
          FIRST.
          FIRST; TIME += 1               };
          P -P-PLEASE...  $RESPOND
    ).
    gsub(/ .* /,'').
    downcase.
    split*
    ''
    

    entry #12

    written by mqyhlkahu
    submitted at
    0 likes

    guesses
    comments 1
    mqyhlkahu *known at the time as [author of #12]

    i mistakenly incorporated a debugging header which is confidential kindly avoid going through it


    post a comment


    DBG.hpp ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include <iostream>
    #include <vector>
    
    
    template<typename T>
    void print_vec_ (const char *vec_name,
                     std::vector<T> vec)
      {
        std::cout << vec_name << ":\n";
        for (const T &elem : vec)
          {
            std::cout << '\t';
            if (elem == UINTMAX_MAX)
              {
                std::cout << "-1";
              }
            else
              {
                std::cout << ' ' << elem;
              }
            std::cout << '\n';
          }
        std::cout << std::flush;
      }
    
    #define print_vec(v) print_vec_(#v, v)
    
    
    
    void print_loc_ (int src_line,
                     int cur_indx)
      {
        
        std::cout << '[' << src_line;
        if (cur_indx != -1)
          {
            std::cout << ':' << cur_indx;
          }
        std::cout << ']' << std::endl;
      }
    
    #define print_loc(v) print_loc_(__LINE__, v)
    
    
    
    template<typename T>
    void print_val_ (const char* val_name,
                     T           val_vlue)
      {
        std::cout << val_name << ": ";
        std::cout << val_vlue << '\n';
        std::cout << std::flush;
      }
    
    #define print_val(v) print_val_(#v, v)
    
    e ASCII text
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    #include <vector>
    #include <cstdint>
    
    
    namespace cg
      {
        using ui_m_t = std::uintmax_t;
        template<typename t>
        using vec = std::vector<t>;
        typedef vec<ui_m_t> vuimt;
        vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
          {
            // stole an algorithm from wikipedia
            vuimt C;
            vuimt M;
            M.push_back(UINTMAX_MAX);
            ui_m_t Z = 0;
            for (ui_m_t Y = 0; Y < seq.size (); Y++)
              {
                ui_m_t l = 1, h = Z + 1, N;
                while (l < h)
                  {
                    ui_m_t m = l + ((h - l) / 2);
                    if (seq.at(M.at(m)) >= seq.at(Y))
                      {
                        h = m;
                      } // if (seq.at(M.at(m)) >= seq.at(Y))
                    else
                      {
                        l = m + 1;
                      } // else
                  } // while (l < h)
                N = l;
                C.push_back(M.at(N - 1));
                if (N >= M.size())
                  {
                    M.push_back(Y);
                  } // if (N >= M.size())
                else
                  {
                    M[N] = Y;
                  } // else
                if (N > Z)
                  {
                    Z = N;
                  } // if (N > Z)
              } // for (ui_m_t Y = 0; Y < seq.size (); Y++)
            std::vector<std::uintmax_t> H = vuimt( Z, 0 );
            ui_m_t f = M.at(Z);
            for (ui_m_t q = Z - 1; q < UINTMAX_MAX; q--)
              {
                H[q] = seq.at(f);
                f = C.at(f);
              } // for (ui_m_t q = Z - 1; q <= 0; q--)
            return H;
          } // vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
      } // namespace cg