| Show all threads Hide all threads Show all messages Hide all messages |
| Some tests (WA#3 included) | Pat | 1613. For Fans of Statistics | 28 Apr 2023 19:49 | 1 |
My code was failing WA#3 until I got this case working:
4
3 1 1 1
14
1 1 3 1 2 3 2 2 3 2 4 3 3 4 3 4 4 3 2 3 3
1 1 1 1 2 1 2 2 1 1 4 1 2 4 1 3 4 1 3 3 1
> 11000000111111
Other:
8
0 0 1 1 0 0 1 1
35
1 2 1 1 1 1 1 3 1 2 3 1 1 6 1 2 5 1 5 6 1
5 5 1 6 6 1 3 4 1 3 3 1 4 4 1 4 7 1 4 6 1
5 7 1 1 2 0 1 1 0 1 3 0 2 3 0 1 6 0 2 5 0
5 6 0 5 5 0 6 6 0 3 4 0 3 3 0 4 4 0 4 7 0
4 6 0 5 7 0 1 7 2 1 2 2 1 1 2 3 3 2 5 5 2
> 00111100011111111111111100011100000
9
1 1 9 9 1 9 9 1 1
70
1 9 9
1 9 1
1 9 5
1 1 1 2 2 1 3 3 9 4 4 9 5 5 1 6 6 9 7 7 9 8 8 1 9 9 1
1 1 9 2 2 9 3 3 1 4 4 1 5 5 9 6 6 1 7 7 1 8 8 9 9 9 9
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1
1 2 9 2 3 9 3 4 9 4 5 9 5 6 9 6 7 9 7 8 9 8 9 9
1 3 9 1 4 9 1 5 9 1 6 9 1 7 9 1 8 9 1 9 9
3 4 1 2 4 1 3 5 1 2 5 1
3 4 9 2 4 9 3 5 9 2 5 9
1 1 5 1 2 5 1 3 5 2 2 5 3 3 5 8 9 5 7 9 5 9 9 5 6 6 5
3 3 1 3 4 1 3 5 1 4 5 1 5 5 1 5 6 1 5 7 1 6 7 1 7 7 1
> 1101111111110000000001101101101111110111111101111111000000000001111100
7
1 1 1 3 1 1 1
11
4 4 3 3 4 3 4 5 3 3 5 3 1 3 3 5 8 3 3 3 3 5 5 3
4 4 1 1 7 3 1 7 1
> 11110000011 |
| New tests added | Merkurev Oleg [Dandelion] | 1613. For Fans of Statistics | 24 Mar 2023 22:02 | 1 |
New tests were added. All accepted solution were rejudged, ~4% of them lost their accepted status |
| Accepted map<int, set<int> > + lower_bound 0.499 | nadinne | 1613. For Fans of Statistics | 22 Dec 2022 18:52 | 5 |
Edited by author 06.02.2016 13:30
Edited by author 06.02.2016 13:38 My result is 0.1 sec, 700 Kb memory usage.
I used VS 2013 (probably its IO works quicker then gcc), C-style (printf/scanf) IO, sorted vector of pairs (count_of_passengers, city_number). Have a similar solution for Java: HashMap<Integer, TreeSet<Integer>> and floor/ceiling functions. I've got execution time: 0.998 it's kinda funny ))
Edited by author 28.03.2019 12:57 I used the same approach - works much faster 0.218
make sure you are not making unintended copies of the set and use a reference -
std::set<int>& current_set = m[x];
instead of
std::set<int> current_set = m[x]; |
| (Test № 4 here) | Iosif inf-10 | 1613. For Fans of Statistics | 27 May 2022 08:41 | 6 |
This is Test 4
11
1 2 2 1 1 1 2 2 1 2 1
11
1 1 3
1 4 1
2 8 1
10 11 1
1 3 1
2 3 1
3 7 2
4 6 2
5 9 2
11 11 2
10 11 2
Answer is 01111010101
Edited by author 08.02.2013 04:06 |
| sort & lower_bound functions from library is enough | imaginary friend | 1613. For Fans of Statistics | 14 Aug 2018 03:14 | 1 |
|
| Segment tree. | Mahilewets | 1613. For Fans of Statistics | 3 Nov 2017 00:42 | 5 |
Store a sorted array [L...R] in each vertex of your ST, corresponding to [L;R]. Hey!
Do you mind explaining the Segment tree approach a little bit more? I still couldn't understand Hi
It is frequently called merge sort tree So there is an array TRANSPORTED[i]
If we have want to find some value in interval of array cells from i=l to i=r
We can do binary search in sorted sequence TRANSPORTED[l], TRANSPORTED[l+1],... TRANSPORTED [r-1], TRANSPORTED[r] In merge sort tree
We have some sorted subsequences precalculated
It is possible to represent any subsequence [l..r] as union of O(log(n)) such precalculated subsequences |
| quicksort TLE#11; use heapsort instead and got AC | LLL | 1613. For Fans of Statistics | 3 Sep 2017 16:12 | 1 |
|
| Why AC with C++11 and TLE with C++ | LastOne | 1613. For Fans of Statistics | 31 May 2017 17:52 | 2 |
Your question is incorrect without code. In C++ 11, there are a lot of new features. Maybe just performance improvement of C++11 over earlier versions gives you AC. Look for example for string class. In C++98, strings are much slower, than modern strings. Your AC code runs in 800ms. Mine just in 240. http://acm.timus.ru/status.aspx?space=1&num=1613&author=201928You can made a lot of optimizations. After those optimizations, you will get no TLE on G++4.9. |
| Another way to get AC | standy | 1613. For Fans of Statistics | 7 Apr 2016 19:06 | 4 |
You should use a SQRT-decomposition. Let BLOCK = sqrt(N) In kth element of the decomposition you should store hash_set containing numbers from k * BLOCK to (k + 1) * BLOCK. i am getting time limit on test 13 , with sqrt-decomposition. You can solve this task using binary search.
Sort all numbers with their indexes.
Now if we get query L R X, we use binary search to find all X numbers between
our numbers. If we found X in binary search, check it's index, if it's >= l and <=r then
answer for query is 1. If such number wasn't found in binary search, answer for query is 0. > if it's >= l and <=r then answer for query is 1
it isn't enough 'cause you can have several cities with the same population and simple binary search finds just one of them
3
666 666 666
1
1 1 666
has to answer 1 |
| Another hint (SQRT-decomposition in C++) | MaximCherchuk | 1613. For Fans of Statistics | 5 Mar 2016 02:57 | 1 |
If you decide to use SQRT-decomposition in C++ using std::set you can get TLE on test 13. All you need is to replace set -> unordered_set in your code :) (dont forget about C++11) |
| One of the solutions | Denis Rozimovschii | 1613. For Fans of Statistics | 13 Aug 2015 20:27 | 1 |
Create an unordered map <int, set <int> > and for each number in the input insert it's index to the corresponding position in the map, then for each query use manipulations with upper_bound in the set.
Looks like O(nlogn + qlogn).
Edited by author 13.08.2015 20:29 |
| Accepted sqrt_decom && binary_search && quick sort 0.765 | Temirbay Miras | 1613. For Fans of Statistics | 12 Feb 2015 10:15 | 1 |
|
| Compiler time differences | Tural Neymanov | 1613. For Fans of Statistics | 17 Jan 2015 15:07 | 1 |
So my algo is to have a vector of pairs(value and index), sort them(used usual <algorithm> sort), and then binary searched each request - first by value, and if value was correct, by index. The program ACed, on G++11 compiler with 0.921 time. when I removed the inclusion of <cstdlib>, it ACed with 0.859(and same on G++14). But funny thing is, on Visual C++ 2010, it ACed with 0.593s time, which is astounding(to me at least) because the difference is quite noticeable(25% drop). So I guess if you are getting TLE, it's worth a try to run it with Visual C++ - you might get a pass this way. Edited by author 17.01.2015 15:10 |
| Hint | TakeOver | 1613. For Fans of Statistics | 17 Sep 2013 20:36 | 2 |
Hint TakeOver 14 Mar 2013 23:19 if you're writing in c++ - use unordered_map instead of map :) |
| If you use Java | Oleg Strekalovsky [Vologda SPU] | 1613. For Fans of Statistics | 21 May 2013 00:18 | 3 |
My solution use Arrays.binarySearch( ) It can be used 1 or 2 times, to establish "1" or "0". There are some interesting moments at this method. look at: Goog Luck! Edited by author 04.05.2009 20:15and use BufferedReader instead of Scanner. if you can implement binary search properly with all terminating conditions, it will work. |
| java, MLE test #6 (69360Kb): what`s in it ? | Ozzy | 1613. For Fans of Statistics | 21 May 2013 00:14 | 2 |
I'm trying to sovle this task using HashMap<Integer, BigInteger>.
Maximal amount of elements in this HashMap object = 70000.
Unfortunatelly, I'm getting MLE, 0.406s 69360Kb.
Which kind of test data should be created to examine memory consumption of my variant ?
TIA. yeah, if you have used binary search, some test case.make it to go for infinite cycle. u can check for terminating conditions. |
| Yesss!... 0.281s 1520 Kb (java) | Ozzy | 1613. For Fans of Statistics | 19 Apr 2013 22:14 | 1 |
Many thanks to author of this task and Oleg Strekalovsky [Vologda SPU] for the hint ( http://acm.timus.ru/forum/thread.aspx?id=22536&upd=634614144741133716 ). PS. It is very unexpectedly to me that some collection types (e.g. HashMap) take so much memory and CPU time in java :-/ Edited by author 19.04.2013 22:14 Edited by author 19.04.2013 22:14 |
| Try Treap~ | Zero | 1613. For Fans of Statistics | 21 Mar 2013 17:55 | 1 |
search if there are the number in the certain interval, use balanced search tree |
| # to admins <weak.tests> | wicked6 | 1613. For Fans of Statistics | 27 Feb 2013 03:21 | 2 |
This test will take my AC program ( http://acm.timus.ru/getsubmit.aspx/4790749.cpp ) to TLE (8 secs) : 70000 1 1 1 1 1 1 ... (70000 times) 70000 1 1 1 1 1 1 1 1 1 1 1 1 ... (70000 times) Could you please add this also ? Edited by author 21.02.2013 23:59 |
| For WA4 or WA6 | ACSpeed | 1613. For Fans of Statistics | 2 Dec 2012 03:35 | 3 |
I find it very strange when in QuickSort :
pivot = A[(High+Low) div 2]; will get me AC for both tests
while
pivot = (High+Low) div 2;
....
A[pivot] will give me WA4/WA6 .
Try to sort this array (it's too big, but i'm so lazy and don't want to discover another example) with second version of your qSort:
16
4 2 3 2 2 1 2 10 6 3 2 2 11 128 0 2
What you got? :)
Edited by author 30.07.2012 21:12 pp := arr[(ll + rr) div 2].val;
while (ii <= jj) do
begin
while (arr[ii].val < pp) do Inc(ii);
while (arr[jj].val > pp) do Dec(jj);
if (ii <= jj) then
begin
t := arr[ii];
arr[ii] := arr[jj];
arr[jj] := t;
Inc(ii);
Dec(jj);
end;
end;
This is right. but not this
pp := (ll + rr) div 2;
while (ii <= jj) do
begin
while (arr[ii].val < arr[pp].val) do Inc(ii);
while (arr[jj].val > arr[pp].val) do Dec(jj);
if (ii <= jj) then
begin
t := arr[ii];
arr[ii] := arr[jj];
arr[jj] := t;
Inc(ii);
Dec(jj);
end;
end;
because in the loop, the if statement will possibly change the value of arr[pp].val.
That is why you have WA6. |
