In file called "AinA.txt", an array is given. The array is described in the following manner:
First, a number is given, and it represents how many elements the array has. That is \( 10^5 \).
The following \( 10^5 \) numbers are elements of that array. Now, it is asked to find how many special sub-arrays exist in the given array. Those special sub-arrays have two properties/characteristics. First one, they have to have at least 2 elements. Second one, the first number and the last one of the sub-array have to be the same number. One more example:

Array has 4 elements: 1 2 2 3

Here we have 4 sub-arrays that have exactly one element {1} , {2}, {2} and {3}, but since they have only one element, they aren't qualified.

Next, we have 3 sub-arrays with exactly 2 elements in it, those are: {1, 2}, {2, 2} and {2, 3}. From these, only {2, 2} satisfies both properties, so: one qualified sub-array for now.

With 3 elements, there are 2 sub-arrays: {1, 2, 2} and {2, 2, 3}. Here, both sub-arrays do not satisfy the second property (first and last the same).

Lastly, there is one sub-array with for elements, and it is the actual starting array {1, 2, 2, 3} and he does not satisfy the second condition either.

Conclusion: There is only one special sub-array (and it is {2, 2}) in the initially given array ( {1, 2, 2, 3} ). So the answer for this example is \( \boxed{1} \). I hope I managed to explain it to some extent and I do apologise for my late response and any other unconviniences, I am in a bit of a haste, and away from home. Good luck :)

Can you provide the file APCS.rar through torrent or maybe split the file across different files? Or maybe through some other file-sharing service (i.e., not dropbox) ?

I have a crappy internet connection and Dropbox starts the download in the browser itself and the download fails everytime after about 20 MB of the file is downloaded and the broken download doesn't resume. I have tried downloading it for about 4-5 times by now and it fails every time. :(

Personally, I'd recommend sharing the text file through Pastebin.

@Prasun Biswas if the file is lesser than 20MB are there any problems with downloading via dropbox? The thing is, dropbox is quite handy, for me at least, and if I can use it for smaller files, I would do so.

Never mind, I was able to download it completely later. Nice problem, but I'd like to ask: Does the optimal solution to that problem take 20 secs to run on your PC or on some standard code-testing site? I wrote a code in python that I think takes more or less \(O(n)\) time to execute and its runtime is ~40 secs on my PC.

If the 20 secs is the time to run on your PC, may I know your PC configuration so that I may be able to test the code in such a CPU configuration? Or maybe I can send you my code via email and you can test if it runs in less than 20 secs in your system or not? I'd like to optimize my code as much as possible. Thanks! :)

@Milan Milanic you can test out behavior of dropbox on bad connections by using the "network conditioning" feature in the Chrome browser dev tools. See here for quick instructions.

Oh, I did not know that. The CS committee in my country uses dropbox often, so I figured it is quite good. But hearing this, I will start using Pastebin.

Thanks for the information. I really didn't know. I seek to constantly evolve....

Thank you kindly for the encouragement! I am glad to hear so. I will try to come up with prospectively exciting and fun problem in the future. All the best.

For clarification, on this problem (https://brilliant.org/problems/creating-sorted-arrays/?ref_id=1280451), is the array always in the form of {1, 2, 3, ..., m}?

Two numbers are given: \( m \) and \( n \). \( n \) says that number of elements of the array in the problem is exactly \( n \), while \( m \) says that elements of the array are positive integers lesser or equal to \( m \). Another important thing is that the array must be strictly increasing. Example (in the case I did not cover everything):

n = 2, m = 3: Array = \( a_1 \), \( a_2 \) ; and the the possible values for elements are from set {1, 2, 3}. For this trivial example, answer is \( \boxed{3} \) and those arrays are:

\( A_1 = 1, 2 \)

\( A_2 = 2, 3 \)

\( A_3 = 1, 3 \)

Do you think that I should perhaps provide example for the problem (within the problem itself)?

Thank you that makes much more sense to me now. I think not understanding was just a problem on my part, but you can never go wrong with including an example.

I understand. I thought that especially this may represent a problem, but I haven't provided better explanation for some reason. I will add a better explanation what the \( S \) actually is in the problem, but I will explain it here as well.

The standard EOTR has a rectangle \( ABCD \) for its base and points \( P \) and \( Q \) for its "main peak points", so that the \( PQ \) is so called "peak line". It is said that the length of the following segments: AP, DP, BQ and CQ must be the same. That length is labelled as that \( S \). So, it means that \( AP = DP = BQ = CQ = 5\sqrt{6} \). I edited some minor text in the problem, would You mind checking it out and informing me whether it is more understandable now? :)

Thank You for pointing this out. If you have any more questions, use this FAQ note again. :)

There are 10 million numbers in that file after all. That number of numbers is somewhat necessary to test the optimization of the solver's code. With the right optimization, I think the run time is about 10 seconds.

No special reason to be honest. I just pick the one randomly, .in .dat .bin or with no extension. Probably there is some difference between them, but with my knowledge, I cannot tell for sure.

The issue is that .dat on many systems (Mac OS X, Ubuntu) is often classified as a video file by the OS which makes it mildly difficult to inspect. I think .txt would be more appropriate.

@Silas Hundt
–
Ubuntu on my computer did not show that issue. But anyhow, what is your opinion, should I re-upload the same file with textual extension or it is not necessary?

@Silas Hundt
–
Now, the document has the textual extension, if my eyes are not deceiving me. I am grateful to You, for notifying and advising me. I look forward to our mutual interacting.

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI don't think I understood this question. Can you please rephrase it / explain to me?

Log in to reply

In file called "AinA.txt", an array is given. The array is described in the following manner: First, a number is given, and it represents how many elements the array has. That is \( 10^5 \). The following \( 10^5 \) numbers are elements of that array. Now, it is asked to find how many special sub-arrays exist in the given array. Those special sub-arrays have two properties/characteristics. First one, they have to have at least 2 elements. Second one, the first number and the last one of the sub-array have to be the same number. One more example:

Array has 4 elements: 1 2 2 3

Here we have 4 sub-arrays that have exactly one element {1} , {2}, {2} and {3}, but since they have only one element, they aren't qualified.

Next, we have 3 sub-arrays with exactly 2 elements in it, those are: {1, 2}, {2, 2} and {2, 3}. From these, only {2, 2} satisfies both properties, so: one qualified sub-array for now.

With 3 elements, there are 2 sub-arrays: {1, 2, 2} and {2, 2, 3}. Here, both sub-arrays do not satisfy the second property (first and last the same).

Lastly, there is one sub-array with for elements, and it is the actual starting array {1, 2, 2, 3} and he does not satisfy the second condition either.

Conclusion: There is only one special sub-array (and it is {2, 2}) in the initially given array ( {1, 2, 2, 3} ). So the answer for this example is \( \boxed{1} \). I hope I managed to explain it to some extent and I do apologise for my late response and any other unconviniences, I am in a bit of a haste, and away from home. Good luck :)

Log in to reply

Understoooood!!!! Thank you

Log in to reply

Can you provide the file

`APCS.rar`

through torrent or maybe split the file across different files? Or maybe through some other file-sharing service (i.e., not dropbox) ?I have a crappy internet connection and Dropbox starts the download in the browser itself and the download fails everytime after about 20 MB of the file is downloaded and the broken download doesn't resume. I have tried downloading it for about 4-5 times by now and it fails every time. :(

Personally, I'd recommend sharing the text file through Pastebin.

Log in to reply

@Prasun Biswas if the file is lesser than 20MB are there any problems with downloading via dropbox? The thing is, dropbox is quite handy, for me at least, and if I can use it for smaller files, I would do so.

Log in to reply

Never mind, I was able to download it completely later. Nice problem, but I'd like to ask: Does the optimal solution to that problem take 20 secs to run on your PC or on some standard code-testing site? I wrote a code in python that I think takes more or less \(O(n)\) time to execute and its runtime is ~40 secs on my PC.

If the 20 secs is the time to run on your PC, may I know your PC configuration so that I may be able to test the code in such a CPU configuration? Or maybe I can send you my code via email and you can test if it runs in less than 20 secs in your system or not? I'd like to optimize my code as much as possible. Thanks! :)

Log in to reply

But, never mind that, I will post the file eventually. I am glad that You solved it correctly, you are the first solver! Congrats :)

What I wanted to tell with this reply, finally, do You want to discuss this via Slack?

Log in to reply

Log in to reply

@Milan Milanic you can test out behavior of dropbox on bad connections by using the "network conditioning" feature in the Chrome browser dev tools. See here for quick instructions.

Log in to reply

Oh, I did not know that. The CS committee in my country uses dropbox often, so I figured it is quite good. But hearing this, I will start using Pastebin.

Thanks for the information. I really didn't know. I seek to constantly evolve....

Log in to reply

Yt?

Log in to reply

Log in to reply

I just managed to solve the king's problem. I really liked that problem and would like to thank you for posting it.

Log in to reply

Thank you kindly for the encouragement! I am glad to hear so. I will try to come up with prospectively exciting and fun problem in the future. All the best.

Log in to reply

For clarification, on this problem (https://brilliant.org/problems/creating-sorted-arrays/?ref_id=1280451), is the array always in the form of {1, 2, 3, ..., m}?

Log in to reply

Two numbers are given: \( m \) and \( n \). \( n \) says that number of elements of the array in the problem is exactly \( n \), while \( m \) says that elements of the array are positive integers lesser or equal to \( m \). Another important thing is that the array must be

strictly increasing. Example (in the case I did not cover everything):n = 2, m = 3: Array = \( a_1 \), \( a_2 \) ; and the the possible values for elements are from set {1, 2, 3}. For this trivial example, answer is \( \boxed{3} \) and those arrays are:

Do you think that I should perhaps provide example for the problem (within the problem itself)?

Log in to reply

Thank you that makes much more sense to me now. I think not understanding was just a problem on my part, but you can never go wrong with including an example.

Log in to reply

Hello Milan, in your EOTR problem you state that S=5*sqrt(6). I wonder what you mean by this. Best regards, Wim

Log in to reply

I understand. I thought that especially this may represent a problem, but I haven't provided better explanation for some reason. I will add a better explanation what the \( S \) actually is in the problem, but I will explain it here as well.

The standard

EOTRhas a rectangle \( ABCD \) for its base and points \( P \) and \( Q \) for its "main peak points", so that the \( PQ \) is so called "peak line". It is said that the length of the following segments: AP, DP, BQ and CQ must be the same. That length is labelled as that \( S \). So, it means that \( AP = DP = BQ = CQ = 5\sqrt{6} \). I edited some minor text in the problem, would You mind checking it out and informing me whether it is more understandable now? :)Thank You for pointing this out. If you have any more questions, use this FAQ note again. :)

Best regards

Log in to reply

Why did you provide input data as a

`.dat`

file?Log in to reply

Yeah I agree, and 29MB is a bit too much!!

Log in to reply

There are 10 million numbers in that file after all. That number of numbers is somewhat necessary to test the optimization of the solver's code. With the right optimization, I think the run time is about 10 seconds.

Log in to reply

Log in to reply

Depends on my mood and the time of the day.

No special reason to be honest. I just pick the one randomly, .in .dat .bin or with no extension. Probably there is some difference between them, but with my knowledge, I cannot tell for sure.

Log in to reply

The issue is that

`.dat`

on many systems (Mac OS X, Ubuntu) is often classified as a video file by the OS which makes it mildly difficult to inspect. I think`.txt`

would be more appropriate.Log in to reply

Log in to reply

`.txt`

that has been gzipped so`<file-name>.txt.gz`

.Log in to reply

Log in to reply