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