IOI 2017, second round

7 years ago, # |

Early statements, please :D

→ Reply

flashmt

7 years ago, # |

+26

Statements uploaded by jonathanirvings http://jonathanirvin.gs/files/ioi2017/day2/

→ Reply

Radewoosh

7 years ago, # ^ |

+124

Breathe deeply, be strong, wait for mirror, be strong...

→ Reply

SeyedParsa

7 years ago, # |

Here you can see the problems and their translations.

→ Reply

IamFromMars

7 years ago, # |

← Rev. 3 →

-41

Deleted

→ Reply

IamFromMars

7 years ago, # ^ |

← Rev. 3 →

-25

→ Reply

Radewoosh

7 years ago, # ^ |

+16

It was link to standings of onsite IOI... What did you expected, upvotes for weak "never gonna give you up"? :/

→ Reply

unbelievable02

7 years ago, # |

+29

SmallBoy, sancho, MadNick, Nurlykhan go++ :)

→ Reply

microtony

7 years ago, # |

+28

The scoring scheme for Prize is terrible.

→ Reply

jonathanirvings

7 years ago, # ^ |

+29

Yesterday I also realized that the distribution of this problem is not good (only 20, 90-100 assuming most people got subtask 1, which is relatively easy). During the yesterday's GA meeting, I raised a minor objection about this. However, the answer from the ISC is satisfying (believe me), so now I am agree with the scoring :)

→ Reply

microtony

7 years ago, # ^ |

+31

My opinion is that the curve should be similar regardless of difficulty. Now contestants who happens to suddenly don't know how to do / have bugs are severely punished. Now it seems that the whole IOI (bronze) will be decided by this 70 points.

Just my own opinion though.

→ Reply

kostka

7 years ago, # ^ |

+43

Can we ask what was the answer?

→ Reply

legendjohn9999

7 years ago, # ^ |

-7

Do you have any ideas about that problem?

→ Reply

rpeng

7 years ago, # |

← Rev. 2 →

+74

Thanks to msg555, the farming edition is up and running again!

(warning: it has sound)

→ Reply

ko_osaga

7 years ago, # ^ |

+10

lol I quickly found out all other teams, but wondered which team is the hydralisk

→ Reply

nhho

7 years ago, # ^ |

+16

copied from his source code

var team_image_map = {
  "KOR": "hydralisk.png",
  "CAN": "moose.png",
  "AUS": "roo.png",
  "NZL": "kiwi.png",
  "GBR": "guard.png",
  "RUS": "hedge.png"
};

→ Reply

accidentallygivenfuck

7 years ago, # |

← Rev. 3 →

+15

jerry's struggle for that 100 in The Big Prize tho lol

edit:

→ Reply

hogloid

7 years ago, # |

+177

yutaka1999! Go for the winner!

→ Reply

7 years ago, # ^ |

+265

MASSIVE CONGRATULATIONS yutaka1999!! Winning both IMO and IOI , impressive... Is he second person in history to achieve this, after Reid Barton as far as I remember?

→ Reply

WuHongxun

7 years ago, # ^ |

+43

I wondered if he would like to share how he accomplished such an impressive achievement.

→ Reply

7 years ago, # ^ |

+108

"Hello sir, how to become red in one year? Looking forward to you answer, best wishes."

→ Reply

rng_58

7 years ago, # ^ |

+99

By the way, Swistakk, now you certainly don't want to take this bet.

→ Reply

7 years ago, # ^ |

+82

I still do. When writing that I also took into account that you will get familiar with IOI format during participating in 100 IOIs :D.

→ Reply

lightweightsenpai

7 years ago, # ^ |

Actually Reyna became red in one year

→ Reply

rng_58

7 years ago, # ^ |

+108

Congratulations, nice double win!

Let's go to major international tournaments together next year and compete for the titles :)

→ Reply

7 years ago, # |

+39

They just announced on the stream that the contest has been extended by 15 minutes because of technical issues, so there's 23 minutes to go!

→ Reply

never_giveup

7 years ago, # ^ |

Thanks for info!

→ Reply

7 years ago, # ^ |

Now they're saying "by at least 15 minutes, maybe longer".

→ Reply

7 years ago, # ^ |

+10

To summarize what was told on the stream, the judging system still doesn't seem to work well, there's a big queue and it's not clear when the contest will end. So far it seems that it has been extended by 15 more minutes, for total duration of 5:30.

→ Reply

7 years ago, # |

rpeng just announced on the stream that 15 minutes more have been added.

→ Reply

7 years ago, # ^ |

Did they give any reasons for the extension?

→ Reply

7 years ago, # ^ |

He briefly mentioned that there was a large queue and that feedback took more than five minutes.

→ Reply

ko_osaga

7 years ago, # |

Is time on submission indicate the "time of judge" rather than "time of submit?"

And I'm nearly getting heart attack for every time extend..

→ Reply

Zlobober

7 years ago, # |

← Rev. 2 →

According to the current state of the contest hall, contest is extended by 30 minutes (in total).

→ Reply

Namnamseo

7 years ago, # ^ |

+15

Are the contestants able to submit solutions in the extended time? (I hear Achilles chasing a turtle...)

→ Reply

Batman

7 years ago, # |

← Rev. 2 →

+24

What did you do to Iran's team LiTi? No gold?

Update : It's still changing. One gold by now.

→ Reply

7 years ago, # |

No changing in the scoreboard
We have to wait untill the closing ceremony to find out the results ?

→ Reply

http://ioi2017.snarknews.info/index.cgi?data=2017/day1pre&class=ioi2017&year=2017

7 years ago, # ^ |

-15

→ Reply

7 years ago, # ^ |

+20

Last change(s): (05:03)

→ Reply

7 years ago, # ^ |

-15

Yeah, I know, but for the most of scoreboard it's a good approximation.

→ Reply

Domonion

7 years ago, # |

If I am not mistaken, ioi never prolonged contest, especially cuz of queue and testing system. Do they have serious reason to do this?

→ Reply

7 years ago, # ^ |

Panic :D

→ Reply

7 years ago, # |

+18

Seems to be over now, judging by the stream.

→ Reply

7 years ago, # ^ |

+10

Thanks god
I almost thought they are going to make day 3

→ Reply

EKGMA

7 years ago, # ^ |

The scoreboard hasn't changed yet.

Do we have to wait until the closing ceremony to see the results?

→ Reply

7 years ago, # |

+18

OK, so that will be some fair amount of work :P. I am really surprised by some similarity of this problem to ... some other problem :P (details in spoiler)

Simurgh solution

Let's start with solution that does <=m queries. It's obvious that if an edge is a bridge that it is a royal road. We will focus on taking an arbitrary spanning tree T and determining for every of its edges whether it's royal. In order to do this we will demand even more. For every vertex v we will fix one of edges that determines its low value (one we compute when determinining bridges etc.). Let's call set of such edges as L. We will determine which roads from L are royal as well, but just as an auxiliary result.

Let's look at two trees T₁ and T₂ so that T₂ is obtained from T₁ by removing edge e₁ and adding edge e₂. If C(T₂) = C(T₁) + 1 (where C is shorthand for count_common_roads function) then we know that e₂ is royal and e₁ isn't. Similarly if C(T₂) = C(T₁) - 1. Call it exchange lemma.

Now let's look at some cycle in our graph. Let it consist of edges e₁, ..., e_k. We can create a tree T_i that has all edges from this cycle except e_i and all such trees has same set of roads except this cycle. From exchange lemma if it is the case that some of edges from this cycle are royal, but some aren't then we will easily determine for every edge whether it is royal or not. It can't be the case that all edges from cycle are royal, so otherwise no edges are royal, so we know everything as well.

Let's return to our goal, determining which of edges from T and L are royal. For start let's ask about C(T). For every edge e from T that is not bridge let's ask about C(T_e) that is created from T by removing e and adding edge that determines low(v), where v is its deeper (in spanning tree) vertex. Moreover for every edge e in L ask for C(T_e) that is T with added e and removed edge from spanning tree that is highest of T's edges lying on a cycle formed in T with added e.

So we know R(e₁) - R(e₂) for some pairs of edges e₁ and e₂, where R(e) = 1 iff e is royal or 0 otherwise. We can create a graph G whose vertices are edges of original graph from either T or L and two vertices (corresponding to original edges) are connected with directed edge if we know difference of R when applied on them. If we take a connected component in such graph and at least one of differences is nonzero we easily determine R values on all of such vertices/edges. We can note that if our original graph is biconnected (and has >2 vertices) then graph G is connected and since it contained cycle we know that if all differences are zero then no edges from T or L are royal. That fact applied to all biconnected components of our original graph leads to algorithm of determining royality of all edges from T and L. But we can forget about L, we will use just T from this point on.

Now for every edge e not from T or L we can create a tree T_e that has edge e and n - 2 of edges from T that together with e form a tree. We can ask about C(T_e) and from exchange lemma we will determine R(e). This leads to a solution scoring 51 points (maybe there is simpler way of getting that many, but this solution can be further extended to get 100 pts)

Now we can move on to solution using $\text{[math]}$ queries instead of O(m). On beginning let's observe that if we have set of edges F that forms a forest we can know how many of its edges are royal by adding edges from T as long as they do not form a cycle and asking about number of royal edges in resulting tree. Since we know which of edges from T are royal we just subtract number of added royal edges from T from the result of C query. However we will use this just for F sets that are stars.

Let's fix a vertex v, we will determine all edges incident to v that are royal and are not from T. If there are k of them we will use at most $\text{[math]}$ queries. We do this in almost the same way as in prize problem, similarity between these two problems is really big. Let E_v be set of edges not from T that are incident to v. We can learn what is C(E_v) (abuse of notation since E_v is not a tree, hope that it is clear). If it is zero then we conclude there are no interesting edges here. If it is k > 0 we then ask about C(H) where H is a first half of E_v. If C(H) > 0 then we recursively find all royal edges in H and if C(H) - k > 0 then we recursively find all royal edges in second half of E_v. It's kinda like a binary search that tries to find multiple objects instead of just one. That results in $\text{[math]}$ queries that are needed to find all royal edges incident to v what gives $\text{[math]}$ queries in total. We are almost done, but this slightly exceeds query limit, because it is something like $\text{[math]}$ , because for edge uv we use $\text{[math]}$ queries when searching through u's edges and $\text{[math]}$ queries when searching through v's edges. To fix this, when we browse v's edges we not only discard ones that are from T but also ones that go to vertices with lower index. That concludes solution which uses at most $\text{[math]}$ queries and gives 100 pts.

→ Reply

Mucosolvan

7 years ago, # |

Could some provide some hints about Prize problem?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

1) There's a lot of least valuable boxes and just a few of more valuable ones
2) Try determining at least one
3) If we have two of them, how can we tell whether there is more valuable one between them? How to use this fact to look for more valuable boxes?

→ Reply

Mucosolvan

7 years ago, # ^ |

Do you have a deterministic way of finding the least valuable box? After ~50 random shots there's almost no way you don't hit at least one, but it is still possible.

→ Reply

izban

7 years ago, # ^ |

I've tried first min(n, 500) boxes at the beginning: 450² > 200 000, so we will find at least one least valuable box.

→ Reply

7 years ago, # ^ |

In order to make my number of queries lower I noted that if sum of two values returned by checker is at least 22 then it is least valuable, because (22²)² > 200000. That allows me to ask about only 23 boxes.

→ Reply

7 years ago, # ^ |

Yes, I have. Note that checker is adaptive, so in fact it is possible that if checker is evil you will not find any even after 50 shots.

→ Reply

bazsi700

7 years ago, # ^ |

In the first 500 there must be a least valuable box. If there were 500 other boxes, then from the least but one valuable box there would be like 470, and 470^2 > 2*10^5.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Whoops I made this error. At my initial code I checked only 450 boxes to find the minimal, as 450^2 > 2*10^5, but I forgot that this is not necessarily the only layer.

1, 2, 5, 26, 440, 199526 requires 473.

→ Reply

Danlark

7 years ago, # ^ |

26^2 > 440

1 4 21 446 198917 requiers 472 and there can't be more (i believe simple cases will provide you with the proof)

→ Reply

MofK

7 years ago, # ^ |

Remember that the grader is adaptive so it can give you 50 valuable boxes just to piss you off ;)

→ Reply

7 years ago, # ^ |

Simple solution for 90 points.

It's easy to see that at most 500 items are non-lollipops. So query the first min(n, 500) items to find at least one lollipop (this is the one with largest answer sum).

Then to locate all the non-lollipop boxes we could binary search prefixes; it takes at most 500*log_2(200K) ~ 8.5K. (you could save a bit, not sure how many by memoizing queries)

Afterwards just search each of the non-lollipop one by one for the diamond (there's at most 500 of them); the diamond is the one with both 0 result.

→ Reply

paulinia

7 years ago, # ^ |

This solution with memorizing was enough for me to get 100 points.

→ Reply

7 years ago, # ^ |

+13

to reduce queries from $\text{[math]}$ to $\text{[math]}$ , divide the array into $\text{[math]}$ blocks and then binary search just within each block.

→ Reply

nhho

7 years ago, # ^ |

← Rev. 3 →

My approach for 9X marks

My approach for 100 marks

→ Reply

PengsenMao

7 years ago, # |

+63

Congrats to 高谷悠太（たかやゆうた） who came first in both IOI2017 and IMO2017!

→ Reply

7 years ago, # ^ |

+10

yutaka seems better for me :p
but I wonder what is inside the brackets ?

→ Reply

PengsenMao

7 years ago, # ^ |

+10

lol it's japanese

→ Reply

7 years ago, # ^ |

+18

oh didn't know -.-

→ Reply

7 years ago, # ^ |

← Rev. 2 →

[deleted]

→ Reply

mogers

7 years ago, # |

+91

Would like to hear what contestants like matthew99 and Reyna thought of the contest. I think everyone is surprised about their result.

→ Reply

matthew99

7 years ago, # ^ |

+362

sad as fuck. how else can i feel

→ Reply

flashmt

7 years ago, # ^ |

+38

Give them a break, man.

→ Reply

Reyna

7 years ago, # ^ |

+129

Hi, i was kinda frustrated, now i'm much better (i gotta thank everyone for their consolations, my family, friends, people of cf and a lot more, thank you everyone)
About the problems, i liked them, but they were too hard for me to solve, there were a lot of strong participants that managed to solve them, congrats (especially yutaka1999 for that impressive win, both on IMO and IOI)
I enjoyed this wonderful event, despite how i performed, hope everyone else enjoys it aswell

→ Reply

-is-this-fft-

7 years ago, # |

The second time extension was like 50 seconds before the extended end time... Please don't do that again...

→ Reply

Zlobober

7 years ago, # ^ |

Our contestants told that the first time extension was around 15 seconds before the end of the 5 hours. Did you hear that announcement earlier?

→ Reply

-is-this-fft-

7 years ago, # ^ |

Definitely earlier, at least 15 minutes before 5 hours.

→ Reply

Bedge

7 years ago, # ^ |

Actually what is the reason of the second extension?

→ Reply

https://en.wikipedia.org/wiki/1972_Olympic_Men%27s_Basketball_Final

7 years ago, # ^ |

→ Reply

Joxa_P

7 years ago, # |

Wow amazing grind Pedrohso ,from nothing to gold!

→ Reply

m_bezrutchka

7 years ago, # ^ |

← Rev. 2 →

+21

Pedrohso is an incredibly talented guy. I feel very proud by having taught him a few classes a while ago, and I'm happy he could overcome his past coding limitations and was able to fully showcase his problem solving skills. We Brazilians are all very excited about this result, which hopefully will get official soon! :D

→ Reply

OliKoJo

7 years ago, # |

-22

Italia again... called it.

→ Reply

7 years ago, # ^ |

-37

???: Hi , so to me seems like a notorious coincidence.

→ Reply

7 years ago, # |

What are the chances of 144.99 reaching bronze cutoff?

→ Reply

kpw29

7 years ago, # ^ |

Decent. Usually cutoffs are 1:2:3:6, there are more than 300 participants, and 150th has something like 135 as far as I remember

→ Reply

Enchom

7 years ago, # ^ |

← Rev. 2 →

I believe it should be bronze. Half of the participants get medals and 144.99 seems to be in the first half.

P.S.

Though, it seems like the current standings are not the final standings for some odd reason.

→ Reply

7 years ago, # ^ |

+38

At this point, I haven't even got the confirmation that day 1 results are final, and I have suspicions that they might not be, which is why I did not publish even preliminary results to the statistics.

→ Reply

7 years ago, # ^ |

Bronze right now is at 135.76 points; do you think appeals would change it significantly?

→ Reply

hogloid

7 years ago, # |

+111

Wow astonished at the result renewed. I would never believe 1, 4, 5-th place would be occupied by Japanese guys.

→ Reply

7 years ago, # |

← Rev. 3 →

+124

5:29:57....

Uhh, maroonrk, how do you submit twice in the last minute of the contest (when the judge is too slow to get feedback) and manage to have exactly one of the solutions work?

→ Reply

square1001

7 years ago, # ^ |

Well, he is a tourist of last minute. He also raised score in last few seconds at some day of JOI Spring Camp :)

→ Reply

gongy

7 years ago, # ^ |

+39

You don't have to wait for the judge to finish to resubmit. Also, in the last 15 minutes, submissions have no minimum interval. So submitting twice in the last minute is very normal...

I was lucky enough to sit next to him this year. He told me after the contest that he submitted in the last few seconds for Q5. He was very happy to find out 3 hours later during analysis time that he received 100 points :)

→ Reply

7 years ago, # ^ |

+10

Sure, submitting twice is normal. I want to know if he was making random changes and submitting or if he miraculously found a bug in the last few seconds, debugged instantly and squeezed in a correct submission three seconds before the contest ended?

→ Reply

gongy

7 years ago, # ^ |

+21

Ah, yes — he told me he found very small bug which he fixed within the last minute. Very impressive.

→ Reply

DEGwer

7 years ago, # ^ |

+10

He said that in last minute he found some optimization and got 100. He didn't know that result until the analysis, since the scoreboard was broken.

→ Reply

7 years ago, # |

+14

for Books , does anyone have a testcase where the logic for S = 0 fails with S > 0?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+20

Lol. Care to elaborate what you mean, just a suggestion :)? There are a lot of ways you can think about this problem and there are a lot things you can simply don't care about if S=0. Don't expect us to know what you mean by "logic for S=0"

→ Reply

7 years ago, # ^ |

first of all i add count of (j <= i && p[j] > i) + (j > i && p[j] <= i) to the answer for all 0 <= i < n-1 (just the number of crossing from i to i + 1 and i + 1 to i)

Then if the permutation isn't connected like this
. . _______ . s . . __________ . . .
I also add those "Gaps" in the middle to the answer , however this seems to fail for s > 0.

→ Reply

nhho

7 years ago, # ^ |

← Rev. 2 →

+20

To clarify, how will you handle the case where the permutation covers s but s is not a part of it, i.e. s is a fixed point?

For example,

3 1
2 1 0

→ Reply

7 years ago, # ^ |

thanks , got my mistake.

→ Reply

Tutis

7 years ago, # ^ |

← Rev. 4 →

How to make it from 70 points to 100 points?

EDIT:

When S=0 I know a O(n) solution what merges cycles. Otherwise, I can't imagine how to count the amount of walking from starting point to largest cycle covering it. I have a dijkstra solution what works in O(n^2) because I need to check if i can travel from one cycle to another...

EDIT: Maybe we need to do the dijkstra from the other side? :D

EDIT: I keep getting WA on testcase 5 :D Somehow testcase 4 works fine :s

→ Reply

snuke

7 years ago, # ^ |

← Rev. 2 →

+21

My first solution outputs 4 instead of 6 for this case.

3 1
2 1 0

more strong cases

5 2
4 3 2 1 0

answer: 16

10 5
8 3 6 1 4 5 2 7 0 9

answer: 32

9 3
1 0 4 3 2 8 7 6 5

answer: 20

→ Reply

vladmart

7 years ago, # |

Can someone show an example code for the "Prize" task? I didn't understand how to interact with the system

→ Reply

7 years ago, # ^ |

90 pts clean code

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
int find_best(int n){
	int mx = 0;
	for(int i = 0 ; i < 500 ; ++i){
		vector < int > res = ask(i);
		if(res[0] + res[1] == 0){
			return i;
		}
		mx = max(mx , res[0] + res[1]);
	}
	int i = 500;
	while(i < n){
		vector < int > res = ask(i);
		if(res[0] + res[1] == 0){
			return i;
		}
		if(res[0] + res[1] == mx){
			int l = i + 1;
			int r = n - 1;
			while(l < r){
				int mid = l + r >> 1;
				vector < int > tmp = ask(mid);
				if(tmp[0] + tmp[1] == 0){
					return mid;
				}
				if(tmp[0] + tmp[1] < mx){
					r = mid;
				}
				else{
					if(res[1] - tmp[1] > 0){
						r = mid - 1;
					}
					else{
						l = mid + 1;
					}
				}
			}
			res = ask(l);
			if(res[0] + res[1] == 0){
				return l;
			}
			i = l + 1;
		}
		else{
			++i;
		}
	}
}

100 pts ugly code

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
bool done[200001];
vector < int > mem[200001];
vector < int > myask(int idx){
	if(done[idx]){
		return mem[idx];
	}
	done[idx] = 1;
	return mem[idx] = ask(idx);
}
int solve(int rsmall , int ql , int qr , int mx){
	if(ql > qr){
		return -1;
	}
	int l = ql;
	int r = qr;
	while(l < r){
		int mid = l + r >> 1;
		vector < int > tmp = myask(mid);
		if(tmp[0] + tmp[1] == 0){
			return mid;
		}
		if(tmp[0] + tmp[1] == mx){
			if(rsmall - tmp[1]){
				r = mid - 1;
			}
			else{
				l = mid + 1;
			}
		}
		else{
			r = mid;
		}
	}
	while(l <= qr){
		vector < int > tmp = myask(l);
		if(tmp[0] + tmp[1] == 0){
			return l;
		}
		if(tmp[0] + tmp[1] == mx){
			break;
		}
		++l;
	}
	if(l == qr + 1){
		return -1;
	}
	if(mem[l][1] - mem[qr + 1][1]){
		return solve(myask(l)[1] , l + 1 , qr , mx);
	}
	return -1;
}
int find_best(int n){
	int mx = 0;
	memset(done , 0 , sizeof(done));
	int groups = 460;
	int small = n / 460;
	int large = small + 1;
	int cur = 0;
	vector < int > ids;
	ids.clear();
	for(int i = 0 ; i < groups ; ++i){
		vector < int > res = myask(cur);
		mx = max(mx , res[0] + res[1]);
		if(res[0] + res[1] == 0){
			return cur;
		}
		ids.push_back(cur);
		if(i < (n % 460)){
			cur += large;
		}
		else{
			cur += small;
		}
	}
	done[n] = 1;
	mem[n] = {mx , 0};
	ids.push_back(n);
	for(int i = 0 ; i + 1 < ids.size() ; ++i){
		int x = ids[i];
		int y = ids[i + 1];
		int res = -1;
		if(mem[x][0] + mem[x][1] == mx && mem[y][0] + mem[y][1] == mx){
			if(mem[x][1] - mem[y][1]){
				res = solve(mem[x][1] , x + 1 , y - 1 , mx);
			}
			else{
				res = -1;
			}
		}
		else if(mem[x][0] + mem[x][1] == mx && mem[y][0] + mem[y][1] < mx){
			while(y >= x){
				vector < int > tmp = myask(y);
				if(tmp[0] + tmp[1] == 0){
					return y;
				}
				if(tmp[0] + tmp[1] == mx){
					break;
				}
				--y;
			}
			if(y == x - 1){
				res = -1;
			}
			else{
				if(mem[x][1] - mem[y][1]){
					res = solve(mem[x][1] , x + 1 , y - 1 , mx);
				}
				else{
					res = -1;
				}			
			}
		}
		else{
			while(x <= y){
				vector < int > tmp = myask(x);
				if(tmp[0] + tmp[1] == 0){
					return x;
				}
				if(tmp[0] + tmp[1] == mx){
					break;
				}
				++x;
			}
			if(x == y + 1){
				res = -1;	
			}
			else{
				if(mem[y][0] + mem[y][1] == mx){
					if(mem[x][1] - mem[y][1]){
						res = solve(mem[x][1] , x + 1 , y - 1 , mx);
					}
					else{
						res = -1;
					}
				}
				else{
					while(y >= x){
						vector < int > tmp = myask(y);
						if(tmp[0] + tmp[1] == 0){
							return y;
						}
						if(tmp[0] + tmp[1] == mx){
							break;
						}
						--y;
					}
					if(y == x - 1){
						res = -1;
					}
					else{
						if(mem[x][1] - mem[y][1]){
							res = solve(mem[x][1] , x + 1 , y - 1 , mx);
						}
						else{
							res = -1;
						}			
					}
				}
			}
		}
		if(res != -1){
			return res;
		}
	}
}

→ Reply

EdwardSnowden

7 years ago, # |

+38

Congrats I_Love_Tina on g̶e̶t̶t̶i̶n̶g̶ ̶a̶ ̶s̶i̶l̶v̶e̶r̶ ̶m̶e̶d̶a̶l̶ defeating Rudy1444.

→ Reply

Rudy1444

7 years ago, # ^ |

+14

→ Reply

I_Love_Tina

7 years ago, # ^ |

-54

It was obvious, actually.

→ Reply

unbelievable02

7 years ago, # |

← Rev. 2 →

-6

UPD Full Result

→ Reply

xuanquang1999

7 years ago, # |

+32

How to lost your medal: Solve problem Prize under the impression that the checker is not adaptive, random 5 times instead of 500 times, spent 3 hours trying to optimize the binary search part without realizing that the checker is adaptive. Profit.

→ Reply

sampriti

7 years ago, # ^ |

← Rev. 3 →

-8

I did the same fucking thing and didn't get time to do ~30 points subtasks for silver. :(

→ Reply

xuanquang1999

7 years ago, # ^ |

→ Reply

VladaMG98

7 years ago, # ^ |

Here is another example. I had Prize coded hour and a half in the contest, and it was correct with one tiny error: my bs was while l < r instead of l <= r, and I spent 3,5 next hours debugging it. I found my error literally minute until the end of the contest, fixed it, submitted, and then I realised I have commented a part of my code, for some kind of debugging. I deleted the comment, alt tabbed to the cms, but it was too late. In the analysis, that solution was accepted, without any changes. :(

→ Reply

Sehnsucht

7 years ago, # ^ |

+18

Oh God, these stories are scarier than any creepypasta.

→ Reply

latvian

7 years ago, # |

-30

When looking on the submission for Simurgh by 9-th placed Lukas Michel, we can observe, that he first solved subtasks 1-3 and in the very last submission only subtask 4. (Probably some other such submissions can be found)

Sure enough, in the rules we can read The score for each task will be sum of scores for its subtasks.

What is the reasoning behind such scoring? Sure, it benefits the participants. But, essentially, participants might produce multiple partial solutions, instead of one that solves all subtasks. What are your thoughts, community?

→ Reply

gongy

7 years ago, # ^ |

← Rev. 2 →

+10

It saves you the time and trouble of figuring out what subtask it is in your code. That's not what is being tested in IOI.

Also, this is the same rule as last year...

→ Reply

popoffka

7 years ago, # ^ |

+33

But, essentially, participants might produce multiple partial solutions, instead of one that solves all subtasks.

This has always been the case. For most problems and sets of subtasks, you can write a solution of the form

if input_looks_like_subtask_1():
  return brute_force()
elif input_looks_like_subtask_2():
  return solve_special_case()
else:
  solution_1 = apply_heuristic_that_doesnt_always_work()
  solution_2 = apply_another_heuristic()
  return whichever_looks_more_reasonable(solution_1, solution_2)

...and this is indeed what participants did, and indeed more or less what the jury expected them to do.

It's totally okay for participants to write partial solutions — indeed that is exactly what the entire concept of subtasks is for. Often it makes no sense to try to write a single solution that solves multiple subtasks: a reasonable IOI participant who cannot solve some problem completely might be able to solve subtask 1 with a bruteforce, and subtasks 2 and 3 might happen to be different special cases that can each be solved with a different special case solution. Requiring this participant to combine all three in a single file is just a waste of their time.

Thus the introduction of the "sum of scores of subtasks" rule doesn't really change anything about the spirit of the competition, but it does fix some awkward things that might happen without it, especially when feedback is broken (and I remember more recent IOIs where feedback was broken at some point than IOIs where it never was). Here's an anecdote that hits close to home: our own OVR in 2012 submitted a solution to some problem that solved subtasks A, B, C. Then feedback was broken (and never got fixed before the end of the contest), and OVR submitted another solution, which happened to solve A, B, D, but broke on C for some reason. Because of the broken feedback, he never learned about this until after the end of the context. (score(ABCD) — max(score(ABC), score(ABD))) would've been enough points to move him from bronze to silver, and the team wrote an appeal arguing that, if feedback was working as intended, he'd have noticed this and just submitted a "merged" solution that invokes his old one when ran on tests from subtask C. The appeal was almost granted, until someone from the jury noticed that the second submission was made less than a minute before the end of the competition, which meant it was quite unlikely he'd have managed to do the merging in time, so the appear was eventually denied. Had the new rule been in place back in 2012, Latvia would've had one more silver medal :)

→ Reply