Akikaze's blog

By Akikaze, 8 days ago, In English,

Model solutions are now available.
GreenGrape and I will write more about problem F, including an alternative data structures (still quite tight on time limit) ;)

1114A - Got Any Grapes?

Author: Akikaze, GreenGrape
Development: Akikaze, GreenGrape, neko_nyaa
Editorialist: Akikaze

Tutorial
Solution (Akikaze)

1114B - Yet Another Array Partitioning Task

Author: xuanquang1999
Development: Akikaze, xuanquang1999
Editorialist: xuanquang1999, neko_nyaa

Tutorial
Solution (xuanquang1999)

1114C - Trailing Loves (or L'oeufs?)

Author: Akikaze
Development: Akikaze, majk, _kun_
Editorialist: Akikaze

Tutorial
Solution (Akikaze)

1114D - Flood Fill

Author: neko_nyaa
Development: Akikaze, neko_nyaa, _kun_
Editorialist: neko_nyaa, _kun_

Tutorial
Solution 1 (_kun_)
Solution 2 (neko_nyaa)

1114E - Arithmetic Progression

Author: Akikaze
Development: Akikaze, GreenGrape
Editorialist: Akikaze, xuanquang1999

Tutorial
Solution (Akikaze)

1114F - Please, another Queries on Array?

Author: Akikaze, _kun_
Development: Akikaze, GreenGrape, _kun_
Editorialist: Akikaze, GreenGrape, _kun_

Tutorial
Solution 1a (_kun_)
Solution 1b (Akikaze) [literally kun's solution, yet shorter, and a bit uglier :P]
Solution 2 (GreenGrape)

Read more »

 
 
 
 
  • Vote: I like it  
  • +148
  • Vote: I do not like it  

By Akikaze, history, 13 days ago, In English,

TREMBLE BEFORE THE MIGHTY OMEGALULGRAPE

Hello Codeforces!

We are honored to invite you to Codeforces Round #538 (Div. 2), which will take place at Feb/10/2019 17:05 (Moscow time). The round will be rated for all Division 2 participants (with rating less than 2100). Still, we warmly welcome Division 1 participants to join us out of competition.

You will be given 6 problems to solve in 2 hours. The round's problems were initially prepared by Duy-Bach Akikaze Le, Xuan-Tung neko_nyaa Nguyen and Xuan-Quang xuanquang1999 D. Nguyen.

There will be an interactive problem in this round. Learn more about interactive problems here.

This is our first attempt in making a Codeforces round, so suggestions are much welcome to help us improve ourselves. ;)

We also want to thanks many friends for making this round possible:

  • Dmitry _kun_ Sayutin for coordinating the round, providing a neat idea on one problem and some Russian translations.
  • Andrew GreenGrape Rayskiy for various suggestions on the problems, some other Russian translations, and most importantly, peacefully submitted himself to be quarantined from pretests. ;)
  • Michal majk Svagerka for testing the round.
  • And last but not least, Mike MikeMirzayanov Mirzayanov for the amazing Codeforces and Polygon platform, without which this round would never be possible :D

P/s: I will be at the Discord CP Community to discuss the problems after the coding phase. However, please follow the rules and don't discuss the problems during the contest by any means.

Wish everyone good luck and high rating!

UPD1: Score distribution: 500-1250-1500-2000-2000-2750

UPD2: Editorial is published.

UPD3: The contest is finished. I apologized for the "somewhat" weak pretests at here and there. Anyway, time to celebrate our winners ;)

Official participants:

  1. xlk200
  2. vasilescu_mihai
  3. Cinro_9baka
  4. africamonkey
  5. 2019_BecameMaster
  6. cdsfcesf
  7. yww_AFO
  8. hr_tian_xia_di_2
  9. JZmster
  10. chinmay0906

Div.1 + Div.2 participants:

  1. Hazyknight
  2. tfg
  3. tempura0224
  4. xlk200
  5. sava-cska
  6. mango_lassi
  7. I_love_Tanya_Romanova
  8. ec24
  9. vasilescu_mihai
  10. Cinro_9baka

Read more »

 
 
 
 
  • Vote: I like it  
  • +570
  • Vote: I do not like it  

By Akikaze, history, 5 weeks ago, In English,

Since the original data has been lost during the dark days of Codeforces, no version of the editorial has been re-released, and I feel the round itself is quite educational, so I decided to give a try.

390A - Inna and Alarm Clock

Approach
Solution 1 (Map)
Solution 2 (Array)

390B - Inna, Dima and Song

Approach
Solution

390C - Inna and Candy Boxes

Approach
Solution

390D - Inna and Sweet Matrix

Approach
Solution

390E - Inna and Large Sweet Matrix

Approach
Solution

Read more »

 
 
 
 
  • Vote: I like it  
  • +37
  • Vote: I do not like it  

By Akikaze, history, 4 months ago, In English,

First note: All observations are from my computer screen with the resolution of 1366 × 768. OS is Windows 10, browsing Codeforces using Google Chrome and coding using Code::Blocks 17.12. People with high-end computers/monitors or different software usages might experience differently or less inconvenient, yet the problem itself is still there.

TL;DR: The source codes presented through the "block code" format in Codeforces blog post should be made slightly smaller in terms of font size, and with less line spacing. A suggestion might be making it similar to the source code presented in the submission pages.

Many problem setters prefer showcasing model solutions on spoilers and direct sourcecode-formatting on blog posts (most notable ones are PikMike and Vovuh). I myself particularly enjoy this design, since the source code is collapsible and you won't lose the editorial tab you're watching (clicking any external links normally will not open it in a new tab, so sometimes it'd be annoying). However, the way the source codes are formatted seems to discourage some people (including me) from reading it.

I know reading source codes should be the last resort, if the editorial texts failed to explain things to you or the implementation intended in some parts was too complex that words couldn't make it. However, there has to be some times for some people to rely on this feature, and if that time comes, it should be made right.

Let's take the editorial blog post of Codeforces Round #515 for example.

Our target is problem D's solution by Vovuh.

Let's assume that I'm a newcomer intending to read the model solution. And this should be how the webpage is positioned when I open the source code (even this one is quite optimal):

Doesn't seem right. I can't even read the main function yet (the I/O optimization doesn't make up anything of the solution, and the find() function above is obviously not the total solution).

And by my estimation, the full solution takes up 1.5 screens. For anyone that have solved 1066D - Boxes Packing, the model solution can't be that tremendously long right?

So I copy-pasted the solution and submitted it to some random problem (I don't want to get another AC, just to test the source code representation). And this is what I have (submission link here):

It fits in just right. Difference in the very same platform.

Let's take another example. The target is the editorial blog post of Educational Codeforces Round 53 — to be specific, problem G and its model solution by adedalic.

And I have this:

Oh great. Now I can't even read anything further than macros and constant declarations.

To be honest, this one is a long solution indeed (compared to model solutions for casual problems). Let's diagnose deeper.

I copied the source code into my IDE. The source code is 175 lines long, and a screen in my IDE can show 39 lines:

Previewing it in Codeforces' submission page results in this (the link is here):

54 lines of source code visible. Technically it's similar to my IDE, just the full screen makes the result better a bit.

And in the blog post:

36 lines. 33.33% fewer than the submission pages. The rate is incredibly high.

Then what causes such differences?

Looking into the two screenshots again, we can see two points:

  1. The font size in the blog post is slightly bigger than in the submission pages. This one might be neglected in some extents, since smaller fonts might affect people with low visibility. Still, if the submission pages work right, then why can't the blog post be the same?
  2. This one is much more significant. The line spacings in the blog post is way wider and unnecessary. In the submission pages, the line spacing's width is from about to that of the line itself, while it's about the size in the blog posts.

Why am I complaining about this? How could the codes being presented in more spaces discourage people from reading it?

Let's make it simple. The model solution, hence its name, is something people would look at, not just to learn about the algorithms for the problem, but also coding experience from the problem setter himself/herself.

Let's assume every setter has for oneself model solutions which are nice, short and clean (as far as he/she can achieves). The short quality is ruined critically by the formatting. Imagine it, the source code is made one-third longer than usual, causing the hallucinogenic effect that makes people more prone to give up reading (since we all naturally feel tired within ourselves to read something long, at some extents depending on each individual). Therefore, the effect and purpose of publishing the source code is halved, and of course, the good efforts created by the setters are poorly wasted.

A solution for this issue can be simple. As I might have stated implicitly throughout the post, there exists two types of formatting source codes, one is worse in terms of UX than another — so why can't we replace it with the better one?

These are my analysis and opinions. I hope the administrators/moderators of the platform will look into this and provide some solutions to improve the satisfaction for both the users and the setters/solution writers.

Best regards.

Read more »

 
 
 
 
  • Vote: I like it  
  • +32
  • Vote: I do not like it  

By Akikaze, history, 5 months ago, In English,

I've just seen this in the Problemset's standing page:

Also, as I noticed, many submissions have been literally disappeared from the status (at least, all of my submissions from Codeforces Round #500 (Div. 1) [based on EJOI] were all gone as well — the status page of that contest only contains not even close to 700 submissions!).

Can anyone tell me what's going on with Codeforces? Just maintenance, or some attack is underway?

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By Akikaze, 15 months ago, In English,

FYI, for an array of distinct numbers from 1 to N, a permutation of this array is called "identity permutation" if there are no indices i such that p[i] ≠ i.

The term "almost-identity permutations" is based on the definition in 888D - Almost Identity Permutations.

I, along with comsv5k, used to solve a similar problem: 101503K - Extrasensory Perception. In short, you are given two integers K and N (both lower than 100, and K is lower than N), and you must calculate the frequency of almost-identity permutations of size N with exactly K indices i such that p[i] = i.

Here is our solution for the problem:

(Implemented in Python 2, and got accepted, original submission link: 31106584)

However, I'm uncertain as if the formula should return the correct number of permutations (showed in variable "mo" before being divided by the GCD of it and "de", provided there are unlimited time to execute the code), as we found out the algorithm through brute-force with the size from 1 to 10 and conclude with an incomplete mathematical induction.

So perhaps I'll leave this as a discussion here.

Was our approach correct (as it could return the right answer in every case)? Is there an alternative, shorter formula that provide the same output?

Thanks for all your replies. And sorry if my English is bad and difficult to read ;)

Also, sorry about the variable names in the source code. I wasn't in good conditions while implementing it, and had nearly screwed everything up. :<

Read more »

 
 
 
 
  • Vote: I like it  
  • -9
  • Vote: I do not like it