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 1523. K-inversions

Give me proof why following approach is wrong
Posted by Mahilewets 11 May 2017 13:17
My approach wrong approach is such.
Read cur number X.
Find CNT count of numbers Y (Y>X) already read.
Find number of ways to pick K-1 items from set of CNT distinctive  items.
Add that number to ANSWER. Find modulo.

Edited by author 11.05.2017 13:28
Re: Give me proof why following approach is wrong
Posted by sak3t 22 Jun 2017 13:53
Your solution is wrong. See for example

6 3

3 4 5 6 2 1

when you read 2, all the numbers before it are > 2 and hence you'll add to your sum, all the possible pairs in previous 4 numbers. But 3 4 5 6 can't make any pair such that a_i > a_{i+1}. Hence your solution doesn't work.

Edited by author 22.06.2017 13:55