#icpc2016

[progcompcl]

Open complaint letter to ICPC Latam (UPDATED)

UPDATE 1 (2016-11-17): After a formal appeal by the coach of the involved team and some members of Universidad de Chile, the ICPC Latin American Steering Committee decided to revoke the disqualification of the team. The formal response, which is completely transcribed at the end of this letter, is summarized in the following sentence by the ICPC Director of Contests, Latin America

“By trying to preserve the contest’s integrity and reputation, we have failed to prevent an injustice that we now correct.”

We sincerely thank the ICPC Latam Steering Committee for considering all the facts and point of views in this new decision.

UPDATE 2 (2016-11-17): The answer to this letter from Ricardo Dahab is available in http://progcomp.cl/post/153324698674/acm-icpc-latam-answer-to-the-open-complaint

Dear Directors of ICPC Latam,

We hereby wish to present a formal complaint from the Chilean ICPC community, with regard to the disqualification of the Chile-14 team, “El Equipo de Paulsen”, which represented Universidad de Chile in the South America/South regional contest held on Saturday, November 12th 2016.

The facts:

A paper titled “Wavelet Trees for Competitive Programming” was published at the IOI conference 2016, with Robinson Castro, Nico Lehmann, Jorge Pérez and Bernardo Subercaseaux as authors. The paper showed several applications of the Wavelet Tree data structure for ICPC-like problems.

Jorge Pérez is the coach of the Chile-14 team, and Robinson Castro is one of the team members.

Nico Lehmann proposed a problem for ICPC Latam 2016 which could be solved with Wavelet Trees. This problem was accepted to be included in the 2016 contest as problem E, called “Emission Spectrum.”

The night before the contest, the Latin American committee raised the alarm on the existence of the aforementioned paper claiming a possible conflict of interest, thus decided to remove problem E from the 2016 contest.

Ultimately, the committee asked the team Chile-14 to voluntarily resign to compete thirty minutes before the start of the contest. The Chile-14 team did not resign, hence the committee decided to disqualify the team.

This has been both an unexpected and unfortunate situation for us. We would like to stress very clearly that we do believe that by no means the Chile-14 team and Nico Lehmann sought to profit from the situation described above, or to behave in ways against the integrity and reputation of the ICPC contest. Nico Lehmann disseminated his work on Wavelet Trees well beyond Universidad de Chile, and therefore we consider that his sole mistake in this situation is that he should have strived to disseminate the paper presented at the IOI conference even further than he did before the ICPC contest took place.

Our point of view

First of all we want to state the following:

We trust that before the contest, the Chile-14 team was completely unaware about the ideas, contents and format of Problem E that was going to be included, or any other problem in the contest in that regard.

We trust that the intention of Nico Lehmann was not to propose a problem to give an unfair advantage to some teams over others, but only to propose a challenging problem for all the teams in Latam, and he had no intention to hide possible conflicts of interest.

The above statements cannot be formally proven. We just want to make as clear as possible that none of us believe that there is anything beside an error and a misunderstanding and that we do trust that the mentioned members of our ICPC Chilean community acted honestly and honourably. We provide additional background and facts to support our claims in the next section of this letter.

We do believe that the Latin American committee made a bad and unfortunate decision on disqualifying the team in the way they did, and these are our main reasons to assert this:

Putting the integrity and reputation of the contest over the people involved. This is possibly the most important aspect. The official note by the committee stated that their decision was “in the interest of preserving the contest’s integrity and reputation”. In preserving that integrity they forgot that this contest is, over all the other things, an event for people, an event whose spirit is not to only state who is better than the other, but to friendly cooperate and learn together. In preserving the integrity and reputation of the contest they forgot that there is hope, dreams, and love for Computer Science in all the participants. When one puts the “reputation of an event” over the good and fair treatment of any of the members of a community, the ethics and values of a human competition are evidently hindered. In this case, the disqualified team was informed of the decision without even being listened to, considering only one side of the story. You may not understand how hopeless the participants felt in that moment, a feeling that is going to last for a long time, especially for one of the members for whom this was his last eligibility year to compete.

The timing of the communication. The team disqualification decision was informed to the affected contestants only a couple of minutes before the start of the competition. We acknowledge that the committee had a short time to decide its course of action, nevertheless, we consider that the severe decision taken was hurried, and communicated to the affected parties in a way that we deem improper. Given the time frame, a cautious way to proceed would have been to postpone any decision or communication regarding the involved team to be taken after the contest and after having conducted a thorough investigation. This is how these problems are usually resolved in other similar competitions.

The reason to put forward both, deletion of the problem and disqualification. It is indeed acceptable that the committee decides to remove a problem from the set if they think it would bring an unfair bias to the contest. This is in the contestants’ best interests. In that respect one may agree with the committee decision of deleting problem E given the known facts, and their belief that this would give an unfair advantage to some of the teams. Allowing the disqualified team in the competition would have not introduced any unfair bias to any of the other competing teams, besides potentially seeing more balloons in the scoreboard that would have been deleted if the team was disqualified later (but we know that this bias currently exists given that not all sites can see the scoreboard of other sites). But the committee decided to disqualify the team giving the message to the team that they have been disqualified because they cheated. Although the committee did not use those words, there is nothing else that a team could understand in a situation like this.

We think that the way in which the committee acted is giving several wrong and misleading messages to the ICPC community. In particular, the damage produced is not only to the mentioned team, but also to the whole community. From our point of view, the decision is against the very notion of sharing material, learning together, and developing new skills as a group. At least in Chile we have this spirit regarding ICPC, which can be witnessed very clearly by the letter that the team from Universidad de Talca wrote after the competition.

We expect that future decisions of the committee will be made considering the points we exposed, in order to preserve the spirit of the ICPC.

Background facts and information

We believe that there are important facts that were not considered by the committee at the time when the decision was taken. We acknowledge that they had very little time to decide but we would like to point out some of them.

About the Wavelet Tree

The Wavelet Tree is a data structure that is more than 13 years old (Grossi et al. 2003). In fact, “Wavelet Tree” is a new name for a data structure that has been used by the Computational Geometry community since the 80’s (B. Chazelle, 1998), and the paper by Grossi et al. (2003) only showed some new applications and a succinct implementation. Moreover, it is a standard data structure nowadays having an entry in the Encyclopedia of Algorithms (Grossi 2014), an extensive survey by Gonzalo Navarro (2012), several application papers, a wikipedia page, several blog posts, and has been already used by Asian contestants for some time. Several of the main functionalities of the Wavelet Tree, such as k-quantile and median queries, can be achieved with data structures like Persistent Segment Trees or Merge Sort Trees, techniques that are very well known by the more experienced programmers in our region, but still not widely used in countries with less experienced ICPC contestants.

Thus, the paper was not proposing anything new, not introducing an unknown topic but only making more accessible some techniques for less experienced contestants and increasing the possibilities for problem setters and judges.

Publication of the paper

Please notice that the paper “Wavelet Trees for Competitive Programming” was openly published (with all authors’ names and affiliations), there is public code available, the presentation of the paper was also public, and the venue was a typical venue to present applications of known data structures to ICPC-IOI problems. Other typical structures and algorithms, like the Hashing method for string processing, Fenwick Trees adaptation for Dynamic Range Minimum Queries, etc. have been presented in a familiar way for programmers in the same conference.

To test the problems for the Wavelet Tree in the mentioned paper, the authors contacted Brazilian and Mexican contestants to produce alternative solutions.

Several coaches and ICPC problem setters attended the presentation of the paper, including some Latin American members of our community. Also notice that the venue was the International Olympiad in Informatics, and Ricardo Anido (ICPC Latam, Director of Judging and Problem Committee) is a member of the International Committee of the IOI.

These facts show that had Nico Lehmann wanted to hide his connection to the paper, he made a terrible choice of a strategy. Actually, it seems to be exactly the opposite; the evidence shows that Nico’s intention was to disseminate the knowledge that he and his coauthors had generated with utmost enthusiasm.

People of the Chilean ICPC community endorsing this letter:

Claudio Álvarez Former coach, Universidad de los Andes, Chile

Diego Arroyuelo Coach, Universidad Técnica Federico Santa María, Chile

Ricardo Baeza-Yates Former coach, Universidad de Chile Former member of the Latin American ICPC Steering Committee

Jorge Baier Former coach, Pontificia Universidad Católica de Chile Former contestant and judge

Sebastián Barbieri Former contestant, ICPC World Finalist

Ricardo Barrientos Coach, Universidad Católica del Maule, Chile

Patricio Beckmann Coach, Universidad Diego Portales, Chile Former contestant

Miguel Campusano Former coach, Universidad de Chile Former contestant

Ruben Carvajal-Schiaffino Coach, Universidad de Santiago de Chile

Francisco Claude Coach, Universidad Diego Portales, Chile Former contestant, ICPC World Finalist

Felipe Contreras Former contestant, ICPC World Finalist

Dietrich Daroch Coach, Pontificia Universidad Católica de Chile Former contestant

Catherine Espinoza Chilean deputy leader IOI Former contestant

Camilo Garrido Coach, Universidad de Chile Former contestant

Andrés Letelier Coach, Pontificia Universidad Católica de Chile Former contestant

Francisco López Coach, Universidad de Santiago de Chile - Ingeniería, Chile Former contestant

Gonzalo Navarro Professor, Universidad de Chile Editor in Chief, ACM Journal of Experimental Algorithmics

Jorge Pérez Coach, Universidad de Chile

Mauricio Quezada Coach, Universidad de Chile Former contestant

Erik Regla Coach, Universidad de Talca, Chile Former contestant

Rodrigo Salas  Coach, Universidad de Valparaíso, Chile

Nicolás Sanhueza Former contestant, ICPC World Finalist

Diego Seco Coach, Universidad de Concepción, Chile

Romina Torres Coach, Universidad Andrés Bello Former contestant

Oscar Valdivia Verdugo Coach, Universidad Diego Portales, Chile Former contestant

Victor Vasquez Coach, Universidad Católica de La Santísima Concepción, Chile

References

R. Castro, N. Lehmann, J. Pérez, B. Subercaseaux (2016) Wavelet Trees for Competitive Programming, IOI Conference

B. Chazelle (1988) A functional approach to data structures and its use in multidimensional searching, SIAM J. Comp. 17 (3) (1988) 427-462.

R. Grossi (2014) Wavelet Trees, Encyclopedia of Algorithms, Springer Science+Business Media New York 2014

R. Grossi, A. Gupta, J.S. Vitter (2003) High-order entropy-compressed text indexes, In Proceedings of SODA 2003 pp 841–850

G. Navarro (2012) Wavelet Trees for All, In proceedings of CPM 2012: 2-26

Response from the ICPC Latam Steering Committee:

Dear Jorge, Éric, Ricardo and Gonzalo,

The ICPC Latin American Steering Committee has reached a decision regarding your appeal. Considering all the attenuating facts surrounding our decision to disqualify the UChile team, taken in a state of near emergency in the morning of contest day, we have decided to revoke the disqualification and consider the team’s solutions stored in the BOCA system as official. Had the team not been disqualified, it would have earned one of the 18 slots already assigned to Latin American teams. Fortunately, recognizing  the extreme circumstances of this case, Bill Poucher, Executive Director of the ICPC (in Cc), has allocated one extra Finals slot to the Latin America Region, which will be used to promote UChile’s team to the 2017 ICPC Finals in Rapid City, USA.

We hope that you recognize that our decision to disqualify the team was not taken lightly, neither with intention of harming the UChile team or Nico Lehmann. As we said in our statement that day, we acted “without risking any assumptions regarding the integrity of those involved in these issues”. We saw some real conflicts of interests that ought to have been put forward by Nico Lehmann regarding problem E, but were overzealous regarding the other problems. By trying to preserve the contest’s integrity and reputation, we have failed to prevent an injustice that we now correct.

Sincerely,

Ricardo Dahab ICPC Director of Contests, Latin America

[progcompcl]

Go Team 86! #SquashMasters #ICPC2016