prithivMLmods/Coder-Stat
Coder-Stat Dataset Overview The Coder-Stat dataset is a collection of programming-related data, including problem IDs, programming languages, original statuses, and source code snippets. This dataset is designed to assist in the analysis of coding patterns, error types, and performance metrics. Dataset Details Modalities Tabular: The dataset is structured in a tabular format. Text: Contains text data, including source code snippets.… See the full description on the dataset page: https://huggingface.co/datasets/prithivMLmods/Coder-Stat.
3139
1 2<H1><font color="#000">Problem G: </font>Longest Chain</H1>3 4<p>5Let us compare two triples <var>a = (x<sub>a</sub>, y<sub>a</sub>, z<sub>a</sub>)</var> and <var>b = (x<sub>b</sub>, y<sub>b</sub>, z<sub>b</sub>)</var> by a partial order ∠ defined as follows.6<br/>7<center>8<var>a</var> ∠ <var>b</var> ⇔ <var>x<sub>a</sub></var> < <var>x<sub>b</sub></var> and <var>y<sub>a</sub></var> < <var>y<sub>b</sub></var> and <var>z<sub>a</sub></var> < <var>z<sub>b</sub></var>9<br/>10</center>11<br/>12<p>13Your mission is to find, in the given set of triples, the longest ascending series <var>a<sub>1</sub></var> ∠ <var>a<sub>2</sub></var> ∠ ... ∠ <var>a<sub>k</sub></var>.14</p>15 16<H2>Input</H2>17 18<p>19The input is a sequence of datasets, each specifying a set of triples formatted as follows.20</p>21 22<pre>23<var>m</var> <var>n</var> <var>A</var> <var>B</var>24<var>x<sub>1</sub></var> <var>y<sub>1</sub></var> <var>z<sub>1</sub></var>25<var>x<sub>2</sub></var> <var>y<sub>2</sub></var> <var>z<sub>2</sub></var>26...27<var>x<sub>m</sub></var> <var>y<sub>m</sub></var> <var>z<sub>m</sub></var>28</pre>29 30<p>31Here, <var>m</var>, <var>n</var>, <var>A</var> and <var>B</var> in the first line, and all of <var>x<sub>i</sub></var>, <var>y<sub>i</sub></var> and <var>z<sub>i</sub></var> (<var>i</var> = 1, . . . , <var>m</var>) in the following lines are non-negative integers.32</p>33 34<p>35Each dataset specifies a set of <var>m + n</var> triples. The triples <var>p<sub>1</sub></var> through <var>p<sub>m</sub></var> are explicitly specified in the dataset, the <var>i</var>-th triple <var>p<sub>i</sub></var> being (<var>x<sub>i</sub>, y<sub>i</sub>, z<sub>i</sub>)</var>. The remaining <var>n</var> triples are specified by parameters <var>A</var> and <var>B</var> given to the following generator routine.36</p>37 38<pre>39int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;40int r() {41 a = 36969 * (a & M) + (a >> 16);42 b = 18000 * (b & M) + (b >> 16);43 return (C & ((a << 16) + b)) % 1000000;44}45</pre>46 47<p>48Repeated 3<var>n</var> calls of <span>r()</span> defined as above yield values of <var>x<sub>m+1</sub></var>, <var>y<sub>m+1</sub></var>, <var>z<sub>m+1</sub></var>, <var>x<sub>m+2</sub></var>, <var>y<sub>m+2</sub></var>, <var>z<sub>m+2</sub></var>, ..., <var>x<sub>m+n</sub></var>, <var>y<sub>m+n</sub></var>, and <var>z<sub>m+n</sub></var>, in this order.49</p>50 51<p>52You can assume that 1 ≤ <var>m + n</var> ≤ 3 × 10<sup>5</sup>, 1 ≤ <var>A,B</var> ≤ 2<sup>16</sup>, and 0 ≤ <var>x<sub>k</sub>, y<sub>k</sub>, z<sub>k</sub></var> < 10<sup>6</sup> for 1 ≤ <var>k</var> ≤ <var>m + n</var>.53</p>54 55<p>56The input ends with a line containing four zeros. The total of <var>m + n</var> for all the datasets does not exceed 2 × 10<sup>6</sup>.57</p>58 59<H2>Output</H2>60 61<p>62For each dataset, output the length of the longest ascending series of triples in the specified set. If <var>p<sub>i<sub>1</sub></sub></var> ∠ <var>p<sub>i<sub>2</sub></sub></var> ∠ ... ∠ <var>p<sub>i<sub>k</sub></sub></var> is the longest, the answer should be <var>k</var>.63</p>64 65<H2>Sample Input</H2>66<pre>676 0 1 1680 0 0690 2 2701 1 1712 0 2722 2 0732 2 2745 0 1 1750 0 0761 1 1772 2 2783 3 3794 4 48010 0 1 1813 0 0822 1 0832 0 1841 2 0851 1 1861 0 2870 3 0880 2 1890 1 2900 0 3910 10 1 1920 0 0 093</pre>94 95<H2>Output for the Sample Input</H2>96<pre>9739859911003101</pre>