https://new.contest.yandex.ru/contests/80784/problem
Задача B.
Одна из болей в том, что это нужно сделать через связный список. Оно проходит первые два кейса, но рушится на третьем. Посмотреть содержимое кейса к сожалению нельзя.
Нашёл такую идею:
За O(n) предподсчетом строим 4 массива: префикс максимумов, префикс минимумов, суффикс максимумов и суффикс минимумов. В i-ой позиции в префиксных массивах храним максимум/минимум среди всех чисел, лежащих левее i-ого индекса и индекс этого максимума/минимума. В i-ой позиции в суффиксных массивах храним максимум/минимум среди всех чисел, лежащих правее i-ого индекса и индекс этого максимума/минимума.
Далее для поиска минимальной разницы за O(n) проходим по префиксу минимумов и суффиксу максимумов, считаем текущую разницу минимума и максимума и запоминаем у минимальной разницы индексы.
Для поиска максимальной разницы аналогично с префиксом максимумов и суффиксом минимумов.
Мой код:
class DoubleLinkedListNode {
constructor(value, prev = null, next = null) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
class DoubleLinkedList {
constructor(head = null, tail = null) {
this.head = head;
this.tail = tail;
}
append(value) {
const newNode = new DoubleLinkedListNode(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
return;
}
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
prepend(value) {
const newNode = new DoubleLinkedListNode(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
return;
}
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
findPrefixMax() {
if (!this.head)
return null;
let currentNode = this.head;
let mx = -Infinity;
let i = 0;
let mxIndex = 0;
const result = new DoubleLinkedList();
while (currentNode) {
if (currentNode.value > mx) {
mx = currentNode.value;
mxIndex = i;
}
currentNode = currentNode.next;
result.append([mx, mxIndex]);
i++;
}
return result;
}
findPrefixMin() {
if (!this.head)
return null;
let currentNode = this.head;
let mn = Infinity;
let i = 0;
let mnIndex = 0;
const result = new DoubleLinkedList();
while (currentNode) {
if (currentNode.value < mn) {
mn = currentNode.value;
mnIndex = i;
}
currentNode = currentNode.next;
result.append([mn, mnIndex]);
i++;
}
return result;
}
findSuffixMax() {
if (!this.head)
return null;
let currentNode = this.tail;
let mx = -Infinity;
let mxIndex = 0;
const result = new DoubleLinkedList();
let len = 0, tmp = this.head;
while (tmp) {
len++;
tmp = tmp.next;
}
let i = len - 1;
while (currentNode) {
if (currentNode.value > mx) {
mx = currentNode.value;
mxIndex = i;
}
result.prepend([mx, mxIndex])
currentNode = currentNode.prev;
i--;
}
return result;
}
findSuffixMin() {
if (!this.head)
return null;
let currentNode = this.tail;
let mn = Infinity;
let mnIndex = 0;
const result = new DoubleLinkedList();
let len = 0, tmp = this.head;
while (tmp) {
len++;
tmp = tmp.next;
}
let i = len - 1;
while (currentNode) {
if (currentNode.value < mn) {
mn = currentNode.value;
mnIndex = i;
}
result.prepend([mn, mnIndex])
currentNode = currentNode.prev;
i--;
}
return result;
}
findDifference() {
const prefixMx = this.findPrefixMax();
const suffixMx = this.findSuffixMin();
let mx = -Infinity;
let mxIndex = 0;
let currnetNodeStartMx = prefixMx.head;
let currnetNodeEndMx = suffixMx.head;
while (currnetNodeStartMx) {
if ((currnetNodeStartMx.value[0] - currnetNodeEndMx.value[0]) > mx) {
mx = currnetNodeStartMx.value[0] - currnetNodeEndMx.value[0];
mxIndex = [currnetNodeStartMx.value[1] + 1, currnetNodeEndMx.value[1] + 1]
}
currnetNodeStartMx = currnetNodeStartMx.next
currnetNodeEndMx = currnetNodeEndMx.next
}
const prefixMn = this.findPrefixMin();
const suffixMn = this.findSuffixMax();
let mn = Infinity;
let mnIndex = 0;
let currnetNodeStartMn = prefixMn.head;
let currnetNodeEndMn = suffixMn.head;
while (currnetNodeStartMn) {
if ((currnetNodeStartMn.value[0] - currnetNodeEndMn.value[0]) < mn) {
mn = currnetNodeStartMn.value[0] - currnetNodeEndMn.value[0];
mnIndex = [currnetNodeStartMn.value[1] + 1, currnetNodeEndMn.value[1] + 1]
}
currnetNodeStartMn = currnetNodeStartMn.next
currnetNodeEndMn = currnetNodeEndMn.next
}
return [mnIndex, mxIndex];
}
toArray() {
const arr = [];
let current = this.head;
while (current) {
arr.push(current.value);
current = current.next;
}
return arr;
}
}
function fromArrayToDoubleLinkedList(arr) {
const doubleLinkedList = new DoubleLinkedList();
for (let i = 0; i < arr.length; i++) {
doubleLinkedList.append(arr[i])
}
return doubleLinkedList;
}
const fs = require('fs')
let fileContent = fs.readFileSync("input.txt", "utf8");
let arrNums = fileContent.split('\n').map((value) => value.split(' ').map(Number))
const nums = fromArrayToDoubleLinkedList(arrNums[1])
const result = nums.findDifference().map((arr) => arr.join(' ')).join('\n')
fs.writeFileSync("output.txt", result.toString())
