ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

Anton The Great O(n) is possible [2] // Problem 1196. History Exam 8 Apr 2007 02:58
But I think, it is cheating...

Edited by author 08.04.2007 03:01
Romko [Lviv NU] Re: O(n) is possible [1] // Problem 1196. History Exam 8 Apr 2007 14:23
My solution is O(n). Bool array, no cheating!
Tutanhamon O(n*log n)-My solution // Problem 1196. History Exam 8 Mar 2008 01:40
in input we have first array sorted an second unsorted

my solution needs to sort second array
so it has O(n*log n) quick sort.
where n is M(number of Student's dates)

then i solve problem in O(n):
--------------------------------
  While (j<=M) and (i<=N) do begin
    While S[j]<T[i] do inc(j);
    if S[j]=T[i] then begin
      inc(j);
      inc(Am);
    end else inc(i);
  end;
-----------------------------------
S-Array of teacher records
T-Array of student records
Am-number of complying dates

so, this algo is O(N*log n);