I was trying to solve this problem: https://mirror.codeforces.com/contest/1487/problem/C and i came up with a wrong solution that i changed, now i know this modified solution works but its based on some assumptions that are:
- if n%2 = 0, then the optimal way is to tie a match between two teams such that each of them has no ties yet. And there is a way to get score = 0, in a way such that we make a team lose (n)/2-1 times and win (n)/2-1 times and 1 tie(assigned previously), also if this team has won/lost a match with any other team, we keep that in mind. So, we fill the grid of size n * n, such that each row(representing a team's matches has sum = 0), one thing that i need prove with is that once i have filled more than n/2 rows its possible to fill remaining such that their sum if 0, and only using -1/0/1 representing lose/tie/win.
- else, the optimal way is to have no ties and make each team lose (n-1)/2 times and win (n-1)/2 times. Here, i needed proof with :- Once I have filled more than n/2 rows, its possible to fill remaining with sum = 0 using only -1/0/1 representing lose/win/tie.
Could you please try to write your statement more clearly? I can't be sure about what you mean by
"Once I have filled more than n/2 rows, its possible to fill remaining with sum = 0 using only -1/0/1 representing lose/win/tie".If you mean that you can fill up the first $$$(n + 1)/2$$$ rows arbitrarily keeping row sum = $$$0$$$, there will always be a way to fill up the rest of the rows keeping row sum = $$$0$$$, then that is wrong.
Here's a counter example:
No matter how you replace the
?, you will not be able to ensure equal number of wins and losses for each team.If there are some specific rules which you are following to fill up the first half rows, please specify it.
yeah this way only, making sure that if grid[i][j] = W then grid[j][i] = L and vice versa. and keeping sum = 0, i see, this is wrong thanks for providing example.
i tried it, it works
this is the output for n=7, first i assign 'L' or losses to a team(except for matches that have already taken place keeping in mind match[i][j] = negation of match[j][i])
So, if I am team $$$x$$$, I beat team $$$x+1$$$, $$$x+2$$$, $$$...$$$, $$$x + m/2$$$ and lose the rest of the matches (in case $$$x + i \gt n$$$, I take $$$(1 + x + i) \mod n$$$). This is symmetric for all the teams (if I beat $$$x + i$$$, $$$x - i$$$ beats me), so the interdependencies are handled. For even $$$n$$$, $$$x + n/2$$$ and $$$x - n / 2$$$ are the same teams (in circular number line), so I can assign a tie there.
yeah, if n=7 and x=6 then i beat 3 teams on left(3, 4, 5) and lose to 3 teams on right(7, 1, 2)
and if n = 8 and x=6 then i beat 3 teams on left(3, 4, 5) and lose to 3 teams on right(7, 8, 1), now match with team '2' is left so we make it a Tie.
thanks for putting it this way, now it makes sense why this works.
and for n=8, this is the output,
initially i understood the scores wrong in case of winning, winning team gets +3 and losing team gets 0 in case of tie, both get +1
for n = 8, this is the output, T=tie
I like the diagonal symmetricity of this grid
I tried it by exploiting the properties of permutation, like teams are ordered 1,2,...n which is a permutation. Let n = 5, initially i assumed all teams have tied with each other and if tie is resolved (i.e conclusive result), each team would have to face equal number of wins and losses. say at a leap of 1, i.e 1 -> 2 -> 3 -> 4 -> 5 -> 1 (forms a cycle), where "x -> y" means "x defeats y". Similary at leap of 2, 1 -> 3 -> 5 -> 2 -> 4 -> 1, and so on. However, some cycles are defective, like for n = 6, leap = 3, 1 -> 4 -> 1, as 1 defeats 4 and 4 too defeats 1, which is not possible, and hence tie cannot be resolved. Though my approach is too complicated.