Форум программистов, компьютерный форум CyberForum.ru

Два указателя. Сложно - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 00:50     Два указателя. Сложно #1
Вот есть задача, с которой я не могу справиться, мне не нужен ваш код, а будет вполне достаточно словесного описания алгоритма или сути его работы. Решается он через 2 указателя, может потребуется сортировка. Никак не могу додуматься до алгоритма. Help.
Учтите, задача не простая, посмотрите на ограничения.

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 262144 KB.

Дана последовательность целых чисел a1, a2,..., an. Требуется найти такую пару (index, length), чтобы сумма чисел [aindex, aindex+1,..., aindex+length-1] была положительной. При этом length должно быть наибольшим возможным. Если ответов несколько, выберите ответ с меньшим index.

В этой задаче последовательность ai будет задаваться в следующем виде: bi = (A · bi-1 + B) mod C, b0 = S, ai = X · bi + Y, где X, Y, A, B, C, S будут числами, заданными во входном файле.

mod — это оператор взятия остатка. Генерацию последовательности делайте в 64-битном типе.


Входные данные
В первой строке содержится число n (1 ≤ n ≤ 5000000). Во второй строке записаны числа X, Y, A, B, C и S, разделенные пробелами (|X| ≤ 1000, |Y| ≤ 10^9, 0 < C ≤ 10^6, 0 ≤ A, B, S ≤ 10^6).


Выходные данные
Выведите числа index и length через пробел. Гарантируется, что length > 0.

Ввод :
7
1 -2 3 4 5 6
Вывод :
3 5

Добавлено через 2 минуты
Хотя, я не брезгую, код тоже не помешает.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 02:01     Два указателя. Сложно #2
Ternsip, думаю что генерацию последовательности ускорить нельзя. Хотя bi напоминает конгруэнтную последовательность, и если можно бы было узнать ее период >_> Самому мне думать лень, так что по теме раз фича, два фича. Надеюсь, что это тебе как-то поможет.
ssXXss
263 / 185 / 10
Регистрация: 15.01.2011
Сообщений: 668
09.05.2013, 02:34     Два указателя. Сложно #3
а тут точно так - bi = (A · bi-1 + B) mod C а не так bi = (A · b0-1 + B) mod C ?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.05.2013, 06:08     Два указателя. Сложно #4
еще раз повторю общую просьбу: публикуйте ссылку на тестер.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 16:53  [ТС]     Два указателя. Сложно #5
ssXXss, да, там b0 опечатка
salam, http://acm.sgu.ru/univer/problem.php...=0&problem=436
http://acm.sgu.ru/univer/

Добавлено через 8 секунд
nonedark2008, спасибо

Добавлено через 5 часов 21 минуту
nonedark2008, первая фича http://stackoverflow.com/questions/1...-or-equal-to-k Попытался по ней реализовать то, что там написано, вот что накатал, не работает, логика не ясна. arr у меня это массив частичных сумм
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std; 
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    vector <int> arr;
    arr.push_back(0);
    arr.push_back(20);
    arr.push_back(-10);
    arr.push_back(20);
    arr.push_back(50);
    arr.push_back(50);
    arr.push_back(-40);
    vector < pair<int, int> > pr(arr.size());
    for(int i = 0; i < pr.size(); i++) {
        pr[i] = make_pair(arr[i], i);
    }
    sort(pr.begin(), pr.end());
    vector <int> lef(pr.size(), 0);
    for (int i = 1; i < pr.size(); i++) {
        if (pr[i].first == pr[i-1].first) 
            lef[i] = lef[i-1];
        else 
            lef[i] = i;
    }
    vector <int> maxid(pr.size(), pr[pr.size()-1].second);
    for (int i = maxid.size() - 2; i >= 0; i--) {
        maxid[i] = max(maxid[i+1], pr[i].second);
    }
    int idx = 0, len = 0;   
    for (int i = 0; i < maxid.size(); i++) {
        int ans = maxid[i] - lef[i];
        if (ans > len) {
            len = ans;
            idx = lef[i];
        }
    }
    cout << idx << " " << len;
    return 0;
}
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 18:24     Два указателя. Сложно #6
Ternsip, не сильно проверял, но вроде работает:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool comp( const pair<int, int> &a, const pair<int, int> &b )
{
  if (a.second < b.second)
    return true;
  return false;
}
 
void main( void )
{
  vector<int> arr(6);
 
  arr[0] = -10, arr[1] = -2, arr[2] = 3, arr[3] = 3, arr[4] = 0, arr[5] = -4;
  
  for (int i = 0; i < 6; ++i)
    cout << arr[i] << ' ';
  cout << endl;
  int sum = 0;
  vector<pair<int, int>> pref(6 + 1);
  pref[0].first = pref[0].second = 0;
  for (int i = 1; i < 6 + 1; ++i)
  {
    sum += arr[i - 1];
    pref[i].first = i + 1;
    pref[i].second = sum;
  }
 
  std::sort(pref.begin(), pref.end(), comp);
  vector<int> maxInd(6 + 1);
 
  for(int i = 0; i < 6 + 1; ++i)
  {
    maxInd[i] = pref[i].first;
    for (int j = i + 1; j < 6 + 1; ++j)
    {
      if (pref[j].second >= pref[i].second && pref[j].first > maxInd[i])
        maxInd[i] = pref[j].first;
    }
  }
 
  int max = 0;
  for (int i = 1; i < 6 + 1; ++i)
  {
    if (maxInd[i] - pref[i].first > maxInd[max] - pref[max].first)
      max = i;
  }
 
  cout << pref[max].first << ' ' <<  maxInd[max] - pref[max].first << endl;
  system("pause");
}
В выводе нумерация элементов массива начинается с единицы.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 18:29  [ТС]     Два указателя. Сложно #7
nonedark2008, у вас сейчас квадратичный, медленный алгоритм, он не подходит, по времени не пройдёт
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 18:53     Два указателя. Сложно #8
Ternsip, ок, увидел. Все из-за двойного цикла. Я его писал без учета отсортированности массива. А так, подойдет та часть, что вы сами написал... Тогда удастся избежать двойного цикла, а значит и сложность будет nlogn.

Добавлено через 16 минут
А алгоритм достаточно понятен. Мы для каждого префикса в массиве находим префиксы больший либо равный текущему и берем тот, у которого индекс будет самым большим. Если идекс одного префикса больше индекса другого и второй префикс >= первому, то сумма элементов между индексов будет >= 0.
Выбирая префикс с самым большим индексом мы выбираем самую длинную цепочку.
А дальше, просто ижем максимум разности maxInd и ind - это будет длина самой длинной цеопчки, сумма которой больше нуля.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 19:11  [ТС]     Два указателя. Сложно #9
nonedark2008, вот переписал под свой лад
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std; 
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, x, y, a, b, c, s;
    cin >> n >> x >> y >> a >> b >> c >> s;
    long long curb = s, cura, sum = 0;
    vector < pair<long long, int> > pref(n + 1);
    pref[0] = make_pair(0, 0); 
    for (int i = 1; i <= n; i++){
        curb = (a * curb + b) % c;
        cura = x * curb + y;
        sum += cura;
        pref[i] = make_pair(sum, i + 1); 
    }
    sort(pref.begin(), pref.end()); // пары сравниваются сначала по 1-ому, затем по второму эл-у
    vector <int> maxid(n + 1, pref[n].second);
    for (int i = n - 1; i >= 0; i--) {
        maxid[i] = max(maxid[i + 1], pref[i].second);
    }
    int max = 0;      
    for (int i = 1; i <= n; i++) {
        if (maxid[i] - pref[i].second > maxid[max] - pref[max].second) {
            max = i;
        }
    }
    cout << pref[max].second << " " << maxid[max] - pref[max].second;
    return 0;
}
Добавлено через 1 минуту
nonedark2008, щас затещу

Добавлено через 2 минуты
nonedark2008, 2/90 видимо сдесь какой то архикосяк, сейчас попробую понять вашу идею, пока сам не допёр ещё

Добавлено через 36 секунд
nonedark2008, кстати, TL очень много за NlogN не проходит решение

Добавлено через 1 минуту
nonedark2008, может из-за make_pair() так медленно ? по идее N Log N должно за 0.5 секунды проходить
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 19:12     Два указателя. Сложно #10
Цитата Сообщение от Ternsip Посмотреть сообщение
curb = (a * curb + b) % c; cura = x * curb + y;
Проверь, мне кажется что строчки перепутаны местами.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 19:20  [ТС]     Два указателя. Сложно #11
nonedark2008, нет, тут всё ок
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.05.2013, 19:20     Два указателя. Сложно #12
Цитата Сообщение от Ternsip Посмотреть сообщение
может из-за make_pair() так медленно ? по идее N Log N должно за 0.5 секунды проходить
может быть, попробуй написать свой pair
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 19:34     Два указателя. Сложно #13
Ternsip, в вашем решении больше всего жрет сортировка - как и должно быть. Чаще всего вызывается оператор сравнения в сортировке, что плохо, т.к. для сравнения двух чисел вызывается отдельный метод.
Так что лучше написать свой алгоритм сортировки, отказаться от использования векторов в пользу массивов, отказаться от использования потокового ввода/вывода в пользу printf/scanf.
Чтобы самому проверять что жрет больше всего - нужно использовать анализатор производительности, например он встроен в VS, а также он есть в утилитах от Intel.

Добавлено через 5 минут
Ternsip, кстати, ты вроде забыл про условие, что если встретятся одинаковые ответы, то нужно выбрать с наименьшим индексом. Так что в последнем цыкле еще нужно проверять на >=, а внутри выбирать с наименьшим индексом.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.05.2013, 20:00     Два указателя. Сложно #14
Цитата Сообщение от Ternsip Посмотреть сообщение
по идее N Log N должно за 0.5 секунды проходить
не должно. тут довольно простая линия.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
09.05.2013, 20:05     Два указателя. Сложно #15
Цитата Сообщение от salam Посмотреть сообщение
не должно. тут довольно простая линия.
Ну хоть по оценке сложности судить о точном времени, но на моем ноуте при максимальном размере n программа выполняется примерно за 0.57 секунды, так что после оптимизации будет самое то!
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.05.2013, 20:08     Два указателя. Сложно #16
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Ну хоть по оценке сложности судить о точном времени, но на моем ноуте при максимальном размере n программа выполняется примерно за 0.57 секунды, так что после оптимизации будет самое то!
во-первых, извините за прямоту, ваш ноут мало кого интересует. если его тех параметры соответствуют параметрам тестера, то ок, конечно...

Добавлено через 37 секунд
вообще разговор не об этом. от человека хотят, чтобы он писал оптимальные решения...
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2013, 20:15     Два указателя. Сложно #17
Дайте, пожалуйста, рабочую ссылку на задачу. Или, если возможно, не могли бы Вы уточнить формулы. Потому что при тех что есть, используя данные из примера, получается последовательность: 4 0 -2 2 -1 0 -2, а это не соответствует ответу. А так вот один из вариантов:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
 
 
int main() {
   const int size = 7;
   int sum[ size ];
   
   int X = 1;
   int Y = -2;
   
   int A = 3;
   int B = 4;
   int C = 5;
   int S = 6;
   
   int index  = 0;
   int length = 0;
   
   int b = S;
   
   sum[ 0 ] = X * b + Y;
   
   for ( int i = 1; i < size; i++ ) {
      b = ( A * b + B ) % C;
      sum[ i ] = X * b + Y + sum[ i - 1 ];
      
      for ( int j = 0; j <= i; j++ )
         if ( sum[ i ] - sum[ j ] >= 0 && i - j >= length ) {
            length = i - j + 1;
            index = j + 1;
         }
   }
   
   std::cout << index << ' ' << length << std::endl;
   
   return 0;
}
Добавлено через 16 минут
Внутренний цикл можно немного оптимизировать, чтобы избежать возможных лишних итераций.
C++
1
2
3
4
5
6
      for ( int j = 0; j <= i && i - j >= length; j++ ) {
         if ( sum[ i ] - sum[ j ] >= 0 ) {
            length = i - j + 1;
            index = j + 1;
         }
      }
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.05.2013, 20:57  [ТС]     Два указателя. Сложно #18
Toshkarik, Вы не правы, последовательность получается такая : 0 -2 2 -1 0 -2 2, да и ответ верен: c 3-й позиции в ровно 5 чисел, сумма = 1.

я уже давал ссылку Два указателя. Сложно, ссылка рабочая, туда доступ только из Саратова

Добавлено через 3 минуты
Toshkarik, я уже делал квадратичный алгоритм, он никак не пройдёт по времени с такими ограничениями!!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
 
using namespace std; 
 
const int NMAX = 5000000;
 
long long from1toi[NMAX+1];
 
int main(){
    int n, x, y, a, b, c, s;
    cin >> n >> x >> y >> a >> b >> c >> s;
    long long curb = s, cura, sum = 0;
    from1toi[0] = 0; 
    for (int i = 1; i <= n; i++){
        curb = (a * curb + b)%c;
        cura = x * curb + y;
        sum += cura;
        from1toi[i] = sum; 
    }
    for (int i = n; i >= 1; i--){
        for (int j = 1; j <= n-i+1; j ++){
            if (from1toi[j + i-1] - from1toi[j-1] > 0){
                cout << j << " " << i;
                return 0;
            }
        }
    }
    return 0;
}
Добавлено через 42 секунды
Toshkarik, послдний код, что я привёл работает всегда правильно, но по времени не укладывается в 0.5 секунды, потому что это лобовая реализация за О(n^2)

Добавлено через 1 минуту
а тут нужен алгоритм за О(n), ну может, в самом крайнем случае, если я что то не понял, то за О(Nlogn)

Добавлено через 11 минут
Toshkarik, кстати sum[ 0 ] = 0;
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2013, 21:46     Два указателя. Сложно #19
Цитата Сообщение от Ternsip Посмотреть сообщение
кстати sum[ 0 ] = 0;
По моей логике первая сумма равна первому элементу последовательности, то есть sum[ 0 ] = a0, sum[ 1 ] = a0 + a1 и тд. Плюс все находится в одном основном цикле, ну и проверка во вложенном цикле ( if ( i - j ) >= length ) позволяет избегать поиска когда уже есть вариант длины с бОльшим значением, чем осталось элементов для поиска.
Цитата Сообщение от Ternsip Посмотреть сообщение
0 -2 2 -1 0 -2 2
Странно, даже в ручную посчитать - первый элемент не равен нулю:
a0 = X * b0 + Y = 1 * 6 + ( -2 ), поправьте меня, пожалуйста, может что то упускаю.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2013, 00:27     Два указателя. Сложно
Еще ссылки по теме:

C++ массив. Сложно C++
Можно ли объявить два указателя на одну функцию? C++
C++ Как сравнить два указателя типа char?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
11.05.2013, 00:27  [ТС]     Два указателя. Сложно #20
Цитата Сообщение от Toshkarik Посмотреть сообщение
a0 = X * b0 + Y = 1 * 6 + ( -2 )
b1 = (a * b0 + b) % c = (3 * 2 + 6) % 5 = 2
a1 = x * b1 + y = 1 * 2 + (-2) = 0
Вы не правильно поняли задание.
Последовательность нумеруется с единицы, но как вы храните, это не важно.
Но не в этом суть, а в том, что никто не может придумать алгоритм с двумя указателями, работающий за О(n), т.е. линейно (на этом форуме). У меня несколько знакомых первокуров её уже сдали.
Цитата Сообщение от Toshkarik Посмотреть сообщение
Плюс все находится в одном основном цикле, ну и проверка во вложенном цикле ( if ( i - j ) >= length ) позволяет избегать поиска когда уже есть вариант длины с бОльшим значением, чем осталось элементов для поиска.
А это на асимптотику не влияет, ваш алгоритм всё равно за О(n^2), как и мой, в моём есть ровно всё то, что вы сказали. Я уже проверял не пройдёт он.

Добавлено через 59 минут
Всё-таки спросил у друга, который сделал. Он помог. Тема закрыта. Вот код, работает он за О(n), жалко, конечно, что никто не помог, но всё равно спасибо
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std; 
 
#define ll long long
 
const int NMAX = 5000000;
 
ll from1toi[NMAX+1];
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, x, y, a, b, c, s;
    cin >> n >> x >> y >> a >> b >> c >> s;
    ll curb = s;
    from1toi[0] = 0; 
    vector < pair<ll, ll> > mx, mn(1, make_pair(0,0));
    for (int i = 1; i <= n; i++){
        curb = (a * curb + b) % c;
        from1toi[i] = from1toi[i - 1] + x * curb + y;
        if (mn[mn.size() - 1].first > from1toi[i])
            mn.push_back(make_pair(from1toi[i], i));
    } 
    mx.push_back(make_pair(from1toi[n], n - 1));
    for(int i = n - 1; i >= 0; --i) {
        if(from1toi[i] > mx[mx.size() - 1].first)
            mx.push_back(make_pair(from1toi[i],i - 1));
    }
    int idx = 0, pos = 0, left = -1;
    for(int i = mn.size() - 1; i >= 0; i--) {
        while (pos < mx.size() && mx[pos].first < mn[i].first) {
            pos++;
        }
        if (mx[pos].second - mn[i].second > left || (mn[i].second < idx && mx[pos].second - mn[i].second == left)){
            idx = mn[i].second;
            left = mx[pos].second - mn[i].second;
        }
    }
    cout << idx + 1 << ' ' << left + 1 << endl;
    return 0;
}
Yandex
Объявления
11.05.2013, 00:27     Два указателя. Сложно
Ответ Создать тему

Метки
два указателя
Опции темы

Текущее время: 16:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru