For large N, 2% of sample are counted.

please,give 23 test

Hints:

1. No sorting. It's useless. Quiqsort - too much memory, Bublesort - too long time.

2. We just need a number that is more than n/2. It always exists.

3. Read values step by step, remember the 'candidate' answer and counter increase or decrease it.

e.g:

3->3 cnt=0+1=1

3->3 cnt=1+1=2

2->3 cnt=2-1=1

2->3 cnt=1-1=0

3->3 cnt=0+1=1

Note 1:

e.g.

5

3

3

2

2

6

My program's answer is 6, but such a case never occurs (!).

"He knows exactly that more than half banknotes have the same value."

Note 2:

C# - "Memory limit exceeded 21"

use this:

    if (i % 1000 == 0)

       GC.Collect();

Regards

Edited by author 12.01.2022 20:54

using System;
using System.Collections.Generic;
namespace Order {
    class Banknotes {
        public long value = 0;
        public int count = 0;
        public Banknotes(long value) {
            this.value = value;
        }
    }

    class Program {
        public static Banknotes FindMaxValue (List<Banknotes> list) {
            int _maxValue = list[0].count;
            Banknotes _maxBanknote = list[0];
            for (int index = 1; index < list.Count; index++) {
                if (list[index].count > _maxValue) {
                    _maxBanknote = list[index];
                    _maxValue = list[index].count;
                }
            }

            return _maxBanknote;
        }

        public static void Main (string[] args) {
            List<Banknotes> banknotes = new List<Banknotes>();
            int length = Convert.ToInt32(Console.ReadLine());
            if (length == 0) return;

            banknotes.Add(new Banknotes(Convert.ToInt64(Console.ReadLine())));
            banknotes[0].count = 1;
            for (int iterable = 1; iterable < length; iterable++) {
                long number = Convert.ToInt64(Console.ReadLine());
                for (int jterable = 0; jterable < banknotes.Count; jterable++) {
                    // Console.WriteLine($"{number} is {numbers[jterable].value}?");
                    if (number == banknotes[jterable].value) {
                        banknotes[jterable].count++;
                        // Console.WriteLine("yes");
                        break;
                    } else if (jterable + 1 == banknotes.Count) {
                      // Console.WriteLine("no");
                        banknotes.Add(new Banknotes(number));
                    }
                }
            }

            Console.WriteLine(FindMaxValue(banknotes).value);
        }
    }
}

If you are using C# and running out of memory somewhere at test 36 think how to gracefully call the GC because the heap is full of strings u read from console.

Hi people.
It looks like there is no one solution which used Python 3.8 x64. I use a linear algorithm (one pass, actually) but I still get TLE21. Are there any options for python or should I just use another language?
Thanks.

Hey guys,
how to get run time under 0.02s?
I implement O(n) solution, but my time is ~0.15s for CLang...
What optimisations do you use?

I got TLE for both, straightforward sort-solution (n*logn) and Moore's algorithm (n).
You can avoid it using this line in your code:
- ios_base::sync_with_stdio(false);

Commands "cout" and "cin" are immensely slow and for large inputs, your code can get TLE.
Surprisingly, both approaches differ from each other only by 0.02 sec (with the aforementioned line included).

#include <stdio.h>

int main(){
int i,n,x,y,z,x1=0,y1=0,z1=0;
scanf("%d",&n);
int* A=new int[n];
for(i=0;i<n;i++)
scanf("%d",&A[i]);
x=A[0];
i=1;
y=-100;
while(1){
if(A[i]==x)
x=A[i];
else if(A[i]!=y)
y=A[i];
else
{
z=A[i];
break;
}
i++;}
for(i=0;i<n;i++)
{
if(A[i]==x)
x1++;
else if(A[i]==y)
y1++;
else if(A[i]==z)
z1++;
}
if(x1>y1 && x1>z1)
printf("%d",x);
else if (y1>z1 && y1>x1)
printf("%d",y);
else if (z1>x1 && z1>y1)
printf ("%d",z);
return 0;
}

I don't understand. I use quicksort and then find solution very fast. MLE #21 say me that
memory limit! I use c#.

Edited by author 26.03.2017 21:16

Edited by author 26.03.2017 21:16

Edited by author 26.03.2017 21:17

Edited by author 26.03.2017 21:37

whats test #1??

What is the test №19?

""
from sys import stdin
from collections import Counter

def search():
    tmp = Counter([int(x) for x in stdin])
    return [i for i in tmp.keys() if tmp[i] == max(tmp.values())][0]
search()
"""

Edited by author 22.10.2015 01:31

Could anyone helps me with test 7?

I wrote simple (dummy) solution - just store all input values in array - then sort it (qsort) - and write array[n/2].

I use free pascal.

On my PC program works correct. at least there no any runtime errors. I tested it with input N=1, 2, 3, 5, 1000, 500000. I enabled all checks like I/O, range check, stack check, overflow check, even init variables with garbage...

Could s/w get me any clue what can be wrong?

my last try - id 6409005

I got TLE, but when i used Visual C++ 2010 I hot AC. It worked for me, I hope it will work also for you

#include<iostream>

using namespace std;

int arr[500005];

int main()
{
    int n;
    cin >> n;

    long long int a;
    int p = 0;

    arr[0] = -1;
    for (int i = 0; i < n; i++)
    {

        cin >> a;

        if (a == arr[p] || p == 0)
        {
            p++;
            arr[p] = a;
        }
        else
            p--;
    }

    cout << arr[1] << endl;

}

Edited by author 12.12.2014 12:48

Edited by author 12.12.2014 12:48

What's wrong with test #38? I got AC with sorting but failed on majority search?

I used dictionary in python 2.7 to solve this problem, but got MLE on test#21. Can anybody give me some advise or hint about how to deal with this problem? Thanks a lot!!!

Here is my code:

from sys import stdin

num = int(stdin.readline())
notes = {}
for i in range(num):
    key = int(stdin.readline().strip())
    if notes.has_key(key):
        notes[key] += 1
    else:
        notes[key] = 1
max = -1
note = -1
for key, value in notes.items():
    if value > max:
        note = key
        max = value
print note

#include<iostream>
using namespace std;
int main ()
{
    int n,a[500000],d,max=0,maxi;
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>d;
        a[d]++;
        if (a[d]>max)
        {
            max=a[d];
            maxi=d;
        }
    }
    cout<<maxi;
    return 0;
}

Hi!
That is no surprise for you that O(N*logN) solution using C++ map<int, int> fits in 1 second perfectly.
An idea is to create a problem "Order: version 2" with lower time limit (0.5 sec or something like that) and, maybe, higher amount of input. For what? Just for saying "YOU SHALL NOT PASS"© to O(N*logN) solutions and giving a chance only to O(N) algorithms (like Boyer-Moore Majority Vote Algorithm). And difficulty, of course, should be increased correspondingly.
Thanks for attention. Long live Timus!

Edited by author 11.01.2014 08:22

What is test #19?