text:
## Journal of Green Engineering

Vol: 5    Issue: Combined Issue 3 & 4

Published In:   July 2015

### An Outlook on Silicon Nanocrystals for Optoelectronics

Article No: 4    Page: 49-70    doi: https://doi.org/10.13052/jge1904-4720.5344

 1 2 3 4 5 6 7 8 9 10

An Outlook on Silicon Nanocrystals
for Optoelectronics

I. Capan1, A. Carvalho2, J. Coutinho3,*

• 1Rudjer Boskovic Institute, P.O. Box 180, 10000 Zagreb, Croatia
• 2Graphene Research Centre and Department of Physics, National University of Singapore, 117542, Singapore
• 3Department of Physics and I3N, University of Aveiro, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal

Corresponding Author: jose.coutinho@ua.pt

Received 5 November 2015; Accepted 3 June 2016;
Publication 1 August 2016

## Abstract

Silicon nanocrystals have emerged as promising material components which extend the realm of the application of its bulk counterpart beyond traditional boundaries. Over the last two decades of research, their potential for application on areas that range from optoelectronics to information storage has been progressively unraveled. Nevertheless, as technology steps forward, new challenges are arising. Here we consider what has been achieved and what are the current limitations on the fields of growth, characterization and modeling of silicon nanocrystals.

## Keywords

• Characterization
• modelling
• nanocrystals
• silicon

## 1 Introduction

Nanocrystals (NCs) have emerged as a successful route to control and access quantum phenomena. They are able to provide novel NC-based materials with unprecedented and spectacular properties, applicable to a wide field of areas ranging from solar cells, memory devices, thermoelectrics, light emitters, spintronic devices or printable electronics.

The use of semiconductor NCs instead of two dimensional floating gate devices like in standard complementary metal-oxide-semiconductor (CMOS) field effect transistors and memory devices, makes charge storage less sensitive to common problems such as leakage current and dielectric breakdown. At the same time allows an ultimate miniaturization, and consequently huge savings in power consumption, without electrical instabilities [1]. In particular, nanostructures offer significant breakthroughs in photovoltaics as they can easily overcome the thermodynamic efficiency limit of a conventional junction cell. In fact, it has been anticipated that quantum dot (QD) solar cells could reach power conversion efficiencies of up to 66% [2]. Much of this improvement comes from the ability of NCs to harvest light with specific wave-lengths, depending on their size, shape, or for example their surface coverage. A colloidal nanocrystal solar cell which combines all the advantages of organics (scalable and controllable synthesis) with transport properties comparable to traditional photovoltaic semiconductors has been demonstrated [3]. Different approaches have also been made to achieve light emission from group-IV semiconductor nanostructures. Despite the indirect nature of the band gap in bulk silicon, quantum confinement of electronic states in sufficiently small NC makes them essentially direct gap structures. This has led to efficient luminescence and electroluminescence of semiconductor nanostructures, including Si- and Ge-NCs embedded in an oxide matrix [4].

Theoretical research on group-IV semiconductor NCs was fundamentally triggered by interest in their optical properties [5&$x02013;7], particularly after a demonstration of quantum confinement in Si-NCs by Furukawa and Miyasato [8]. These authors reported the opening of the optical gap of small Si dots by more than 100% with respect to bulk Si. Within a “particle-in-a-box” description, the effect was simply cast as a power law Egap = Ebulk+α/Rn [9], where R is the particle size, α is a confinement factor and n is usually 1 <n< 2, depending mostly on the surface termination and host material (for a detailed description see Ref. 10). Despite its popularity, such an empirical approach overlooks important physical aspects such as the chemical nature of the NCs or the dielectric mismatch across their boundaries [11]. One important issue that has led to considerable debate relates to the screening effects within the NCs [12&$x02013;15]. An accurate theory for the dielectric screening is essential to understand the response of nanostructures and nanostructure ensembles to an external electro-magnetic field. Screening is also at the realm of electrical doping. It is now consensual that even for NCs with a diameter as small as 2 nm, the spatially averaged electronic screening within the core is virtually identical to that in bulk, decreasing to the vacuum value close to the polarized surface [16]. Confinement due to underscreening is essentially a surface/interface effect that manifests itself when the surface-to-volume ratio of the structures becomes large enough [14].

Many important questions related to impurities and surface chemistry are yet to be answered. In this respect, quantum-chemical modeling can play a decisive role. Atomistic-scale density functional theory (DFT) calculations of NC materials have been hampered for several reasons. Possibly the most important one stems from the sheer size of the problem. However, with the development of efficient linear-scaling density functional methods along with the steady drop of CPU-time costs, we are now able to solve by first-principles the all-electron problem of systems with a few thousands of atoms [17]. This has led to the understanding of more complex problems such as doping [18&$x02013;20] and electronic transport [21, 22]. These are among the advances that will be addressed below. ## 2 Growth and Characterization Among all semiconductor nanostructures for photovoltaics, the Si-NCs embedded in a SiO2 matrix have been the most studied in the last few years. One of the first approaches was to form layered structures, so-called superlattices, of Si-NCs produced by reactive evaporation [23]. Reactive evaporation, magnetron co-sputtering and ion implantation are techniques which enable us to control the size, ordering and space distribution of the embedded NCs. These growth techniques are briefly revised below, along with their benefits and limitations. However, it should be noted, that other important and wide-spread techniques are also used for the growth of Si-NCs, namely plasma-enhanced chemical vapor deposition (PECVD) and molecular beam epitaxy (MBE). From the experimental point of view, the synthesis of free-standing NCs will not be covered within this review. However, those issues are covered in the Section 3 of this paper, which deals with the first principles modelling of the NCs. ### 2.1 Magnetron Co-sputtering Magnetron co-sputtering is a technique for thin film deposition. Together with thermal evaporation and pulsed laser deposition (PLD), they are all fabrication methods based on the production of sub-stoichiometric oxides, with thermal evaporation being the simplest among them. The main difference between these techniques is the exact stoichiometry of the oxides produced. In particular, silicon oxide is thermodynamically unstable, and subsequent annealing will yield to the formation of Si-NCs embedded in silicon dioxide. As already mentioned, the first super-lattice approach for Si-NC formation was achieved by evaporation. Lately, the magnetron co-sputtering has become the most used technique for such structures. The NC’s size, distribution and shape can be easily controlled by varying sputtering time, composition of sputtered material, as well as the annealing temperature, time and atmosphere. Since NCs embedded in the oxide matrix have a large interface area-to-volume ratio, they show a high density of interface defects [24]. In such cases, the role of the interface and interface-related traps cannot be neglected. The interface traps are located at the substrate/oxide matrix interface (most commonly Si-SiO2) and at the NC/oxide matrix interface. Unlike the other traps located in the oxide matrix (fixed and mobile oxide charges), interface traps are in electrical communication with the underlying substrate, and therefore largely affect the electrical properties of such structures [25]. Passivation of deep levels caused by the interface is necessary before any NC-based devices become a reality. Vacuum annealing, which is commonly used for NC crystallization, is known to increase the density of the interface traps. However, most of the interface traps can be neutralized by means of a low-temperature (450C) anneal in a hydrogen or forming gas [25]. PLD is another technique for the deposition of high quality oxide thin films, and a huge effort has been devoted to the production of Si-NCs by this way. Martin-Sanchez et al. [26] have reported that crystallization of as-deposited amorphous Ge-NCs can be achieved by a relatively low and short temperature treatment, which significantly decreases the thermal budget, when compared to other growth techniques. Moreover, it implies that PLD should be considered as an excellent alternative to widely used magnetron co-sputtering technique for the deposition of complex oxide thin films and NCs. Another variation of this technique, the pulsed laser ablation (PLA) in liquid media has attracted a lot of interest in the recent years. The advantages of the PLA are numerous but still not fully exploited. In particular, PLA in liquid media is a very simple, fast and environment-friendly technique for the synthesis of colloidal semiconductor nanoparticles. ### 2.2 Ion Implantation The synthesis of semiconductor NCs by means of ion beams has been extensively studied in the past years [24]. NC size, shape and distribution can be controlled by varying the implantation conditions (implantation energy and dose) and subsequent annealing. A huge effort has been devoted to the understanding of the energy loss process and defect formation in implanted materials. The ion implantation introduces defects in materials, and it is a well-known fact that Si-ion implantation of SiO2 is characterized by the production of a large number of oxygen vacancies and other defects in the oxide matrix. These defects play a crucial role in the process as they enhance the NC formation and the formation of the sub-oxide interface states [24]. Ion implantation is inseparable from CMOS technology, and as such, it is desirable to use it not only for NC fabrication but for the doping of NCs as well. Doping of the NCs is one of the still unresolved issues which limits the applicability of NCs in optoelectronics. Over the past decade, phosphorus and erbium doped Si-NCs have attracted a great deal of attention, due to the promising optoelectronic applications from solar cells to optical amplifiers in telecommunications [27]. It has been shown that in order to study the donor doping and dependences of the photoluminescence (PL) intensity in such systems, it is crucial to understand and control the presence of defects. The effects of donors and defects to the PL of Si-NCs are strongly overlapping [28]. Moreover, it was reported that the decrease in the density of interface related defects may be produced by light phosphorus doping [29]. Another approach for doping semiconductor NCs could be found among techniques already used for doping their bulk counterparts, like neutron transmutation doping (NTD). NTD is a technique commonly used to dope bulk silicon, but for the NCs is not much explored. Recently, the promising application of the NTD for arsenic doping of Ge-NCs has been reported [30]. ### 2.3 Properties and Characterization To obtain all necessary information regarding the properties of NCs and their possible applications, it is desirable to perform a complete characterization that includes structural, optical and electrical specifications. Most characterization reports on semiconductor NCs start with transmission electron microscopy (TEM) data. This is a widespread and well-known technique, which gives extremely valuable structural information. TEM has been used to study Si-NCs produced by reactive evaporation in one of the first approaches in producing embedded semiconductor NCs, the so-called superlattice approach [23]. This method enables an easy and well-defined control over the particle size, density and ordering. Along with TEM, there are other useful techniques that can provide information regarding the structural properties of NCs. One of them is grazing incidence small x-ray scattering (GISAXS), which is a non-destructive technique for structural characterization of NCs supported on a substrate [31] and NCs embedded in a matrix [32]. The Si-NCs formed in the super-lattice structures have been successfully studied by means of GISAXS despite the fact that the difference in electronic density (on which GISAXS is very sensitive) between Si-NCs and silicon oxide is very small [33]. Figure 1 shows the schematic representation of a typical experimental GISAXS setup, with details given elsewhere [34]. A two-dimensional CCD detector placed perpendicular to the incoming beam (grazing angle of incidence) is used to record 2D GISAXS pattern. From the measured 2D GISAXS patterns, it is possible to determine the size, shape, inter-NCs distance and size distribution of NCs. Figure 1 Schematic representation of the GISAXS experiment. The sample is placed horizontally. The incident angle is denoted as αi. A 2D CCD detector is positioned perpendicular to the incident beam, and it is used to record SAXS intensity (so called 2D GISAXS pattern). A thin Al-strip (beam stopper) is usually placed in front of the central part of the 2D detector to avoid the overflow of the detector. Among all properties of semiconductor NCs, the optical properties have been the most extensively studied, usually by PL. Si-NCs often show strong luminescence intensity in the visible and near-infrared region. A size-dependent blue shift of the luminescence comparable to porous Si is well documented. Interaction of Si-NCs with Er ions has attracted a lot of attention due to the possibility of operating in the telecommunications band around 1.5 μm. Recent studies have shown that phosphorus doping can result in either a quenching or an enhancement of the Si-NC’s PL, depending on the dopant concentration and NC sizes [28, 35]. Crowe et al. [35] suggested the existence of competing pathways for the donor electron, which depend strongly on the NC size. For relatively small NCs, the tendency of phosphorus to accumulate at the nanocrystal-oxide interface results in a passivation of dangling bond type defects as evidenced by an enhancement of the integrated intensity and corresponding blue-shift of the emission peak. As the density of large NCs increases at the expanse of the smaller NCs, the majority of phosphorus atoms occupy substitutional lattice sites within the NCs and the luminescence enhancement rapidly diminishes. To check the transport properties of the embedded Si-NCs and their charge trapping properties, different electrical characterization techniques could be applied. The most common are current-voltage (I-V) and capacitance-voltage (C-V) techniques. The I-V measurements have been widely used in order to investigate the mechanism of conductivity of the embedded Si-NCs. The direct tunneling (DT), trap-assisted tunneling (TAT), Fowler-Nordheim tunneling (FN), Poole-Frenkel (PF) conduction or space charged limited current (SCLC) are mostly applied for describing the charge transport properties [36]. Transport properties are affected by the NCs size and space distribution. Zhou et al. [37] have studied the influence of the Si-NC’s diameter on charge transport, and explained the influence by the percolation-hopping conduction mechanism. Figure 2 shows a typical I-V measurement at RT for the embedded Si NCs. NCs are formed by the Si+ ion implantation in the SiO2 layer grown on the Si substrate and the subsequent annealing at 900 C. Metal-oxide-semiconductor (MOS) structures are prepared by thermal evaporation of gold through the masks. Moreover, C-V gives valuable information as far as interface-defects and oxide defects are concerned. There are numerous studies on the charge trapping properties of embedded NCs. However, it should be noted that in a significant number of those reports, effects of defects (either interface-related or in the oxide) have been completely neglected. As some studies indicate [1, 26] these issues should be properly considered. Figure 2 A typical I-V measurement performed on the MOS structure, with embedded Si NCs in SiO2, at RT. NCs are produced by ion implantation and subsequent annealing. To obtain even more information about defects in embedded NCs and at their interfaces, deep level transient spectroscopy (DLTS) can be applied. DLTS is a well-established technique which is commonly used in studying trap states in the bulk semiconductors [38], and has also been successfully applied in studying traps at the Si-SiO2 interfaces [39] and within NCs [40, 41]. Accordingly, electrons/holes can be thermally emitted out from the NCs and then be detected by DLTS only when their electronic states are lifted above/below the bulk Fermi level. Another open and still unresolved problem is the electrical transport across doped NC films. Here significant progress has been made in free-standing Si-NC films [22], but much more effort is needed, for instance by using different electrical characterization techniques, to understand the electrical properties of doped and embedded NCs. ## 3 Theoretical Modeling of Nanocrystals Effective mass models and more elaborate k⋅p-theory were widely employed to understand a several phenomena, including quantum confinement [42], dispersion, as well as strain and electric field dependence of the electronic levels of nanocrystals and quantum dots [43]. Despite being helpful towards grasping of trends found by experiments, these techniques lack atomic resolution and overlook many interesting effects. More recently, significant understanding of the relationships between the atomic structure, chemistry and electronic structure have been obtained from first-principles calculations based on DFT. In analogy to nanostructures grown in a liquid solution or within a solid matrix, nanocrystal models are usually divided into free-standing and embedded. The first class of models mimics the NCs grown, for example, by solidification from plasma or liquid phases, while the second class comprises embedded structures, for example Si- or Ge-NCs in a SiO2 amorphous matrix. Free-standing nanocrystals in vacuum can be modeled using open boundary conditions i.e. requiring the wavefunction to vanish far from the nanocrystal. An alternative approach is to impose periodic boundary conditions (“particle-in-a-box” approach). This has the advantage of allowing for expansion of the charge density in plane-waves and the use of numerical approaches developed for crystalline solids. However, care has to be taken to ensure that there is little interaction between periodic images of the system. This is particularly relevant when treating systems with a finite electric charge or dipole [44]. Embedded nanocrystals are best modeled using periodic boundary conditions. In that case, one of the main difficulties consists of reproducing the correct structure of the interface and oxidation numbers [45]. The gap between such idealized models, which provide insight into quantum effects, and their respective real-life systems is difficult to bridge. In this respect, there have been some attempts at building multi-scale modeling frameworks [46]. Still, there is ample room for improvement of the description of growth, interaction with solvents, and other multi-scale phenomena. ### 3.1 The Many-body Problem In the absence of external fields, the Schrödinger equation for a non-relativistic and stationary problem involving a set of N electrons and M atomic nuclei can be written as $H^Ψ(R)=EΨ(R), (1)$ with R representing all electronic and nuclear degrees of freedom (we drop electronic spins for the sake of simplicity). The Hamiltonian in Eq. 1 contains the usual kinetic and potential terms, $H^=−12∑i=1N∇i2−∑α=1M12mα∇α2+12∑i≠jN1| ri−rj |−∑i=1,α=1N,MZα| ri−Rα |+12∑α≠βM,MZαZβ| Rα−Rβ |, (2)$ with ri and Ri representing electronic and nuclear coordinates, respectively,whereas mα and Zα stand for the mass and atomic number of each nucleus,respectively. Disregarding any analytical solution for the above equation, (only known for problems such as the hydrogen and He+ atoms [47]), the fact that Ψ depends on at least 3M + 3∑ αZα Cartesian coordinates makes the simplest of the problems intractable, even when the fastest supercomputers are put at our disposal. The greatest challenge associated with modeling NCs is the great number of atoms required for the model to meet the sizes of even the smallest particles realized experimentally (about 1000 atoms for a 3 nm diameter NC). Among the several terms in the many-body Hamiltonian, the electron-electron interaction is the hardest do obtain as it scales with N4. This is where DFT comes into play. As opposed to the Schrödinger approach, the Hamiltonian is replaced by a total energy functional E[n] and }Ψ by the electron density n(r), with vext representing an external potential to which the electrons are subjected (see for example Ref. 48 for a review on this method). This includes electron-ion interactions and others, such as applied electrical and magnetic fields. The functional F[n] is universal (system-independent), and accounts for the electronic kinetic energy, as well as electronic exchange-correlation interactions [49]. The striking feature of DFT, is that despite the huge simplification of adopting the electron density as the variational variable, no approximations are made. The drawback is that DFT is formally valid for the ground state only, and the exact form of F[n] is unknown. Despite that, several approximations for F[n] have been proposed, with increasing degree of complexity as they improve in the description of the non-local properties of the electron-electron interactions. Various DFT implementations using localized basis sets e.g. AIMPRO [17, 50], Conquest [51], Onetep [52], OpenMX [53] and SIESTA [54] exhibit order-N scaling [55] and are advertised as enabling calculations with up to N∼104 atoms. Larger systems have been treated using tight binding or semi-empirical methods [56]. Further, atomic-like basis sets, such as Gaussian-type orbitals, are convenient in the case of free-standing nanocrystals, both because they can be naturally combined with open boundary conditions and simultaneously they lead to sparse Hamiltonian and overlap matrices that can be efficiently diagonalized. Notwithstanding, many implementations of density functional theory traditionally used in solid state physics rely on the use of plane-wave basis sets for expansion of wavefunctions and charge density. Although more robust than local-basis implementations, plane-wave codes have the disadvantage that to make the basis size finite it is then necessary to impose periodic boundary conditions, allowing for sufficiently large vacuum spaces in between a nanoparticle and its image. The large supercell size reflects then into a great number of plane waves, which is independent on the ratio between the volumes of matter and vacuum. ### 3.2 Calculation of Optical Properties The indirect band-gap nature of bulk Si has been one of the main handicaps of this material. It has placed Si away from many optical applications like lasers and LEDs, in favor of the more expensive and less environmental friendly III-V semiconductors. While radiative recombination on compound semiconductors is a relatively efficient process, in Si such transitions are rather unlikely to take place as the large k-space mismatch between conduction band minimum and valence band maximum states implies the coupling with phonons. On the other hand, the dispersionless and tunable nature of the electronic structure of Si-NCs holds many promises in all-Si optoelectronics. In this respect theoretical modeling has provided many insights. Besides the size and shape effect to the energy and rate of optical transitions, the chemical nature of the surface, shell or host where the NC is embedded play a critical role [57]. For instance, Guerra and Ossicini [58] showed that while radiative recombination of H-saturated Si NC is strongly dependent on the size of the crystallites, in hydroxyl-terminated or SiO2-embedded NCs the optical yield is mostly conditioned by the fraction of oxygen termination. First-principles DFT modeling has also been insightful on the study of local polarizations that take place at Si-NC/SiO2 interfaces [59]. The abrupt change of chemical species (with different electronegativities) at the edge of the NCs induces charge displacements that can be accounted for by using pseudopotentials. It has been found that polarizations due to the oxide interface have two important effects, namely (i) to quench the low energy absorption region and (ii) a blue-shift of some particularly intense transitions. Another important aspect is the role of defects. Si dangling bonds or radicals are strongly localized being effective traps for both electrons and holes [21]. They are therefore likely to degrade the optical yield. On the other hand, shallower states like those produced at the Si/SiO2 core-shell interface of oxidized Si-NCs are most likely to shift the absorption/emission spectra with respect to pristine NCs [60]. Inclusion of many-body effects is important especially for small nanoparticles where the exciton binding energy can be large [61]. These can be calculated using the Bethe-Salpeter equation [62]. However, for nanocrystals with radius larger than about 0.6 nm, the self-energy and Coulomb corrections almost exactly cancel, and one-particle calculations actually give accurate values for the excitonic gap [62]. ### 3.3 Modeling Dopants in Nanocrystals Deliberate introduction of alien species into materials lies at the heart of microelectronics. A prototypical example is the replacement of a few lattice sites in a billion in crystalline Si, for instance by phosphorous or boron, to confer good electrical conductivity to an otherwise poor insulator. In the same way, doping NCs will play an analogous role in future artificial solids or meta-materials made of wave-function engineered nanoparticles. Although many promising applications of Si-NCs rely on the possibility to tune their electronic states by exploring size and surface effects, the fact is that this is only possible in ultra-small NCs where effective electrical doping (which should lead to considerable fraction of ionized dopants at room-temperature) is yet to be demonstrated. Notwithstanding, the introduction of dopants in Si-NCs has been unequivocally demonstrated, for instance by monitoring the 31P hyperfine splitting of the phosphorous donor state during electron paramagnetic resonance experiments [63], or from photoluminescent transitions of bound excitons to boron [64]. In small NCs, where surface conditions affect the electronic states, theory predicts that phosphorous and boron levels are rather deep with carrier binding energies of the order of 1 eV, anticipating serious difficulties in finding suitable dopants to operate at room temperature [21, 65&$x02013;67].

Figure 3 Hybridization between F4-TCNQ and Si-NC one-electron states. (a)–(d) Kohn-Sham eigenvalue energy diagrams and (e) Isosurface plot of the F4-TCNQ lowest unoccupied state (b2g symmetry). The energy-level diagrams are for (a) isolated F4-TCNQ and (b)–(d) for F4-TCNQ adsorbed on Si NCs of increasing size. Each state is represented by a bar of unitary length, with the abscissa of the left- and right-hand ends of the bar indicating, respectively, the relative localization on the molecule (negative values) and on the NC (positive values). Blue and red bars stand for occupied and unoccupied states, respectively. (Reprinted with permission from Carvalho et al. [20], 2011 the American Physical Society).

In this respect other routes for doping have been under investigation, where transfer doping by means of molecules with high electron affinity or low ionization potential stands as a rather promising alternative. For instance, In Ref. 20 it is suggested that the F4-TCNQ (7,7,8,8-tetracyano-2,3,5,6-tetrafluoroquinodimethane) molecule, which is commonly used as a p-dopant in organic electronics, could be a candidate to produce holes in the Si-NCs, as shown in Figure 4. They also showed that about 3–4 molecules adsorbed to the NC surface are able to produce a positively charged NC, although the first excitation of the doped system was almost 1 eV, again indicating that free-holes are unlikely to be produced at room temperature. These results were confirmed recently by means of electrical measurements combined with first-principles calculations [22], demonstrating that F4-TCNQ within a Si-NC solid film is not a shallow acceptor, but rather a deep acceptor with levels that can edge the conduction band minimum of the Si-NC film. In fact, this dopant was used to increase the conductivity of the films by more than 2 orders of magnitude, although the majority carriers were electrons.

Figure 4 (a) Three-dimensional view of an fcc-superlattice of Si-NCs (large solid spheres) doped with F4-TCNQ molecules (blue). (b) Electron density isosurface (red) of the HOMO level overlapping both the F4-TCNQ molecule and an adjacent Si-NC. Circles enclosing individual NCs are drawn for eye guidance purposes. (Reprinted with permission from Ref. [22]. 2014 American Chemical Society).

### 3.4 Surface Properties

The NC surface is one of the most important variables in the engineering of its shape, intrinsic properties and stability in air and interaction with solvents and solid matrices.

For nanocrystals with a clean surface or with a hydrogen-covered surface, the orientation dependence of the surface energy, as well as edge and corner energies (for less than about 100 atoms) determine the shape of the NCs grown under near-equilibrium quasi-static conditions. It has been found that diamond NCs are most stable in a truncated octahedral structure, but Si- and Ge-NCs are stable in a nearly-spherical geometry [68]. In any case, free standing Si and Ge-NCs are most often grown in conditions very far from equilibrium, justifying the use of spherical models [69]. Diamond nanocrystals however have been grown in different shapes and configurations, and their optical properties have been found to be in discrepancy with theoretical models, presumably due to the contribution of defects [70].

As nanocrystals have a very large surface-to-volume ratio, their electronic and optical properties are largely determined by the surface or interface morphology. Amongst group-IV NCs, Si-NCs are especially reactive in air, immediately forming an oxide cap. Surface oxidation also decreases the gap energy of the NC, red-shifting its absorption and photoluminescence edges [71, 72]. Models of Si-NCs embedded in SiO2 also show optical red-shifting following oxidation, and suggest that this effect is associated not only with the decreased quantum confinement, but also with the presence of silanonelike Si=O bonds [73]. As a consequence of the change in the electronic structure and dielectric screening, the ionization energy of dopants is also altered. The earliest oxidation stage corresponding to the formation of silanol surface groups was found to increase the electron binding energy of the P, As and Sb, and decrease the hole binding energy of B, Al, Ga and In [74].

Chlorine covered Si-NCs were found to have higher electron affinity, higher ionization energy and lower optical absorption energy threshold than hydrogen covered nanocrystals with the same size [75]. Like the hydrogenated Si-NCs, chlorinated Si-NCs doped with phosphorus or boron require a high activation energy to transfer an electron or hole, respectively, to undoped Si-NCs. The electronic levels of surface dangling bonds are similar for both types of surface passivation, although in the chlorinated Si-NCs some fall off the narrower gap. Functionalization with chlorine, nitrogen and fluorine was also found to be an effective way to control the bandgap of nanodiamonds [76].

Nanocrystals functionalized with organic groups have so far only been considered in a limited number of theoretical studies, for silicon [55, 77&\$x02013;79] and diamond [80]. Functionalization with alkyl and aryl molecules is an important preparatory step for the conjugation of the surface to larger organic molecules. Regarding the direct influence on the physical properties, alkyl passivation was found to change little the optical gaps of silicon QDs, but to decrease substantially their ionization potentials and electron affinities and affects their excited state properties. Nevertheless, there is still ample space for the modeling of the interaction of functionalized nanocrystals with solvents, polymers and biological molecules. A tight-binding parameterization has been proposed for this family of systems, offering a cheaper approach that may become a basis for a function-oriented treatment of organic-inorganic interfaces [54].

## 4 Conclusions

Although group-IV NCs may emerge as a natural way to extend, enhance and control the properties of their respective bulk materials, the last two decades of research have shown that not only the device architecture, but also the growth, characterization and modeling techniques have to be redesigned to meet their very specific requirements.

Silicon and germanium NCs have revealed to be promising on the areas of optical luminescence and absorption, where size-dependent optical transitions have been consistently reported. This property is particularly appealing from photovoltaics and light emitting devices. Memory devices are another promising area of application. So far, the greatest challenges continue to be the control of surface, interface and other deep levels, misfit strain, and doping efficiency.

From a theoretical point of view, even though one of the most important attributes of nanoparticles – their size-dependent bandgap – is a quantity hard to predict, modeling studies have been able to provide great insight into the fundamental optical and electronic properties of different types of NCs. An open issue still resides on the difficult task of bridging the length scales – from the largest sizes achievable numerically to the smallest sizes produced experimentally.

## Acknowledgments

The authors would like to acknowledge the contribution of the COST Action MP1406 MultiscaleSolar. JC thanks support by the FCT through Projects No. PTDC/CTM- ENE/1973/2012 and UID/CTM/50025/2013. IC thanks support by the Croatian Centre of Excellence for Advanced Materials and Sensing Devices.

## References

[1] El Hdiy A., Gacem, K., Troyon, M., Ronda, A., Bassani, F., and Berbezier, I. (2008). J. Appl. Phys. 104, 063716.

[2] Nozik, A. J. (2002). Physica E. 14, 115.

[3] Gur, I., Fromer, N. A., Geier, M. L., and Alivisatos, A. P. (2005). Science 310, 462.

[4] Ray, S. K., Maikap, S., Banarjee, W., and Das, S. (2013). J. Phys. D: Appl. Phys. 46, 153001.

[5] Wang, L., and Zunger, A. (1994). J. Phys. Chem. 98, 2158.

[6] Öğüt S., Chelikowsky, J. R., and Louie, S. G. (1997). Phys. Rev. Lett. 79, 1770.

[7] Delerue, C., Lannoo, M., Allan, G. (2000). Phys. Rev. Lett. 84, 2457.

[8] Furukawa, S., and Miyasato, T. (1988). Phys. Rev. B 38, 5726.

[9] Timmerman, D., and Gergorkiewicz, T. (2012). Nano. Res. Lett. 7, 389.

[10] Belyakov, V., Burdov, V. A., Lockwood, R., and Meldrum, A. (2008). Adv. Opt. Technol. 2008, 279502.

[11] Franceschetti, A., and Zunger, A. (2000). Phys. Rev. B 62, 2614.

[12] Wang, L., and Zunger, A. (1994). Phys. Rev. Lett. 73, 1039.

[13] Giustino, F., and Pasquarello, A. (2005). Phys. Rev. B 71, 144104.

[14] Delerue, C., Lannoo, M., and Allan, G. (2003). Phys. Rev. B 68, 115411.

[15] Öğüt S., Burdick, R., Saad, Y., and Chelikowsky, J. R. (2003). Phys. Rev. Lett. 90, 127401.

[16] Trani, F., Ninno, D., Cantele, G., Iadonisi, G., Hameeuw, K., Degoli, E., et al. (2006). Phys. Rev. B 73, 245430.

[17] Rayson, M. J., and Briddon, P. R. (2009). Phys. Rev. B 80, 205104.

[18] Ramos, L. E., Degoli, E., Cantele, G., Ossicini, S., Ninno, D., Furthmüller, J., et al. (2008). Phys. Rev. B 78, 253310.

[19] Chan, T. L., Tiago, M. L., Kaxiras, E., and Chelikowsky, J. L. (2008). Nano Letters 8, 596.

[20] Carvalho, A., Coutinho, J., Barroso, M., Silva, E. L., Öberg S., Rayson, M. J., et al. (2011). Phys. Rev. B 84, 125437.

[21] Carvalho, A., Öberg S., Rayson, M. J., and Briddon, P. R. (2012). Phys. Rev. B 86, 045308.

[22] Pereira, R. N., Coutinho, J., Niesar, S., Oliveira, T. A., Aigner, W., Wiggers, H., et al. (2014). Nano Letters 14, 3817.

[23] Zacharias, M., Heitmann, J., Scholz, R., Kahler, U., Schmidt, M., and Blasing, J. (2002). Appl. Phys. Lett. 80, 661.

[24] Barbagiovanni, E. G., Lockwood, D. J., Simpson, P. J., and Gonncharova, V. (2014). Appl. Phys. Rev. 1, 011302.

[25] Schroder, D. K. (2006). ‘Semiconductor Material and Device Characterization’, (Wiley, New Jersey)

[26] Martin-Sanchez, J., Capan, I., Chahboun, A., Pinto, S. R. C., Vieira, E. M. F., Rolo, A. G., et al. (2013). Appl. Surf. Sci. 280, 632.

[27] Shah, M., Wojdak, M., Kenyon, A. J., Halsall, M. P., Li, H., and Crowe, I. F. (2012). J. Lumin. 132, 3103.

[28] Murakami, K., Shirakawa, R., Tsujimura, M., Uchida, N., Fukata, N., and Hishita, S. (2009). J. Appl. Phys. 105, 054307.

[29] Mimura, A., Fujii, M., Hayashi, S., Kovalev, D., and Koch, F. (2000). Phys. Rev. B 62, 12625.

[30] Chen, Q., Lu, T., Xu, M., Meng, C., Hu, Y., Sun, K., et al. (2011). Appl. Phys. Lett. 98, 073103.

[31] Kovacevic, I., Pivac, B., Dubcek, P., Zorc, H., Radic, N., Bernstorff, S., et al. (2007). Appl. Surf. Sci. 253, 3034.

[32] Bernstorff, S., Dubcek, P., Kovacevic, I., Radic, N., and Pivac, B. (2007). Thin Solid Films 515, 5637.

[33] Pivac, B., Dubcek, P., Capan, I., Zulim, I., Betti, T., Zorc, H., et al. (2009). Nanosci. Nanotech. 9, 3853.

[34] Kovacević, I., Dubcek, P., Duguay, S., Zorc, H., Radić, N., Pivac, B., et al. (2007). Physica E 38, 50.

[35] Crowe, I., Papachristodoulou, N., Halsall, M. P., Hylton, N. P., Hulko, O., Knights, A. P., et al. (2013). Appl. Phys. 113, 024304.

[36] Jambois, O., Berencen, Y., Hijazi, K., Wojdak, M., Kenyon, A. J., Gourbilleau, F. et al. (2009). J. Appl. Phys. 106, 063526.

[37] Zhou, X., Usami, K., Rafiq, M. A., Tsuchiya, Y., Mizuta, H., and Oda, S. (2008). J. Appl. Phys. 104, 024518.

[38] Dobaczewski, L., Peaker, A. R., and Bonde Nielsen, K. (2004). J. Appl. Phys. 96, 4689.

[39] Capan, I., Janicki, V., Jacimovic, R., and Pivac, B. (2012). Nuclear Instrum. Meth. Phys. Res. B 282, 59.

[40] Antonova, I. V., Popov, V. I., Smagulova, S. A., Jedrzejewski, J., and Balberg, I. (2013). J. Appl. Phys. 113, 084308.

[41] Buljan, M., Grenzer, J., Holy, V., Radic, N., T. Misic-Radic, Levichev, S., et al. (2010). Appl. Phys. Lett. 97, 163117.

[42] Bimberg, D., Grundmann, M., and Ledentsov, N. N. (1999). Quantum Dot Hetero-structures. Chichester: John Wiley and Sons.

[43] Chang, K., and Xia, J.-B. (1998). J. Appl. Phys. 84, 1454.

[44] Makov, G., and Payne, M. C. (1995). Phys. Rev. B 51, 4014.

[45] Pasquarello, A., Hybertsen, M. S., and Car, R. (1998). Nature 396, 58.

[46] Zahi, I., Mur, P., Blaise, P. H., Estève, A., Djafari Rouhani, M., Vergnes, H., et al. (2011). Thin Solid Films 519, 7650.

[47] J-REF1. Schiff, L. I. (1955). Quantum Mechanics. Singapore: McGraw-Hill.

[48] Jones, R. O., and Gunnarsson, O. (1989). Rev. Mod. Phys. 61, 689.

[49] Hohenberg, P., and Kohn, W. (1964). Phys. Rev. 136, B864.

[50] Rayson, M. J. (2010). Comput. Phys. Commun. 181, 1051.

[51] Bowler, D. R., Miyazaki, T., and Gillan, M. J. (2002). J. Phys. Condens. Matter. 14, 2781.

[52] Skylaris, S.-K., Haynes, P. D., Mostofi, A., and Payne, M. C. (2005). J. Chem. Phys. 122, 084119.

[53] OpenMX code. Available at: http://www.openmx-square.org

[54] Soler, J. M., Artacho, E., Gale, J. D., Garcia, A., Junquera, J., Ordejon, P., et al. (2002). J. Phys. Condens. Matter. 14, 2745.

[55] Kohn, W. (1996). Phys. Rev. Lett. 76, 3168.

[56] Trani, F., and Baroni, V. J. (2011). Chem. Theor. Comput. 7, 713.

[57] Puzder, A., Williamson, A. J., Grossman, J. C., and Galli, G. (2002). J. Chem. Phys. 117, 6721.

[58] Guerra, R., and Ossicini, S. (2010). Phys. Rev. B 81, 245307.

[59] Guerra, R., Marsili, M., and Ossicini, S. (2011). Phys. Rev. B 84, 075342.

[60] Koponen, L., Tunturivuori, L. O., Puska, M. J., and Nieminen, R. M. (2009). Phys. Rev. B 79, 235332.

[61] Rajadell, F., Climente, J. I., Planelles, J., and Bertoni, A. (2009). J. Phys. Chem. C 113, 11268.

[62] Delerue, C., Lannoo, M., and Allan, G. (2000). Phys. Rev. Lett. 84, 2457.

[63] Stegner, A. R., Pereira, R. N., Klein, K., Lechner, R., Dietmueller, R., Brandt, M. S., et al. (2008). Phys. Rev. Lett. 100, 026803.

[64] Fujii, M., Hayashi, S., and Yamamoto, K. (1998). J. Appl. Phys. 83, 7953.

[65] Melnikov, D. V., and Chelikowsky, J. R. (2004). Phys. Rev. Lett. 92, 046802.

[66] Cantele, G., Degoli, E., Luppi, E., Magri, R., Ninno, D., Iadonisi, G., et al. (2005). Phys. Rev. B 78, 113303.

[67] Ni, Z., Pi, X., and Yang, D. (2014). Phys. Rev. B 89, 035312.

[68] Barnard, A. S., and Zapol, P. (2004). J. Chem. Phys. 121, 4276.

[69] Mangolini, L., and Kortshagen, U. (2010). Silicon Nanocrystals; Fundamentals, Synthesis, and Applications, eds L. Pavesi and R. Turan (Weinheim: Wiley-VCH).

[70] Landt, L., Klünder, K., Dahl, J. E., Carlson, R. M. K., Möller, T., and Bostedt, C. (2009). Phys. Rev. Lett. 103, 047402.

[71] Vasiliev, I., Chelikowsky, J. R., and Martin, R. M. (2002). Phys. Rev. B 65, 121302(R).

[72] Zhou, Z., Friesner, R. A., and Brus, L. (2003). J. Am. Chem. Soc. 125, 15599.

[73] Luppi, M., and Ossicini, S. (2005). Phys. Rev. B 71, 035340.

[74] Carvalho, A., Rayson, M. J., and Briddon, P. R. (2012). J. Phys. Chem. C 116, 8243.

[75] Carvalho, A., Öberg, S., Rayson, M. J., and Briddon, P. R. (2012). Phys. Rev. B 86, 045308.

[76] Brown, N., and Hod, O. (2014). J. Phys. Chem. C 118, 5530.

[77] Reboredo, F. A., Schwegler, E., and Galli, G. (2003). J. Am. Chem. Soc. 125, 15243.

[78] Reboredo, F. A., and Galli, G. (2005). J. Phys. Chem. B 109, 1072.

[79] Zhou, Z., Brus, L., and Friesner, R. (2003). Nano Lett. 3, 163.

[80] Zhong, Y. L., Loh, K. P., Midya, A., Chen, Z.-K., and Suzuki, M. (2008). Chem. Mater. 20, 3137.

## Biographies

I. Capan was born on 16th of Feb. 1977, Tuzla, Bosnia and Hercegovina. She has obtained her Ph.D. in physics at University of Zagreb, Croatia in 2006. She works at Rudjer Boskovic Institute, Croatia, and currently holds a position of a senior research associate. She was awarded by Chancellor’s Award for the Best Student Scientific Work at University of Zagreb in 1999 and National Science Award for Junior Researchers in 2006. Her research is mainly focused on the optoelectronic characterization of semiconductors (from the bulk to the low dimensional structures) and hybrid materials with particular interest in the developing the new generation of devices, from non-volatile memories to solar cells. She has published 50 research papers.

A. Carvalho received her first degree at the University of Aveiro, Portugal, in 2005. This was followed by a Ph.D. at the University of Exeter, UK (2005–2008), where she investigated defects in semiconductors, and an incursion at the physics of ferroelectrics as a post-doctoral researcher at the EPFL, Switzerland. She was awarded a Marie-Curie fellowship at the University of Aveiro, from 2011 to 2012. At present, Alexandra is a Senior Research Fellow at the National University of Singapore.

J. Coutinho is a Principal Researcher at the University of Aveiro in Portugal. He did a Ph.D. in Physics at the University of Exeter (UK), and since then he has been involved in several funded projects, many of them in collaboration with experimentalists. His research is mostly theoretical, and involves looking at the fundamental properties of defects in solids, surfaces and nanostructures of semiconducting and insulating materials by means of electronic structure calculations (density functional theoretical methods) and first principles molecular dynamics. He has (co-)authored over 100 papers in peer-review journals (ISI).

format: plain


text: The susceptibility of a body to the acquisition of a magnetic moment when exposed to a magnetic field, H a, is its magnetic susceptibility, χ Ξ M/H a, where M is its magnetization. a magnetic field that varies sinusoidally), this is called AC susceptibility. R. Zimmerman, and M. R. Foster Magnetic susceptibility (simplified as susceptibility hereinafter) is an important physical property of materials for many physical, chemical, and engineering applications. 2004; Zhu et al. Furthermore, in this topic, you will learn about the magnetic field, magnetic field formula, its derivation, and solved examples. We used both raw materials and heated samples. When the coercivity of the material parallel to an applied field is the smaller of the two, the differential susceptibility is a function of the applied field and self interactions, such as the magnetic anisotropy. The proportional constant links magnetization to the applied magnetic field intensity (at levels below which saturation and hysteresis are important). Effort should be made to trace the data in such tables to the original sources, and to double-check the proper usage of units. Given: Magnetic field = B = 1.8 T, magnetic intensity = H = 1000 A/m, μ o = 4π x 10-7 Wb/Am. Generally, non-magnetic materials are said to be para- or diamagnetic because they do not possess permanent magnetization without external magnetic field. Magnetic Field Due to Current-Carrying Coil: The magnetic induction at a point on the axis at a distance of ‘x’ from the centre of a circular coil of radius ‘a’ is given by. The most common is to use the inferior hemisphere and to plot the data of K max,Kint and K min with different symbols, so it is Figure 1. A related term is magnetizability, the proportion between magnetic moment … From the classical description of magnetism, Lenz's law can be stated as: =1+4 (23) where B/H is called the magnetic permeability of the material and K is the magnetic susceptibility per unit volume (I/H). where χijd{\displaystyle \chi _{ij}^{d}} is a tensor derived from partial derivatives of components of M with respect to components of H. Magnetic susceptibility is a measure of the ability of a material to be magnetized. Magnetic susceptibility is dimensionless in the SI unit system (Cano, Cordova-Fraga, Sosa, Bernal-Alvarado, & Baffa, 2008; Collinson, 2013 1999). This is a dimensionless quantity. |CitationClass=journal These results are sensitive to the domain wall configuration of the material and eddy currents. Their SI unit is Henry per meter (H/M or Hm 2) or newton per ampere square (N-A 2).. It is denoted by χ. This tube is U shaped and has two limbs, one with very narrow width compared to the other. Volume magnetic susceptibility is measured by the force change felt upon a substance when a magnetic field gradient is applied. 19:23. the magnetic susceptibility of a substance. We all have seen magnets and are very fond of playing with them. The new Magnetic Susceptibility Balance - AUTO is a microprocessor controlled, state of the art balance for detecting the magnetic properties of gases, liquids and solids. curie law modified curie law variation of magnetic susceptibility with temperature - duration: 11:06. a plus julana - apj 13,519 views. It is expressed by the formula shown below. Related formulas Relation between relative permeability and magnetic susceptibility. susceptibility axes is through a stereographic net. [5] For liquid samples, the susceptibility can be measured from the dependence of the NMR frequency of the sample on its shape or orientation. | author=J. }}, {{#invoke:citation/CS1|citation Magnetic susceptibility, k, is related to magnetic permeability (m) by: The tensor is thus rank 2, dimension (3,3) describing the component of magnetization in the i-th direction from the external field a… \$(window).on('load', function() { Magnetic susceptibility $$\chi _{m}$$ = $$K_{m}$$ – 1. The molar susceptibility is the mass susceptibility multiplied by the formula weight. This change is converted into a magnetic susceptibility reading. 2000, 2001; Hrouda 2003; Hrouda et al. B = B1 + BH = μ0I + μ0H. Alle Stoffe reagieren zu einem gewissen Grad auf magnetische Felder. [6][7][8][9][10], The magnetic susceptibility of most crystals is not a scalar quantity. We offer a range of magnetic susceptibility instruments for laboratory and field use. magnetic susceptibility in experiments of up to 2 kbar [e.g., 76]. window.jQuery || document.write('


text:
# Question 26 10 pts What characteristics of the labour market make it distinctive from other markets,...

###### Question:

Question 26 10 pts What characteristics of the labour market make it distinctive from other markets, justifying a special sub-discipline of economics? What are the major implications of the neoclassical model of labour supply and demand? How realistic is this model? (5+3+2 = 10 points) Upload Choose a File

#### Similar Solved Questions

##### Use these data and test to see whether the mean number of parts produced is the same with each method , UseState the null and alternative hypotheses_ Ha; Not all the population means are equal: Ha' Va = KBHo' At least two of the population means are equal: Ha: At least two of the population means are different;Ho: PA  PB Pc Ha: VA = KBHa: HLA = PB = Ec Ha' /A  P8Ha; PA = Pp = Ec Not all the population means are equal:Find the value of the test statistic. (Round your answer to tw
Use these data and test to see whether the mean number of parts produced is the same with each method , Use State the null and alternative hypotheses_ Ha; Not all the population means are equal: Ha' Va = KB Ho' At least two of the population means are equal: Ha: At least two of the populat...
##### How do you integrate int (sinx)(5^x) using integration by parts?
How do you integrate int (sinx)(5^x) using integration by parts?...


text:
## Chapter Chosen

Mechanical Properties of Solids

## Book Store

Currently only available for.
CBSE Gujarat Board Haryana Board

## Previous Year Papers

Download the PDF Question Papers Free for off line practice and view the Solutions online.
Currently only available for.
Class 10 Class 12
Two wires P and Q of same length and material but radii in the ratio 2:1 are suspended from a rigid support. Find the ratio of strain produced in the wires when: (i) both are under same stress (ii) both are loaded by same weight.

Given the radii of two wires is of the ratio 2:1.
Using the formula as per Hooke's law,

i) When both the wires are under the same stress, strain produced will be the same.

ii) When both the wires are loaded by the same weight, then

$\frac{Strai{n}_{p}}{Strai{n}_{Q}}=\frac{\left({r}_{Q}{\right)}^{2}}{\left({r}_{P}{\right)}^{2}}=\frac{1}{4}$

269 Views

Define interatomic forces and give an example?

The force between atoms of the molecule is called interatomic force.

E.g.The nucleus and electron cloud of a molecule is binded by electrostatic force.
1032 Views

What is the force of cohesion?

Cohesive attraction or cohesive force is the force of attraction between same types of molecules sticking together.
651 Views

What is the nature of inter-atomic or inter-molecular forces?

Inter-atomic or inter-molecular forces are electrostatic in nature.

637 Views

What do you understand by intermolecular forces?

Intermolecular force is the force between the molecules of the substance is called intermolecular force.

There is a dipole-dipole interaction between the molecules.
630 Views

What is the force of adhesion?

Adhesive force is the attractive force between two unlike molecules. They are caused by forces acting between two substances like electrostatic force (attraction due to opposing charges), mechanical force etc.

E.g., Force of attraction between gum and paper.

587 Views


text:
1. ## Equation Help

Hey guys first post here I'm a j2me developer using some maths for my weather application.

I'm trying to calculate the time of sunrise using this equation:

cos(ωo) = -tan(φ)×tan(δ)

this can be found at [link] Sunrise equation - Wikipedia, the free encyclopedia [/link] aswell as some other places

I know once I have ωo I can find the sunrise however, I dont understand the cos(ωo) bit. I just want the equation in the form

ωo = . . . .

any ideas how I factor out the cos()? I did try and do some inv cos functions but to no avail, any help much appreciated.

2. Originally Posted by blundell
Hey guys first post here I'm a j2me developer using some maths for my weather application.

I'm trying to calculate the time of sunrise using this equation:

cos(ωo) = -tan(φ)×tan(δ)

this can be found at [link] Sunrise equation - Wikipedia, the free encyclopedia [/link] aswell as some other places

I know once I have ωo I can find the sunrise however, I dont understand the cos(ωo) bit. I just want the equation in the form

ωo = . . . .

any ideas how I factor out the cos()? I did try and do some inv cos functions but to no avail, any help much appreciated.
If you have $\displaystyle \cos x = a$ (and $\displaystyle |a|\leq 1$) then it means $\displaystyle x = \cos^{-1} a$ is one such solution. And all solutions are given by $\displaystyle \pm \cos^{-1} a + 2\pi n$.


text:
# ignite.contrib.metrics#

## Contrib module metrics#

 AveragePrecision Computes Average Precision accumulating predictions and the ground-truth during an epoch and applying sklearn.metrics.average_precision_score . CohenKappa Compute different types of Cohen's Kappa: Non-Wieghted, Linear, Quadratic. GpuInfo Provides GPU information: a) used memory percentage, b) gpu utilization percentage values as Metric on each iterations. PrecisionRecallCurve Compute precision-recall pairs for different probability thresholds for binary classification task by accumulating predictions and the ground-truth during an epoch and applying sklearn.metrics.precision_recall_curve . ROC_AUC Computes Area Under the Receiver Operating Characteristic Curve (ROC AUC) accumulating predictions and the ground-truth during an epoch and applying sklearn.metrics.roc_auc_score . RocCurve Compute Receiver operating characteristic (ROC) for binary classification task by accumulating predictions and the ground-truth during an epoch and applying sklearn.metrics.roc_curve .

## Regression metrics#

Module ignite.contrib.metrics.regression provides implementations of metrics useful for regression tasks. Definitions of metrics are based on Botchkarev 2018, page 30 “Appendix 2. Metrics mathematical definitions”.

Complete list of metrics:

 CanberraMetric Calculates the Canberra Metric. FractionalAbsoluteError Calculates the Fractional Absolute Error. FractionalBias Calculates the Fractional Bias. GeometricMeanAbsoluteError Calculates the Geometric Mean Absolute Error. GeometricMeanRelativeAbsoluteError Calculates the Geometric Mean Relative Absolute Error. ManhattanDistance Calculates the Manhattan Distance. MaximumAbsoluteError Calculates the Maximum Absolute Error. MeanAbsoluteRelativeError Calculate Mean Absolute Relative Error. MeanError Calculates the Mean Error. MeanNormalizedBias Calculates the Mean Normalized Bias. MedianAbsoluteError Calculates the Median Absolute Error. MedianAbsolutePercentageError Calculates the Median Absolute Percentage Error. MedianRelativeAbsoluteError Calculates the Median Relative Absolute Error. R2Score Calculates the R-Squared, the coefficient of determination. WaveHedgesDistance Calculates the Wave Hedges Distance.


text:
### Archive

Posts Tagged ‘finite fields’

## Cayley-Hamilton Theorem and Jordan Canonical Form

I was discussing last week with my officemates Hu Fu and Ashwin about the Cayley-Hamilton Theorem. The theorem is the following, given an ${n \times n}$ matrix ${A}$ we can define its characteristic polynomial by ${p_A(\lambda) = \det(A - I\lambda)}$. The Cayley-Hamilton Theorem says that ${p_A(A) = 0}$. The polynomiale is something like:

$\displaystyle p_A(x) = a_k x^k + a_{k-1} x^{k-1} + \hdots + a_1 x^1 + a_0$

so we can just see it as a formal polynomial and think of:

$\displaystyle p_A(A) = a_k A^k + a_{k-1} A^{k-1} + \hdots + a_1 A + a_0 I$

which is an ${n \times n}$ matrix. The theorem says it is the zero matrix. We thought for a while, looked in the Wikipedia, and there there were a few proofs, but not the one-line proof I was looking for. Later, I got this proof that I sent to Hu Fu:

Write the matrix ${A}$ in the basis of its eigenvectors, then we can write ${A = \Gamma^t D \Gamma}$ where ${D}$ is the diagonal matrix with the eigenvalues in the main diagonal.

$\displaystyle A^k = (\Gamma^t D \Gamma) \hdots (\Gamma^t D \Gamma) = \Gamma^t D^k \Gamma$

and since ${D = \text{diag}(\lambda_1, \hdots, \lambda_n)}$ we have ${D^k = \text{diag}(\lambda_1^k, \hdots, \lambda_n^k)}$. Now, it is simple to see that:

$\displaystyle p_A(A) = \Gamma^t p(D) \Gamma$

and therefore:

$\displaystyle p(D) = \begin{bmatrix}& p_A(\lambda_1) & & & \\ & & p_A(\lambda_2) & & & \\ & & & \ddots & \\ & & & & p_A(\lambda_n) \end{bmatrix} = \begin{bmatrix} & 0 & & & \\ & & 0 & & & \\ & & & \ddots & \\ & & & & 0 \end{bmatrix} = 0$

And that was the one-line proof. One even simpler proof is: let ${v_i}$ be the eigenvectors, then ${p_A(A)v_i = p_A(\lambda_i)A = 0}$, so ${p_A(A)}$ must be ${0}$ since it returns zero for all elements of a basis. Well, I sent that to Hu Fu and he told me the proof had a bug. Not really a bug, but I was proving only for symmetric matrices. More generally, I was proving for diagonalizable matrices. He showed me, for example, the matrix:

$\displaystyle \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$

which has only one eigenvalue ${0}$ and the the eigenvectors are all of the form ${(x,0)}$ for ${x \in {\mathbb R}}$. So, the dimension of the space spanned by the eigenvectors is ${1}$, less than the dimension of the matrix. This never happens for symmetric matrices, and I guess after some time as a computer scientist, I got used to work only with symmetric matrices for almost everything I use: metrics, quadratic forms, correlation matrices, … but there is more out there then only symmetric matrices. The good news is that this proof is not hard to fix for the general case.

First, it is easy to prove that for each root of the characteristic polynomial there is one eigenvector associated to it (just see that ${\det(A - \lambda I) = 0}$ and therefore there must be ${v \in \ker(A - \lambda I) \setminus \{ 0 \}}$, so if all the roots are distinct, then there is a basis of eigenvalues, and therefore the matrix is diagonalizable (notice that maybe we will need to use complex eigenvalues, but it is ok). The good thing is that a matrix having two identical eigenvalues is a “coincidence”. We can identify matrices with ${{\mathbb R}^{n^2}}$. The matrices with identical eigenvalues form a zero measure subset of ${{\mathbb R}^{n^2}}$, they are in fact the roots of a polynomial in ${x_{ij}}$. This polynomial is the resultant polynomial ${R_{p,p'} = 0}$. Therefore, we proved Cayley-Hamilton theorem in the complement of a zero-measure set in ${{\mathbb R}^{n^2}}$. Since ${A \mapsto p_A(A)}$ is a continuous function, it extends naturally to all matrices ${A \in {\mathbb R}^{n^2}}$.

We can also interpret that probabilistically: get a matrix ${U}$ where ${U_{ij}}$ is taken uniformly at random from ${[0,1]}$. Then ${A + \epsilon U}$ has with probability ${1}$ all different eigenvalues. So, ${p_{A+\epsilon U} (A+\epsilon U) = 0}$ with probability ${1}$. Now, just make ${\epsilon \rightarrow 0}$.

Ok, this proves the Theorem for real and complex matrices, but what about a matrix defined over a general field where we can’t use those continuity arguments. A way to get around it is by using Jordan Canonical Form, which is a generalization of eigenvector decomposition. Not all matrices have eigenvector decomposition, but all matrices over an algebraic closed field can be written in Jordan Canonical Form. Given any ${A \in \overline{K}^{n^2}}$ there is a matrix ${\Gamma \in \overline{K}^{n^2}}$ so that:

$\displaystyle A = \Gamma^{-1} \begin{bmatrix}& B_1 & & & \\ & & B_2 & & & \\ & & & \ddots & \\ & & & & B_p \end{bmatrix}\Gamma$

where ${B_i}$ are blocks of the form:

$\displaystyle B_i = \begin{bmatrix}& \lambda & 1 & & \\ & & \lambda & 1 & & \\ & & & \ddots & \\ & & & & \lambda \end{bmatrix}$

By the same argument as above, we just need to prove Cayley Hamilton for each block in separate. So we need to prove that ${p_A(B_i) = 0}$. If the block has size ${1}$, then it is exacly the proof above. If the block is bigger, then we need to look at how does ${B_i^k}$ looks like. By inspection:

$\displaystyle B_i^2 = \begin{bmatrix}& \lambda^2 & 2 \lambda & 1 & & & \\ & & \lambda^2 & 2 \lambda & 1 & & & \\ & & & & & \ddots & \\ & & & & & \lambda^2 \end{bmatrix}$

Tipically, for ${B_i^k}$ we have in each row, starting in column ${k}$ the sequence ${\lambda^k, k \lambda^{k-1}, k(k-1) \lambda^{k-1}, \hdots}$, i.e., ${\frac{d^0}{d\lambda^0} \lambda^k, \frac{d^1}{d\lambda^1} \lambda^k , \frac{d^2}{d\lambda^2} \lambda^k \hdots}$. So, we have

$\displaystyle p(B_i) = \begin{bmatrix} p(\lambda) & p'(\lambda) & p''(\lambda) & p'''(\lambda) & \hdots \\ & p(\lambda) & p'(\lambda) & p''(\lambda) & \hdots \\ & & p(\lambda) & p'(\lambda) & \hdots \\ & & & p(\lambda) & \hdots \\ & & & & \ddots \\ \end{bmatrix}$

If block ${B_i}$ has size ${k}$, then ${\lambda_i}$ has multiplicity ${k}$ in ${p(.)}$ and therefore ${p(\lambda_i) = p'(\lambda_i) = \hdots = p^{(k-1)}(\lambda_i)}$ and therefore, ${p(B_i) = 0}$ as we wanted to prove.

It turned out not to be a very very short proof, but it is still short, since it uses mostly elementary stuff and the proof is really intuitive in some sense. I took some lessons from that: (i) first it reinforces my idea that, if I need to say something about a matrix, the first thing I do is to look at its eigenvectors decomposition. A lot of Linear Algebra problems are very simple when we consider things in the right basis. Normally the right basis is the eigenvector basis. (ii) not all matrices are diagonalizable. But in those cases, Jordan Canonical Form comes in our help and we can do almost the same as we did with eigenvalue decomposition.

Categories: theory Tags:

## Using expanders to prove sum-product inequalities in finite fields

I am happy to have the first guest post of BigRedBits written by Igor Gorodezky about an elegant and exciting result in combinatorics.

————————-

I’m fortunate enough to be spending this semester in beautiful Los Angeles as a core participant in the 2009 long program on combinatorics at IPAM (an NSF-funded math institute on UCLA’s campus). We’ve recently wrapped up the first part of the program, which consisted of tutorial lectures on various topics in combinatorics. There was an abundance of gorgeous mathematics, and with Renato’s kind permission I’d like to hijack his blog and write about what to me was one of the most memorable lectures.

This was a lecture by Jozsef Solymosi of the University of British Columbia describing some of his recent work on the sum-product problem in finite fields. In particular, he outlined a spectral-graph-theoretic proof of a recent sum-product inequality due to Garaev. Solymosi’s proof is an extremely clever and elegant application of spectral graph theory to a classical problem in combinatorial number theory, and so I thought I’d present it here. Before stating the result and giving Solymosi’s proof, let us begin with a very brief introduction to the sum-product problem.

1. Introduction

Given a finite set of real numbers ${A}$, define the sum set

$\displaystyle A+A = \{a+b \mid a,b \in A\}$

and the product set

$\displaystyle A \cdot A = \{ab \mid a,b \in A\}.$

Both the sum set and the product set clearly must have cardinality between ${|A|}$ and ${|A|^2}$. Observe that if ${A}$ is an arithmetic progression then ${|A+A| \approx 2|A|}$ while ${|A \cdot A| \approx |A|^2}$, while if ${A}$ is a geometric progression then ${|A \cdot A| \approx 2|A|}$ while ${|A + A| \approx |A|^2}$. Intuition suggests that keeping ${|A+A|}$ small by giving ${A}$ lots of additive structure inevitably blows up ${|A \cdot A|}$, while keep ${|A \cdot A|}$ small by giving ${A}$ lots of multiplicative structure in turn blows up ${|A+A|}$. For an arbitrary ${A}$, one would expect at least one of these sets, if not both, to be fairly large.

Estimating the maximum of ${|A+A|}$ and ${|A \cdot A|}$ is the sum-product problem. It was posed in a paper by Erdos and Szemeredi, who proved the existence of a small constant ${c}$ such that

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+c} \right)$

for any finite ${A}$. They conjecture that we actually have

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{2-\delta} \right)$

for any ${\delta > 0}$ and sufficiently large ${|A|}$. In other words, the value of ${c}$ in their bound can be made arbitrarily close to 1.

Much ink has been spilled in attempts to push up the value of ${c}$. At present, the best sum-product bound is due to Solymosi and gives ${c \approx 3/11}$. As an aside, I want to mention an extremely simple and elegant probabilistic proof of Elekes that gives ${c=1/4}$; it is detailed in Alon and Spencer’s classic text The Probabilistic Method, and is an absolute gem (look in the chapter on crossing numbers of graphs).

2. The finite field variant

Solymosi’s IPAM lecture was not, however, on this original sum-product problem, but rather on its natural finite field analogue: if ${A}$ is a subset of ${\mathbb F_p}$, the finite field of prime order ${p}$, what can we say about the maximum of ${|A+A|}$ and ${|A \cdot A|}$? Observe that it is important to consider fields whose order is prime and not the power of a prime, for in the latter case we could take ${A}$ to be a subring and end up with the degenerate case ${|A|=|A+A|=|A \cdot A|}$.

Bourgain, Katz and Tao got the party started in 2004 by proving the following sum-product bound.

Theorem 1 For all ${\epsilon > 0}$ there exists ${\delta > 0}$ such that if ${A \subseteq \mathbb F_p }$ with ${p^{\epsilon} < |A| < p^{1+\epsilon}}$ then

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+\delta} \right).$

We note that the implied constant also depends on ${\epsilon}$. The best known bound is the following, due to Garaev (2007).

Theorem 2 If ${A \subseteq \mathbb F_p}$ then

$\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2},|A|^2p^{-1/2} \right\} \right).$

To illustrate the theorem, observe that if ${|A| \approx p^{2/3}}$ then ${\max\{ |A+A|, |A \cdot A| \} = \Omega( |A|^{5/4})}$. It is this theorem that Solymosi proves using spectral graph theory (Garaev’s original proof went by way of Fourier analysis and the estimation of exponential sums).

3. Solymosi’s proof

In this section we give Solymosi’s proof of Theorem 2 (we will assume familiarity with basic facts about eigenvalues and eigenvectors of adjacency matrices). Let us first establish some notation. Consider a ${d}$-regular graph ${G}$ and let the eigenvalues of its adjacency matrix be

$\displaystyle d=\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n.$

As usual, we define

$\displaystyle \lambda(G) = \max\{ \lambda_2,|\lambda_n|\}.$

Recall that if ${G}$ is connected and non-bipartite then ${\lambda(G)}$ is strictly smaller than ${d}$, and such a graph is an expander if ${d-\lambda(G)}$ is bounded below by some constant.

We will make use of a fundamental result in spectral graph theory: the expander mixing lemma.

Lemma 3 Let ${G}$ be a ${d}$-regular graph with ${n}$ vertices. For all ${S,T \subseteq V(G)}$ we have

$\displaystyle \left| e(S,T) - \frac{d}{n}|S||T| \right| \leq \lambda(G) \sqrt{|S||T|}$

where ${e(S,T)}$ is the number of edges with one endpoint in ${S}$ and the other in ${T}$.

The proof of the lemma is straightforward; we omit it because of space considerations, but it can be found in the survey on expanders by Linial, Hoory, and Wigderson.

Now, back to Theorem 2: we have a finite field ${\mathbb F_p}$ and a subset ${A}$. Solymosi proves the desired lower bound on ${\max\{ |A+A|, |A \cdot A| \}}$ by constructing a sum-product graph ${G_{SP}}$ over ${\mathbb F_p}$ and using its spectral properties to reason about ${|A+A|}$ and ${|A \cdot A|}$. So without further ado, let’s define ${G_{SP}}$.

The vertex set of ${G_{SP}}$ is ${\left( \mathbb F_p \setminus \{0\} \right) \times \mathbb F_p}$, and two vertices ${(a,b),(c,d)}$ have an edge between them if ${ac=b+d}$. It is easy to see that ${G_{SP}}$ has ${p(p-1)}$ vertices and is ${(p-1)}$-regular (some edges are loops). We also have the following key fact.

Lemma 4 Consider ${(a,b),(c,d) \in V(G_{SP})}$. If ${a=c}$ or ${b=d}$ then these two vertices have no common neighbor, otherwise they have precisely one.

Proof: This follows from the fact that the unique solution of the system

$\displaystyle \begin{array}{c} ax=b+y \\ cx=d+y \end{array}$

is given by

$\displaystyle \begin{array}{c} x = (b-d)(a-c)^{-1}\\ 2y = x(a+c)-b-d \end{array}$

which is only defined when ${a \neq c, b \neq d}$. $\Box$

Lemma 4 can be used to show that ${G_{SP}}$ is in fact a very good expander (those more familiar with the literature on expanders will recognize that moreover, ${G_{SP}}$ is almost a Ramanujan graph).

Lemma 5 ${\lambda(G_{SP}) < \sqrt{3p}}$.

Proof: Let ${M}$ be the adjacency matrix of ${G_{SP}}$. Recall that the ${(u,v)}$-entry of ${M^2}$ is the number of walks from ${u}$ to ${v}$ of length 2. If ${u=v}$, this number is the degree ${p-1}$, while if ${u \neq v}$, with ${u=(a,b)}$ and ${v=(c,d)}$, Lemma 4 tells us that this number is 1 if ${a\neq c}$ and ${b \neq d}$ and 0 otherwise. It follows that

$\displaystyle M^2 = J+(p-2)I-E \ \ \ \ \ (1)$

where ${J}$ is the all-1 matrix, ${I}$ is the identity matrix, and ${E}$ is the adjacency matrix of the graph ${G_E}$ whose vertex set is the same as ${G_{SP}}$, and in which two vertices ${(a,b)}$ and ${(c,d)}$ are connected by an edge if ${a=c}$ or ${b=d}$. It is easy to see that ${G_E}$ is a ${(2p-3)}$-regular graph.

Since ${G_{SP}}$ is regular and its adjacency matrix ${M}$ is symmetric, we know that the all-1 vector is an eigenvector of ${M}$ and all other eigenvectors are orthogonal to it. It is easy to check that ${G_{SP}}$ is connected and not bipartite, so that the eigenvalue ${p-1}$ has multiplicity 1, and for any other eigenvalue ${\theta}$ we have ${|\theta| < p-1}$.

Given such an eigenvalue ${\theta}$, let ${\bf v}$ be a corresponding eigenvector. Then by equation~(1),

$\displaystyle \theta^2 \mathbf{v} = (p-2)\mathbf{v} - E \mathbf v$

since ${J\mathbf v}$ is the all-0 vector. Therefore ${p-2-\theta^2}$ is an eigenvalue of ${E}$.

Now, the degree of ${G_E}$ is an upper bound on the absolute value of every eigenvalue of ${E}$. It follows that

$\displaystyle p-2-\theta^2 \geq -2p+3$

which implies ${|\theta| < \sqrt{3p}}$, as desired. $\Box$

So ${G_{SP}}$ is an expander; very good, but what about ${A}$? Solymosi introduces ${A}$ into the proof through very clever use of the expander mixing lemma: if we define ${S,T \subseteq V(G_{SP})}$ by

$\displaystyle S=(A \cdot A) \times (-A), \ \quad T=(A^{-1}) \times (A+A)$

then that lemma tells us that

$\displaystyle e(S,T) \leq \frac{|S||T|}{p} + \lambda(G_{SP}) \sqrt{|S||T|} < \frac{|A\cdot A||A+A||A|^2}{p} + \sqrt{3p|A \cdot A||A+A||A|^2}$

where the second inequality used Lemma 5.

But for every ${a,b,c \in A}$ there is an edge between ${(ab,-c) \in S}$ and ${(b^{-1},a+c) \in T}$, so that ${e(S,T) \geq |A|^3}$. Using this observation and rearranging the resulting inequality gives

$\displaystyle \sqrt{|A \cdot A||A+A|} > \left( \frac{\sqrt{|A \cdot A||A+A|}}{p|A|}+\sqrt{3}\frac{p^{1/2}}{|A|^2} \right)^{-1}.$

Now, since ${(x+y)^{-1} \geq \frac{1}{2}\min\{x^{-1},y^{-1}\}}$ for positive ${x}$ and ${y}$, we find that

$\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ \frac{p|A|}{\sqrt{|A \cdot A||A+A|}}, |A|^2 p^{-1/2} \right\} \right)$

which in turn implies

$\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2}, |A|^2 p^{-1/2} \right\} \right).$

To finish the proof, we need only cite the two-term AM-GM inequality:

$\displaystyle \max\{ |A+A|, |A \cdot A| \} \geq \frac{|A \cdot A|+|A+A|}{2} \geq \sqrt{|A \cdot A||A+A|} .$

4. A very terse bibliography

Solymosi’s proof is from his paper “Incidences and the spectra of graphs” (requires institutional access).

A more knowledgeable treatment of sum-product problems than I could ever provide can be found in these two entries from Terry Tao’s blog. In these, Tao provides a detailed introduction to the problem, gives the probabilistic proof of Elekes’ bound, discusses an interesting cryptographic application, and provides many references.

### Igor Gorodezky

Categories: theory Tags:


text:
# A new strategy for querying priced information.

Cicalese F, Laber ES (2005)
In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). 674-683.

Conference Paper | Published | English

Author
;
Publishing Year
PUB-ID

### Cite this

Cicalese F, Laber ES. A new strategy for querying priced information. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). 2005: 674-683.
Cicalese, F., & Laber, E. S. (2005). A new strategy for querying priced information. Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005), 674-683.
Cicalese, F., and Laber, E. S. (2005). “A new strategy for querying priced information.” in Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005) 674-683.
Cicalese, F., & Laber, E.S., 2005. A new strategy for querying priced information. In Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). pp. 674-683.
F. Cicalese and E.S. Laber, “A new strategy for querying priced information.”, Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005), 2005, pp.674-683.
Cicalese, F., Laber, E.S.: A new strategy for querying priced information. Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). p. 674-683. (2005).
Cicalese, F., and Laber, E. S. “A new strategy for querying priced information.”. Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). 2005. 674-683.
This data publication is cited in the following publications:
This publication cites the following data publications:

### Export

0 Marked Publications

Open Data PUB


text:
### havaliza's blog

By havaliza, 8 years ago,

Hi all! :{

We're glad to invite you to participate in Codeforces Round #173 prepared by A.K.Goharshady, LGM and me (havaliza). I want to thank Gerald, MikeMirzayanov and Delinur who helped us to prepare the round on this platform. And thanks to Dani1373, hhoomn, MrM, MMJ and xorfire who tested the problems and helped us a lot.

Today is LGM's birthday and yesterday was gpac's birthday. Happy birthday to you guys! ^.^

Hope you enjoy today's round and have lots of fun. :)

Update. The editorial is out!

• +279

 » 8 years ago, # |   +70 Happy Birthday!!!
•  » » 8 years ago, # ^ |   +2 ALL say HappyBirthday No one ask for score distribution :D
 » 8 years ago, # |   +22 Hi. And tomorrow is my birthday. Hope to have a good contest to enjoy my birthday much more. :DAnd Happy Birthday you guys. Glad to know it. Wish you bests in whole LIFE.HF & GL!
 » 8 years ago, # |   -21 I want to participate,but I'm too tired:(
 » 8 years ago, # |   +34 Happy birthday to you guys(lgm,gpac,S.HASHEMI)!!! ^.^ and also Congratulations to havaliza,keivan,fab,dani1373 ,because of being selected for IOI team of IRAN for next year!!! hope you win 4 gold medals for IRAN!!!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +6 Thanks a lot. :D Wish you bests.
 » 8 years ago, # |   +4 Your prev contest was great! (at least for me!) I hope it will be like the prev! How is score distribution?
 » 8 years ago, # |   +22 I was surprised a lot! thank you havaliza :)
•  » » 8 years ago, # ^ |   +2 Happy birthday gpac. Wish you get rank 1 today. :D
•  » » » 8 years ago, # ^ |   0 Happy Birthday to you too! I hope you have the best day of your life and have a professional contest. Let's go to infinity and beyond it!!!!
•  » » » » 8 years ago, # ^ |   +2 Taxiiiiiii.....Infinity please.
•  » » » 8 years ago, # ^ |   -6 Happy birthday to you guys:)I hope you also will get present from codeforces like me)I had birhtday in 25.02 and codeforces gave me +61:) http://codeforces.ru/bestRatingChanges/213901:)
 » 8 years ago, # |   0 happy birthday boys <:-P And special thanks for preparing the contest :-)
 » 8 years ago, # | ← Rev. 2 →   0 173 cool number , because it is number my school ))
 » 8 years ago, # |   +3 A bunch of Problemsetters from IRAN :D
 » 8 years ago, # |   +6 Happy Birthday
 » 8 years ago, # |   -10 Happy Birthday guys :) god bless you !!
 » 8 years ago, # |   +11 wow! More than 3000 registered users :D .
•  » » 8 years ago, # ^ |   -11 due to iranian setter :D
 » 8 years ago, # |   +7 please tell us about score distribution ?
•  » » 8 years ago, # ^ |   +4 since it's no announcements about it, i think it's standard
 » 8 years ago, # | ← Rev. 9 →   -11 ...d
 » 8 years ago, # |   0 Problem B: jury solution for test 3 1000 0 998 2 503 497is "222". W T F???
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 0+2+497=499 499<=500
•  » » 8 years ago, # ^ |   0 Oh, i found my mistake :(
 » 8 years ago, # |   0 Who solved D and how?
•  » » 8 years ago, # ^ |   -10 For n=1 the situation is clear. For n=2 (two non-zero integers) if a[0]=a[1], first player wins, elsewhere he loses. For n=3 (three non-zero numbers) there are (300^3)/6 possible situations (excluding permutations of those), and for each of them we can calculate if the first player wins or loses in O(1).
•  » » » 8 years ago, # ^ |   0 in testcase 2 1 5 your solution is wrong. because first player can make situation 1 2 which is bad for the second player and first will win
•  » » » » 8 years ago, # ^ |   0 update a[0]=1 a[1]=5 2 is for n
•  » » » 8 years ago, # ^ |   +1 2 2 3
•  » » » 8 years ago, # ^ |   0 I think you meant vice versa for case n=2. didn't you?
•  » » » » 8 years ago, # ^ |   0 Fine, we can iterate through all (300^2)/2 situations as well.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Sorry. I was Wrong :|
•  » » » 8 years ago, # ^ |   0 if n=2 you are logically wrongbecause if a[0]!=a[1] you said that second is winner but the first player can make a move that makes also a[0]!=a[1] then and become the second then he is winner , so how become both first and second winners?e.glet n=2 , a[0]=1 , a[1]=3the first is the winner and the winning move is subtract 1 from a[1]
•  » » » » 8 years ago, # ^ |   +5 I know, mate. Just didn't think about it well.
•  » » 8 years ago, # ^ |   +11 Use dp[i][j][k] to stand for whether (i,j,k) is a state in which the first person will win. It can be easily proved that the number of (i,j,k) such that dp[i][j][k] is false is O(n^2). We can use dp[i][j][k]=false to update dp[i+t][j+t][k+t] dp[i+t][j][k] dp[i][j+t][k] dp[i][j][k+t]. And it takes O(n). So we can get an O(n^3) solution by this way.
•  » » » 8 years ago, # ^ |   0 May you please give further explanation about the O(N^2) bound on losing situations (i,j,k) ?
•  » » » » 8 years ago, # ^ |   +11 Because if (i,k,j) is false than (i',j,k) is true when i'>i, which means the number of tuples (i,j,k) that is false is O(1) for each pair (j,k).As there is O(n^2) such pair (j,k), it is obvious that the number of tuples (i,j,k) that is false is O(n^2).
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 My submission 3308449
 » 8 years ago, # |   +10 How to solve E?
•  » » 8 years ago, # ^ |   +30 3306281 0_o
•  » » » 8 years ago, # ^ |   0 Well, I don't think, this solution will survive system tests :D
•  » » » » 8 years ago, # ^ |   -8 Does it work for the numbers (in binary):1000 , 10 , 10 , 100, 1, 1100You say it should find 1111 but I don't see how it can.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 give 0 to right and give 6 to left it will be 0 ^ 1111 ? Edit:I got it.
•  » » » 8 years ago, # ^ |   +4 Isn't <1,7,2,1> a counterexample for this solution?!!!
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +2 No, since it's permitted take <1,7> and <1> for 7 points.<1,1,2,2,4,4,8,8,16,16> breaks it, though.
•  » » » » » 8 years ago, # ^ |   0 oh, your right. thanks.
•  » » 8 years ago, # ^ |   0 It can be solved by greedy algorithm using trie.
•  » » » 8 years ago, # ^ | ← Rev. 4 →   0 but dude what isn't it possible to make 63 for this: 6 13 21 3 61 1 2 but judge says 62.I mean we can give 0 to right and 6 to the left .Than the pleasure will be 111111^0=63 ?Edit: I got it.
 » 8 years ago, # |   0 My C is soo going to fail.
 » 8 years ago, # | ← Rev. 2 →   0 I notice a code will get TLE so I make generation to this testcase string a=""; for (int i = 0; i < 1000000; ++i){ a+='1'; } cout<
•  » » 8 years ago, # ^ |   0 Maybe, you should make "endl" after second "cout"?
•  » » » 8 years ago, # ^ |   0 but error say Input can't contain two or more consecutive spaces
•  » » 8 years ago, # ^ |   0 Maybe you mistook "code generator" and "input" just like me last time.
 » 8 years ago, # |   0 It is really hard to solve problems in Java, and Petr is really great, because he uses Java and he is the fastest coder.
•  » » 8 years ago, # ^ |   +1 Come on mate , This should have been well thought before taking petr as prefix in your handle. Now you are expected to code in Java :P
 » 8 years ago, # | ← Rev. 2 →   +5 Problem C was very interesting....a lot of people's solutions ( and also my solution!! ) has been hacked
•  » » 8 years ago, # ^ |   +4 I hacked 2 user with this testcase: 111 000
•  » » » 8 years ago, # ^ |   +5 I also hacked with: 1 0 :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +12 I hacked about 9 users with :0 0Lol.
•  » » » 8 years ago, # ^ |   +5 I found a hackable solution just before the contest was over. I guess C is the most trick one in this contest.
•  » » 8 years ago, # ^ |   +1 Very simple problem, but it has some pitfalls.
•  » » 8 years ago, # ^ |   0 Why do you have this weird if statement in your code? if ( yek1 >= ceil((float)yek2/(float)2) ){...} After some analysis you will know that one can construct every string(except a '0'-string that consists only of '0's), iff we have at least one '1' in our string.
•  » » » 8 years ago, # ^ |   0 Yes, I think i was very lucky that my solution has been hacked, because my algorithm has a lot of bugs and finally I found the answer!!
•  » » » » 8 years ago, # ^ |   0 I hoped my soloution had been hacked too, then I could submit the correct one... Grammere jomlam dorost bud??
 » 8 years ago, # |   +4 I'm waiting system testing, for lunch!!! Please, hurry up... :D
 » 8 years ago, # | ← Rev. 2 →   0 Deleted.
 » 8 years ago, # |   0 Testcase for problem C is to much (about 100 test). Systest will run very low.
•  » » 8 years ago, # ^ |   0 there are more than 100 test cases for D problem too
•  » » 8 years ago, # ^ |   0 Where is sence to make so many tests for so easy task?..
•  » » » 8 years ago, # ^ |   +17 Here: 3303326
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +2 It's bad example. If you know right solution — ( put "YES" only if '1' exists in both strings or doesnt exist in both ) you can make about 10-20 tests to check all the solutions. But not 100.
•  » » » » 8 years ago, # ^ |   +11 c1*r1 == 0 (mod 2^32), funny mistake!
 » 8 years ago, # |   +7 Great Contest! I realy Liked problems D and E even though i didn't solve them
 » 8 years ago, # |   -40 Today during the contest I got two messages from MIT_1996 who was in my room, asking for help in problem B with algorithm. Where should I report ??
•  » » 8 years ago, # ^ |   +13 i think you should forgive him and not report this.
•  » » 8 years ago, # ^ |   +11 You could have asked where to report a dishonesty without saying the name of the competitor in public chat. Is not a good practice to a shame people for such reasons in front of all.
 » 8 years ago, # |   +7 thx! very nice contest:)
 » 8 years ago, # |   -10 The problems are easy. Good contest
 » 8 years ago, # |   +1 That was a nice contest, thanks to havaliza and happy birthday to LGM and gpac...
 » 8 years ago, # |   0 I cant't exactly understand the meaning of problem E ! We are asked to find the maximum of what ? (BitHaval and BitAryo) what does 'and' mean here?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 "The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness."
•  » » » 8 years ago, # ^ |   0 tnxwould u explain about test case 3 ?2 1000 1000
•  » » » » 8 years ago, # ^ |   +6 The sausages can be empty, so give 1000 to BitHaval and nothing to BitAryo :D
•  » » » » » 8 years ago, # ^ |   0 tnx, sorry, one more please :D test 8: 4 1 2 4 12 the answer is 15, why?
•  » » » » » » 8 years ago, # ^ |   0 for example, all to BitHaval: 4 xor 1 xor 2 xor 4 xor 12 = 15
•  » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I mean test 8, that is : n = 4 and the numbers are : 1 2 4 12
•  » » » » » » » » 8 years ago, # ^ |   0 Oh, sorry. In this case, give 1,2 to BitHaval and 12 to BitAryo.
•  » » » 8 years ago, # ^ |   0 Oh! I got it now. :|
 » 8 years ago, # |   +4 very good contest but I think test 26 from problem D should be in pretest , so many person got WA due to this test , thanks.
 » 8 years ago, # |   +9 that was a nice contest thanks to havaliza but why Bitlandians are weird they are amazing
 » 8 years ago, # |   +4 Thats funny. I solved my solution using Delphi compiler: http://codeforces.ru/contest/282/submission/3302945 The same code, using FPC: http://codeforces.ru/contest/282/submission/3311282
•  » » 8 years ago, # ^ |   +1 Thats not funny I think... :D exactly like the diffrence between visual studio compiler and GNU...
•  » » » 8 years ago, # ^ |   0 Something i have experienced while using CodeBlock for C++ and G++ compiler !!
 » 8 years ago, # |   +4 When will the plus and minuses appear on the graph???
 » 8 years ago, # |   +1 painting eggs is a very ancient and attractive custom in Iran and the children still do this
 » 8 years ago, # |   +3 Very nice problems. Thanks to authors!
 » 8 years ago, # |   +6 Happy birthday to all of you guys (gpac, LGM and S.HASHEMI)!!! and I hope that we get 4 Gold medals from havaliza, dani1373, fab and keivan!The contest was very cool! Thank you for problems.
 » 8 years ago, # |   +1 This is now 4 hours after contest but ratings had not changed yet... when does it want to change?? And I am right here in the site since the contest started... :D
 » 8 years ago, # |   0 Has anyone solved problem 'E' without a trie or with a easier solution to implement ?
•  » » 8 years ago, # ^ |   0 I have no idea what this does, but it looks suspicious: http://www.codeforces.com/contest/282/submission/3303893
•  » » » 8 years ago, # ^ |   0 It seems to be the same ideia using trie. However, the code is a lot more clear and simply.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +5 Well, what I did was following: I replaced the given array by an array, where . BTW, The given array was a[1..n], I just added the 0th element to indicate we didn't give the first person anything to eat. Now imagine we gave the first person a piece [0..l] (it is equivalent to [1..l]) and the second — [r..n]. Then the tasty value of this is . We can replace the value r - 1 to m. Now we want to maximize . Notice two things: 1) l and m is the only variables since n is fixed, 2) 0 ≤ l ≤ m ≤ n. Then just sort the array s and then for any 0 ≤ m ≤ n use binary search for digits in the binary representation of to find l. Total complexity is .My submission: 3304910
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 Thank you a lot ! For me this solution is much easier than author's :)
 » 8 years ago, # |   0 i think this my solution still wrong, but get accepted http://codeforces.com/contest/282/submission/3309655because 'is' never change, and did this solution true after i add is++? http://codeforces.com/contest/282/submission/3312416
 » 8 years ago, # |   0 Please don't delay publishing the editorial for this contest. thks
 » 8 years ago, # | ← Rev. 2 →   +8 Problem D was a nice DP problem. I calculated the losing scenarios offline and found a formula for it. Then just applied the formula and solve the problem in O(1). It was very fun. Problem E was a very nice problem too. I scratched my head for a little while to make it run in time, until I thought of building a trie, and I really like building tries :)
 » 8 years ago, # |   +1 Thanks for really interesting problems! But what mean's verdict Skipped? My solve of problem C — XOR and OR received Accepted in final tests. I see Skipped and only two solved problems today.
•  » » 8 years ago, # ^ |   0 hmm this is weird thing..happened to one once. let see if someone can explain it
 » 8 years ago, # |   0 I was actually shocked that problem B had a greedy solution to it. I was trying so hard to partition the numbers :P. But after end of competition when i saw some solutions which had got accepted i was surprised and confused. But then i came up with an inductive proof for the greedy method. Had fun. Will have to improve myself.
•  » » 8 years ago, # ^ |   +3 I thought about knapsack problem,but when i saw many accepted code I wrote greedy solution.Now i know why this solution is correct(with an inductive proof,as you say).
 » 8 years ago, # |   +10 I love this contest.
•  » » 8 years ago, # ^ |   0 I also ))