Sazzon's blog

By Sazzon, history, 4 years ago, In English

Hi, it has been a long time since I've last posted anything here and, as usual, I'll talk more on the human level rather than just being a technical post.

The fate of every competitive programmer is someday (hopefully far for now) you'll retire! The reasons behind it can be multiple.

  • You got a fulltime job
  • You graduated
  • You got kids or
  • You are just sick of getting hacked on 2 out of the mere 4 questions you passed on every god damn contest!

The fact is: now you are getting rusty, slow and dumb. You may think that's not that bad. Your coworkers still didn't put as many struggling hours of problem-solving as you did in the past, you can still solve hard questions that everyone just gives up right away, you are really good in understanding the head of your partners in code and can fix their bugs by just clearing their heads and helping them out. But that's just you lowering the bar and getting used to the software development life unconsciously.

If you think about it, you are not as sharp as you used to be. You take longer to figure out optimization solutions, you are getting sloppy and code slower. Let's face it, not every day you encounter an interesting problem just like the old ones. That's not the case for everyone, of course. Some of you have the privilege of getting constant interesting problems, but they are not small and constant as they used to be. And that's normal, the software industry is more focused on developing a scalable, fast and reliable product instead of targeting a new problem every day.

And that's not all bad. You are learning new things. Software development useful things. But your heart is the same, right? The competitive flame inside you is still burning. You are eager to get your hands on an amazing insight that solves a nice problem. You still want to feel that sensation of solving something hard cleverly. You want to still be able to solve those questions with the same (or maybe close to) speed of thought as you once had.

But for that to happen, we all know that practice is needed. And fitting practice time as we did in the past is totally impracticable. You just don't have the time for it. You need to take care of your health (that you neglected for so long). You need to invest time in your relationships with your family, spouse, kids, and dogs (or kittens (; ). And on top of all that you still have to work and learn new things to be productive on.

If you fit this profile that I just laid out, please share your everyday habits on how to still practice and maintain your sharpness from competitive days. How your teammates are doing today? Do you still get together and code? How these habits changed your work code?

I'd love to read them! Be nice in the comments and thank you for sharing!

Full text and comments »

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

By Sazzon, history, 5 years ago, In English

Hello codeforces,

as you may know, the famous book "Looking for a challenge?" is quite beloved by our community, given it has really interesting/hard problems and editorials from problem's writer itself.

Recently I got back to my copy, craving to know if I could solve it entirely. On each question statement, the book gives you a URL for that particular question. The problem is, they are outdated. The last time I tried to upload a solution to that URL, at least it gave me another option to it. But now, this is what we see:

For those who don't know polish (Or don't know the magic of google translate), this domain is no longer being properly used to host the questions.

After searching through the web (also here), I couldn't find the site that I once visited, and fortunately I found! Here it is:

Since some of you do not have a copy yet, the value of the book is in each writer's explanation (which I'm not allowed to make it public) of their question and lastly the questions are public to be solved, I took the time to gather the links to those precious (and freaking hard!! ò.ó) questions:

  1. Ants
  2. Hyperclock
  3. Fishes
  4. Pilots
  5. Skiers
  6. Barricades
  7. Travel Agency
  8. Mushrooms
  9. Sweets
  10. Coding of permutations
  11. Rooks
  12. Monkeys
  13. Plotter : your help comes here
  14. Termites
  15. Window
  16. Altars
  17. Axes of Symmetry
  18. Leonardo Numbers
  19. Ritual : your help comes here
  20. Questions
  21. Chocolate
  22. Fibonacci sums
  23. The search : your help comes here
  24. Hashing : your help comes here
  25. Afternoon tea
  26. Kangaroos
  27. Sums
  28. Superknight
  29. Ice skates
  30. Termites 2
  31. Cave
  32. Shuffle
  33. Game of tokens : your help comes here
  34. Straight lines
  35. Guilds
  36. Reconstruction of byteland
  37. Army training
  38. Riddle
  39. Fuel
  40. Ploughing
  41. Canoes
  42. Painter's studio
  43. Triangles : your help comes here
  44. Triangles 2
  45. Circular game
  46. Byteland
  47. Cakes
  48. Building blocks
  49. Matching
  50. Party : your help comes here
  51. Dice
  52. Two parties
  53. Guesswork : your help comes here

For those eagle eyed readers, some questions I couldn't find there, I'm sorry =(

But fear not! If you have the particular missing link, please leave a comment so we can make it complete. Also, if you found anything wrong on this list, let me know so I can fix it (It's a pretty long list and I'm tired from working all day).


PS : Thanks to my amazing friend and teacher that loaned me this book and never asked it back (I could give him props, linking his account, but he has like 30 different candidate master accounts, so ... enough of lists ¯\_(ツ)_/¯).

Full text and comments »

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

By Sazzon, history, 7 years ago, In English


on today's Educational Round I came across a problem that made me a bit sad..

On the problem Two Seals I submitted this code.

As you can see, on the third input it fails. But when I run this code on my machine with the following CLI

g++ -o [object] [code.cpp] -std=c++11 -Wfatal-errors

It returns me the correct answer for this test case. Can someone help me figure out what am I missing on CLI or compiler option here on codefoces (So I can prevent myself from doing it again) ?

It really made me sad, what if it was a rated round ? My dreams would have been crushed.

Thank you for your time.

PS: I'm using GNU C++14 here on codeforces.

Full text and comments »

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

By Sazzon, history, 7 years ago, In English


as usual, when you ask someone in codeforces tips on how to improve with the most amazing feature of this site has (that's constant contests rounds), they are all equal: compete, read all problem statements and then read the editorial to solve the unsolved ones. I follow this step by step, but when I reach the last one I fail completely.

What I mean is, why is so hard to understand most (Most because from the top of my head I can recall really good editorial writers like zscoder and Errichto) of editorials here ? Sometimes is like the contest writers want us to get inside their brain and understand what they mean by some paragraph. I get it, is really difficult to be great in explaining things, maybe the hardest thing in the job of creating a contest.

But sometimes I think it only requires time and effort. Some of the most interesting contest & editorials I've seen had depictions of how the idea of the algorithm works, or lots and lots of tips before giving it out, or even displaying the content needed to be already understood to get this question right (which is one of the most effective, for me =] ). It's really not great to try your best to improve on some contest and fail at the final step, even if you read 20x the same paragraph you wont understand.

I'm glad we are here as a community and everytime I stumble on a difficult explanation, I quickly go to the comment section and find about 3 comments teaching their way of doing it and they are crystal clear! Also 5 comments complaining of how difficult it is to understand what was written, and most of the time the author is there to help out, but if the editorial was written more carefully this wouldn't be necessary at all.

I think what is missing is empathy. Empathy on how the people that did not solve that question is going to read that explanation. Those are your targets. People that don't really understand and maybe don't have the background to get the idea as you, problem setter, do. Focus on how you are going to explain a idea of your algorithm to a person that is not a programmer, try to explain with figures, with tips, use everything in your hands. After doing so, ask some friend of yours, to try understand your text and explain it to you and so on.

Teaching is hard, really hard, but rewarding. I think the community would really improve with great editorials.

Does someone experiencing this too? Let's discuss it. Help our writers to improve too.

To problem setters: get this post as a constructive critique. The job of creating good and interesting contests are really hard alone, but don't forget to put the same effort on the explanations. Cheers!

Full text and comments »

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

By Sazzon, history, 7 years ago, In English

Hello, and welcome to another insecure blog entry of mine.

Lately I've increased my study by being motivated by interesting problems, nice blogs and community here, and also by a endless urge to excel my knowledge. All of this helps me get through some though times when I'm stuck in a particular problem or technique. But this isn't the same on my teammates.

I've already instigated them to participate more here, or to look for interesting problems as well as teaching each other, but it seems not quite effective. Maybe the problem is with me, maybe I'm too focused and they are not. Maybe they want different things right now in their life and their focus are on other things, like earning some money developing stuff to someone, or even they are too comfortable thinking they are the best in our sub-regional (which I think is a huge trap).

Don't get me wrong, they have a huge potential of being one of the best and together achieve a lot and I have absolute faith on them, but recently this faith and this potential are being put to test by lack of study.

Sometimes I can be very harsh in my critiques just to maybe put them to work so we can grow together, but more than one time this was treated as some kind of bossy action, and I don't blame them.

Have you ever being in this situation before? What should I do to get them on tracks again? Give me tips to get them working again and also not be a total jerk while doing it.

Thank you for your time! Be gently in the comments.

Full text and comments »

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

By Sazzon, history, 7 years ago, In English


An interesting problem appeared at work today. I've managed to reduce the problem into what seems to be a solvable problem. Here it is:

Given an resultant array A of C elements and a list of N arrays, also with C elements. Is there a way to sum a subset of the N given arrays such that every element in the i-th position is summed with the element on the i-th position of the other array and result in the given array A? Let me give you an example:

C = 3

N = 6

A = {2,1,1}

N arrays:

1 = {1,0,1} 2 = {1,1,0} 3 = {1,0,1} 4 = {1,0,0} 5 = {0,1,1} 6 = {0,1,0}

The best answer is both 1 and 2 or 2 and 3. If we sum 1,0,1 + 1,1,0 = 2,1,1 or 1,1,0 + 1,0,1 = 2,1,1.

Have you ever came across a problem like this ? Is there any problem here in codeforces which has the same solution or editorial ? Do you know any technique that maybe useful for this purpose. If you have any input, please feel more than welcome to share.

Thank you in advance :-)

Full text and comments »

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

By Sazzon, 7 years ago, In English

Hi everyone!

Recently I've been taking notes on my behavior during contests (It can be some round here in Codeforces, Hackerrank or even at ACM-ICPC sub-regionals) and trying to come up with a way to setup my brain to perform well. Sad thing is: I get too nervous .

My first attempt in a competitive envoriment was in 2014, an Brazillian ACM-ICPC sub-regional (not a very intense envorioment as you may guess). I was there, me and my colleages. No hopes on getting a good place. Just for fun. Trying my best to prove something to someone, I don't know. For our surprise, we came in 4º out of 31 teams. That was a great result for our first try! But one year later, with other teammates (better ones, in my opinion!) and after one entire year of intense studying (I was definetly more prepared) we came in 5º place. I was personally devastated. I couldn't pass even the easy ones, my teammates helped a lot and basicly carried me entirely.

Also I'm on a streak of highs and lows on contests here. All of them I get the feelling that a can do better in the next one (which I do in some of cases and others ... not so much). The thing I noticed was: If some contests is really important to me and I have big expectations on my performance, I do worse than I thought. If not, I get my regular performance.. It seems that if I try to be calm and ready to do well and I fail 1 single time during the contest I get on spiral of failure that only seems to get worse. Like a paradox, if I force myself to do well, I do worse. Otherwise I do regular (most of the times).

PS: My latest results that prove this behaviour was the last contest of 2016 here. I wanted to start 2017 with the right foot and do well in this one and change my rank: Solved 1 out of 8. Joined this hacker earth contest with no hopes of getting a good place or even 2 questions right: Solved 3 out of 6...

PS2: And is not even about my knowledge barrier. Some questions I do naive errors or overkill questions. Or my mind is blocked during contest time and I can't solve an easy problem (I can solve it even after minutes out of contest area ...).

I can't be the only one, please!

Is this ever happened to you ? What did you do to overcome this problem ? Did you overcame this with time and patience or it was just a change in your mindset ?

Please share your thoughts and behaviours so me and other troublesome people can be as good as you are.

Sorry for the long post! Happy New Year !!


Full text and comments »

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

By Sazzon, history, 7 years ago, In English


I'm currently trying to improve my problem solving skills to score high here! Recently a friend of mine suggested that I should start solving the a2oj Ladder (which I am!). But I started noticing that most of the problems there are from old rounds and 90% of those are pretty easy. It gets harder along the way or should I try something else ?

Thanks in advance for any nice tips!

Full text and comments »

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

By Sazzon, history, 7 years ago, In English

Olá todos!

Esse é o primeiro editorial feito pelos alunos da UECE no Codeforces. Esse contest foi criado como um treino do grupo de estudos da maratona. A seleção das questões do UVa, organização do contest foi feita com muito empenho pelo alissonrgs. Obrigado especial aos que ajudaram a fazer este editorial: wjoao, Lamartine e novamente ao alissonrgs.

Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. Em último caso vejam o código.

Sorry for the lack of translation, we are from Brazil and the group is closed. Don't downvote this post just because you don't understand the language. We are using the platform to communicate internally. Please be nice ! :-)

Burguer Time?

Pré-requisitos: Nenhum

O problema é facilmente resolvido se pensarmos que se houver um restaurante e uma farmácia no mesmo local (se houver um caractere 'Z' na string) a distância mínima já vai ser 0. Se não houver, basta iterar por toda a string guardando a posição da última aparição de 'R' e 'D'. Quando uma nova posição aparecer, verificar se a distância entre os 2 atuais é menor do que a anteriormente calculada.


Complexidade : O(n)

*n sendo o valor de L na questão.

Autor : Filipe Herculano Rocha


Pré-requisitos: next_permutation

Para resolver essa questão vou usar dois métodos da biblioteca padrão: sort() e next_permutation(). O sort vai fazer a primeira string e o next_permutation vai gerar a próxima permutação da string inicial, na ordem lexicográfica. O problema é que a questão quer em ordem alfabética, então “Ba” virá antes de “aB”, dando resposta errada. Meu truque foi fazer um vetor com valores relativos aos caracteres, de modo que a string AaBbCc… vire o vetor {0,1,2,3,4,5...}. Daí, uso sort e next_permutation nesse vetor. Na hora de imprimir, verifico se o valor é par. Se for, então é maiúsculo. Senão, minúsculo.


Complexidade : O(n!)

*n sendo o tamanho da string.

Autor : Lamartine Cabral

Euclid Problem

Pré-requisito: Algoritmo de Euclides extendido

Esse problema é a aplicação prática do algoritmo de Euclides extendido.


Complexidade : O(log n)

Autor: Filipe Herculano Rocha

Laser Sculpture

Pré-requisitos: Nenhum

Com uma simples passada por todo o vetor com as alturas finais dos blocos, nós conseguimos o resultado. Dado uma altura de um bloco i (0 <= i < C) em um vetor v, se o bloco for o primeiro, deve-se somar ao contador abs(A-v[i]) . Caso i não seja o primeiro, deve-se verificar se ele é menor que o bloco anterior e se for soma-se ao contador abs(v[i]-v[i-1]) . O motivo é que raios são comuns em alturas superiores à direita, porém não são comuns quando a altura é menor.


Complexidade : O(n)

*n sendo o valor de C na questão.

Autor : Filipe Herculano Rocha

Maximum Product

Pré-requisitos: Nenhum

Como o tamanho máximo do vetor é N = 18 (bem pequeno), uma solução possível era testar todos os conjuntos existentes. Com um loop para representar o tamanho do conjunto a ser testado (1 <= i <= N), bastava realizar mais dois loops com os valores do vetor, um de (0 <= j < N) e o outro com o tamanho do conjunto (j <= k < j + i), multiplicava os valores do conjunto e no final testava se o valor era maior.


Complexidade: O(N^3)

Autor: Alisson Soares

Where is the Marble?

Pré-requisitos: Ordenação, busca binária, lower_bound

Para achar a solução da questão, tinha que receber os N elementos, e ordená-los. Após isso receber Q consultas, cada uma delas, tinha que retornar o índice do número e se existir mais de um número igual, pegar o menor índice, no vetor ordenado.

Para se ordenar um vetor, pode-se usar a função sort.

Ex: int vetor[n]; sort(vetor, vetor+n);

Para realizar a busca binária em um vetor ordenado, você pode usar o lower_bound do cpp:

Ex: int *p = lower_bound(vetor, vetor+n, valor_buscado);

Obs: Detalhe que o lower_bound retorna um ponteiro para a posição do vetor, onde está o elemento encontrato, e caso ele não exista, ele retorna para algum número menor que o número buscado, e o mais próximo dele. Logo ao fazer o lower_bound, é necessário verificar se o valor de *p é igual ao valor da busca. Se for igual é porque foi achado e é necessário achar o indice e para isso é necessário apenas fazer uma operação de ponteiros, diminuindo p por vetor( A posição atual do ponteiro no meio do vetor, menos a posição do ponteiro inicial do vetor ) e o resultado disso é o indice, baseado em 0. Caso não fosse igual, o elemento não teria sido achado.

Complexidade : O(n*log n + q*log n)

Código com busca binária

Autor : Filipe Herculano Rocha

Código com lower_bound

Autor: João Vitor

Zeros and Ones

Pré-requisitos: Prefix Sum

Como a string tinha apenas 1s e 0s era possível aplicar a soma de prefixos, assim usando um vetor, bastava passar uma única vez por toda a string e ir somando o valor da posição da string com a posição anterior do vetor ( sum[ i ] = str[ i ] + sum[ i-1 ] ). Feito isso as consultas ficam O(1), pois para uma consulta de i até j com j > i, basta calcular ( sum[ j ]-sum[ i ] + s[ i ] ), se for igual a diferença dos índices ( j — i + 1 ) é porque todos os valores na string são 1s, e caso for 0 é porque todos os valores na string são 0s.

Esse problema também era possível com força bruta, a cada consulta bastava fazer um ‘for’ verificando se uma posição no vetor era diferente da anterior, caso fosse é porque a sequência não é de mesmos dígitos, caso contrário sim.


Complexidade: O(n+q)

*n sendo o tamanho da string e q sendo a quantidade de queries

Autor: Alisson Soares


Pré-requisitos: Bit — Fenwick Tree

Utilização básica da bit. Usa-se o operador de Update em um ponto. e de Query para saber o resultado da soma entre intervalos.


Complexidade: O(n*logn + q*logn)

*q sendo a quantidade de queries na BIT.

Autor: João vitor

Full text and comments »

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