Боря программирует

CF 942D

Решал тут CodeForces раунд и очень понравилось решение одной из задач. На контесте я перемудрил, попытался придумать слишком сложное решение и в итоге задачу не сдал. Но на самом деле все гораздо проще, и в следующем посте расскажу как надо было решать. А вы пока можете в комментариях предложить свои решения.

Если выкинуть неинтересные детали, то условие такое. Дан массив a длиной 10^6 из чисел от 0 до N-1 и массив next (длиной N с числами от 0 до N-1). Можно любое количество раз заменить a[i] на next[a[i]] для любого i (причем можно применять операцию для одной и той же позиции несколько раз). N=10^6. Спрашивается, можно ли сделать массив a неубывающим?

🔥7👍1

www.tgoop.com/bminaiev_blog/66

3.73K viewsApr 30, 2024 at 17:42

CF 942D

Решал тут CodeForces раунд и очень понравилось решение одной из задач. На контесте я перемудрил, попытался придумать слишком сложное решение и в итоге задачу не сдал. Но на самом деле все гораздо проще, и в следующем посте расскажу как надо было решать. А вы пока можете в комментариях предложить свои решения.

Если выкинуть неинтересные детали, то условие такое. Дан массив a длиной 10^6 из чисел от 0 до N-1 и массив next (длиной N с числами от 0 до N-1). Можно любое количество раз заменить a[i] на next[a[i]] для любого i (причем можно применять операцию для одной и той же позиции несколько раз). N=10^6. Спрашивается, можно ли сделать массив a неубывающим?

BY Боря программирует